Линейна оптимизация

Тази глава е предназначена като въведение в сложната тема за линейната оптимизация (LOP). В този контекст възникват някои въпроси, които искаме да изясним постепенно.

Какво се разбира под термина "линейна оптимизация"?
Как може математически да се формулира проблемът?
Какви са известните случаи на използване на линейна оптимизация?
Какви методи за решение има?
Какви решения са възможни?

Нашите обяснения в тази глава са ограничени до линейна оптимизация с две променливи.

Какво е линейна оптимизация?

Линейната оптимизация може да се използва като (практически) Приложение на линейни системи за неравенство да бъде разбран. Предишната статия "Системи на линейни неравенства с две променливи" е съответно основата на тази глава.

Линейната оптимизация се занимава с тези математически процеси, които определят най-голямата или най-малката стойност на линейна функция. Те обикновено са ограничени от допълнителни условия.

The линейна оптимизация се занимава с максимизиране или минимизиране на линейна функция при ограничения.

Математическа формулировка

Така наречената „линейна програма“ (LP) се състои от следните компоненти

Целева функция

Линейната функция, която трябва да бъде максимизирана (минимизирана), се нарича целева функция. Променливите (\ (x \), \ (y \)), възникващи в целевата функция, се наричат променливи на решение.

Ограничения (ограничения)

\ (\ begina_1x + b_1y & \ leq c_1 \\ a_2x + b_2y & \ leq c_2 \\\ qquad \ vdots \ qquad \ vdots \\ a_nx + b_ny & \ leq c_n \ end \)

(Условие за неотрицателност)

В повечето практически проблеми променливите за решение са ограничени до стойности, по-големи или равни на нула. Причината за това е, че те обикновено не могат да приемат отрицателни стойности. Например, една компания не може да произвежда „отрицателен брой“ продукти.

Екскурс: Какво означава графично условието за неотрицателност?

\ (x \ geq 0 \) графично означава, че само площта вдясно от оста y е от значение за разглеждане.

\ (y \ geq 0 \) графично означава, че само площта над оста x е релевантна за разглеждане.

Ако човек наблюдава както \ (x \ geq 0 \), така и \ (y \ geq 0 \), ще открие, че само 1-ви квадрант на координатната система е от значение за разглеждането.

Следователно зоната, подчертана в цвят, е зоната, която отговаря на условието за отрицание.

Приложения

На практика има различни приложения за линейна оптимизация. Някои от тях ще бъдат обяснени по-подробно на примери.

Тъй като условието за неотрицателност трябва да бъде изпълнено в следващите примери, графичното разглеждане е ограничено до 1-ви квадрант на координатната система.

На този етап силно се препоръчва да погледнете отново главата "Линейни системи от неравенства с две променливи".

а) производствен проблем

Два различни вида кабели се произвеждат във фабрика и се продават за 150 евро (тип А) и 100 евро (тип В) на 100 метра. Кабелите тип А изискват 16 кг пластмаса и 4 кг мед. Кабелите тип B изискват 6 кг пластмаса и 12 кг мед. Количеството произведен В не трябва да бъде по-голямо от двойното количество на А. Освен това в момента доставката на материали е само 252 кг пластмаса и 168 кг мед.

Кои количества от двата вида кабели максимизират оборота на компанията, като същевременно спазват ограниченията?

1.) Ясна компилация на задачата

2.) Математическа формулировка на задачата

Целева функция	\ (z (x, y) = 150x + 100y \ quad \ rightarrow \ quad \ text \)
Ограничения	\ (\ започнете 16x + 6y & \ leq 252 \\ 4x + 12y & \ leq 168 \край\)
. и поради \ (y \ leq 2x \) имаме:	\ (2x - y \ geq 0 \)
Условие за неотрицателност	\ (x \ geq 0 \) \ (y \ geq 0 \)

3.) Графично разглеждане

Искате ли първото вторично състояние
\ (16x + 6y \ leq 252 \)
изчертайте в координатна система, трябва да се реши неравенството за \ (у \) \ (6y \ leq - 16x + 252 \)
\ (y \ leq - \ fracx + 42 \)
и след това интерпретирайте неравенството като уравнение с права линия
\ (у = - \ fracx + 42 \)

Цветната зона обозначава зоната, която отговаря на 1-во вторично условие.

Искате ли второто вторично състояние
\ (4x + 12y \ leq 168 \)
изчертайте в координатна система, трябва да се реши неравенството за \ (y \) \ (12y \ leq - 4x + 168 \)
\ (y \ leq - \ fracx + 14 \)
и след това интерпретирайте неравенството като уравнение с права линия
\ (у = - \ fracx + 14 \)

Цветната зона показва областта, която отговаря на второто вторично условие.

Третото вторично условие е:
„Количеството произведен В не трябва да бъде по-голямо от двойното количество на А.“
. или формулирана математически: \ (y \ leq 2x \)

Цветната област показва областта, която отговаря на 3-то вторично условие.

The Набор от решения на системата за линейно неравенство.
\ (16x + 6y \ leq 252 \)
\ (4x + 12y \ leq 168 \)
\ (y \ leq 2x \)
.е подчертано в цвят в съседната графика.

Сега знаем как графично изглежда възможният набор от решения. Следващата стъпка е да се потърси оптималното решение. Можем да определим това или графично, или чрез изчисление.

4.1) Определете оптималното решение (математическо)

Тъй като оптимумът съответства на ъглова точка на зоната на решението, първо я отчитаме: \ (P_1 (0,0) \); \ (P_2 (6.12) \); \ (P_3 (12,10) \); \ (P_4 (15,75; 0) \);

Сега поставяме точките в целевата функция и определяме максимума.

\ (z (0.0) = 150 \ по 0 + 100 \ по 0 = 0 € \)

\ (z (6.12) = 150 \ по 6 + 100 \ по 12 = 2100 € \)

\ (z (12.10) = 150 \ cdot 12 + 100 \ cdot 10 = 2 800 € \ qquad \ rightarrow \ quad \ text \)

\ (z (15,75; 0) = 150 \ по 15,75 + 100 \ по 0 = 2 362,50 € \)

отговор:
Фабриката увеличава продажбите си, като същевременно спазва ограниченията, когато произвежда 12 х 100 м кабел от тип А и 10 х 100 м кабел от тип В.

4.2) Определете оптималното решение (графично)

Можете да го намерите графично максимум, чрез изтегляне на целевата функция и след това паралелно преместване, докато правата линия не означава последна ъглова точка от зоната на разтвора. Тогава последният ъгъл съответства на оптималното решение.

Първо решаваме целевата функция за \ (y \).
\ (z (x, y) = 150x + 100y = 0 \)
\ (100y = -150x \)
\ (у = -1,5x \)
.да ги нарисувате в координатната система. След това преместваме правата линия успоредно, докато стигнем последния ъгъл на зоната на решението.

Оптимума (тук: максимум) е показан на графиката с червена точка.

б) Проблем с транспорта

Авиокомпания иска да създаде полетна връзка между два града. Целта е да се транспортират 1600 души и 96 тона товар за определен период от време. В момента се предлагат два типа самолети: 11 самолета тип А и 8 самолета тип В. Тип А струва 4000 евро на полет и може да превозва 200 души и 6 тона товар. Тип Б струва 1000 евро на полет и може да превозва 100 души и 15 тона товар.

Подобно на много самолети от всеки тип, авиокомпанията ще работи при ограничения, за да сведе до минимум разходите си?

1.) Ясна компилация на задачата

\ започнете
& \ text & \ text & \ text \\ \ hline
\ text & 200 & 100 & 1600 \\ \ hline
\ text & 6 & 15 & 96 \\ \ hline
\ текст & 4000 & 1000 &
\край

2.) Математическа формулировка на задачата

Целева функция	\ (z (x, y) = 4000x + 1000y \ quad \ rightarrow \ quad \ text \)
Ограничения	\ (\ започнете 200x + 100y & \ geq 1600 \\ 6x + 15y & \ geq 96 \край\)
. също се прилага:	\ (x \ leq 11 \) \ (y \ leq 8 \)
Условие за неотрицателност	\ (x \ geq 0 \) \ (y \ geq 0 \)

3.) Графично разглеждане

Искате ли първото вторично състояние
\ (200x + 100y \ geq 1600 \)
изчертайте в координатна система, трябва да се реши неравенството за \ (у \) \ (100y \ geq -200x + 1600 \)
\ (y \ geq -2x + 16 \)
и след това интерпретирайте неравенството като уравнение с права линия
\ (у = -2x + 16 \)

Цветната зона обозначава зоната, която отговаря на 1-во вторично условие.

Искате ли второто вторично състояние
\ (6x + 15y \ geq 96 \)
изчертайте в координатна система, трябва да се реши неравенството за \ (y \) \ (15y \ geq - 6x + 96 \)
\ (y \ geq - 0,4x + 6,4 \)
и след това интерпретирайте неравенството като уравнение с права линия
\ (у = - 0,4x + 6,4 \)

Цветната област показва областта, която отговаря на второто вторично условие.

Третото вторично състояние
\ (x \ leq 11 \)
е успоредник на оста y с пресичане на оста \ (x = 11 \).

Цветната област показва областта, която отговаря на 3-то вторично условие.

Четвъртото вторично състояние
\ (y \ leq 8 \)
е успоредник на оста x с пресичането на оста \ (y = 8 \).

Цветната зона показва областта, която отговаря на 4-то вторично условие.

The Набор от решения на системата за линейно неравенство.
\ (200x + 100y \ geq 1600 \)
\ (6x + 15y \ geq 96 \)
\ (x \ leq 11 \)
\ (y \ leq 8 \)
.е подчертано в цвят в съседната графика.

Сега знаем как графично изглежда възможният набор от решения. Следващата стъпка е да се потърси оптималното решение. Можем да определим това графично или чрез изчисление.

4.1) Определете оптималното решение (математическо)

Тъй като оптимумът съответства на ъглова точка на зоната на решението, първо я отчитаме: \ (P_1 (6,4) \); \ (P_2 (4.8) \); \ (P_3 (11.8) \); \ (P_4 (11.2) \);

Сега поставяме точките в целевата функция и определяме минимума.

\ (z (6.4) = 4000 \ по 6 + 1000 \ по 4 = 28 000 € \)

\ (z (4.8) = 4000 \ по 4 + 1000 \ по 8 = 24 000 € \ qquad \ rightarrow \ quad \ text \)

\ (z (11,8) = 4000 \ по 11 + 1000 \ по 8 = 52 000 € \)

\ (z (11.2) = 4000 \ по 11 + 1000 \ по 2 = 46 000 € \)

отговор:
Авиокомпанията минимизира разходите си в съответствие с ограниченията, ако експлоатира 4 самолета тип А и 8 самолета тип Б.

4.2) Определете оптималното решение (графично)

Можете да го намерите графично минимум, чрез изтегляне на целевата функция и след това паралелно преместване, докато права линия не означава първа ъглова точка от зоната на разтвора. Тогава първият ъгъл съответства на оптималното решение.

Първо решаваме целевата функция за \ (y \).
\ (z (x, y) = 4000x + 1000y = 0 \)
\ (1000y = -4000x \)
\ (у = -4x \)
.да ги нарисувате в координатната система. След това преместваме правата линия успоредно, докато стигнем до първия ъгъл на зоната на решението.

Оптималното (тук: минимум) е показано на графиката с червена точка.

Възможни решения

В горните примери вече видяхме, че проблемът с оптимизацията може да има уникално решение. Възможно е също така да има няколко решения или изобщо да няма решение.

По-долу ще намерите графичен пример за всяко решение. Целта е винаги да се намери минимум.

Ясно оптимално решение

. Вече разгледахме два примера подробно по-горе.

Безкраен брой оптимални решения

Ако целевата функция е успоредна на ограничение, има няколко решения. Графично това означава, че при паралелното изместване целевата функция съвпада с тази ограничителна линия.

Не е оптимално решение

Има случаи, когато няма оптимално решение.

Заключение

Когато става въпрос за темата „линейна оптимизация“, често се налага да се справяме с проблемите с думите. Важно е да можете да прочетете основите на задачата и да я обобщите в таблица. С помощта на това ясно представяне последващата математическа формулировка е значително опростена.

Ако линейната програма има само две променливи, графичен анализ е подходящ за решаване на задачата за оптимизация.

The максимум може да бъде намерен графично чрез изтегляне на целевата функция и паралелно преместване, докато достигне последна ъглова точка от зоната на разтвора.
The минимум може да бъде намерен графично чрез изтегляне на целевата функция и паралелно преместване, докато достигне първа ъглова точка от зоната на разтвора.

По принцип задачите за линейна оптимизация могат да имат ясно, безкрайно число или никакво (оптимално) решение.

За линейни програми с повече от две променливи графичен изглед (най-вече) не е възможен. На практика в този случай оптимумът се изчислява с помощта на така наречения симплекс алгоритъм.

Казвам се Андреас Шнайдер и от 2013 г. ръководя безплатната и награждавана платформа за обучение по математика www.mathebibel.de. До 1 милион ученици, родители и учители разглеждат изявленията ми всеки месец. Публикувам ново съдържание почти всеки ден. Абонирайте се за моя бюлетин сега и получавайте безплатно 3 от моите 46 електронни книги!

PS: Вече видях текущия епизод от моя сериал #MatheAmMontag?