Линеарна оптимизација

Ова поглавје е наменето како вовед во сложената тема за линеарно оптимизирање (ЛОП). Во овој контекст, се појавуваат некои прашања што сакаме постепено да ги разјаснуваме.

Што се подразбира под поимот „линеарна оптимизација“?
Како математички може да се формулира проблемот?
Кои се познати, користат случаи на линеарно оптимизирање?
Кои методи на решение се таму?
Кои решенија се можни?

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

Што е линеарна оптимизација?

Линеарната оптимизација може да се користи како (практична) Примена на системи за линеарна нееднаквост да бидат разбрани. Претходниот напис „Системи на линеарни нееднаквости со две променливи“ е соодветно на основата за ова поглавје.

Линеарната оптимизација се занимава со оние математички процеси кои ја одредуваат најголемата или најмалата вредност на линеарната функција. Овие обично се ограничени со дополнителни услови.

На линеарна оптимизација се занимава со максимизирање или минимизирање на линеарна функција под ограничувања.

Математичка формулација

Таканаречената „линеарна програма“ (ЛП) се состои од следниве компоненти

Објективна функција

Линеарната функција што треба да се зголеми (минимизира) се нарекува објективна функција. Променливите (x, y, 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 \ крај \)

(Состојба на ненегативност)

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

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

\ (x \ geq 0 \) графички значи дека само областа десно од оската y е релевантна за набудувањето.

\ (y \ geq 0 \) графички значи дека само областа над х-оската е релевантна за разгледување.

Ако некој ги набудува и \ (x \ geq 0 \) и \ (y \ geq 0 \), ќе открие дека само првиот квадрант на координатниот систем е релевантен за разгледување.

Областа што е обележана со боја е област што ја исполнува условот за негативност.

Апликации

Во пракса има голем број апликации за линеарно оптимизирање. Некои од нив ќе бидат објаснети подетално користејќи примери.

Бидејќи условот за негативност мора да биде исполнет во следниве примери, графичкото размислување е ограничено на 1-ви квадрант на координатниот систем.

Во овој момент, се препорачува повторно да се погледне во поглавјето "Линеарни системи на нееднаквости со две варијабли".

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

Два различни типа на кабли се произведуваат во фабрика и се продаваат за 150 евра (тип А) и 100 евра (тип Б) на 100 метри. Каблите од типот А бараат 16 кг пластика и 4 кг бакар. Каблите од типот Б бараат 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.) Графичко разгледување

Дали сакате 1-ва секундарна состојба
\ (16x + 6y \ leq 252 \)
нацртај во координатниот систем, треба да се реши нееднаквоста за \ (y \) \ (6y \ leq - 16x + 252 \)
\ (y \ leq - \ fracx + 42 \)
а потоа ја толкуваме нееднаквоста како права равенка
\ (y = - \ fracx + 42 \)

Обоената област ја означува областа што го исполнува 1-от секундарен услов.

Дали би сакале 2-ри секундарен услов
\ (4x + 12y \ leq 168 \)
нацртај во координатниот систем, треба да се реши нееднаквоста за \ (y \) \ (12y \ leq - 4x + 168 \)
\ (y \ leq - \ fracx + 14 \)
а потоа ја толкуваме нееднаквоста како права равенка
\ (y = - \ fracx + 14 \)

Обоената област ја означува областа што го исполнува 2-риот секундарен услов.

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

Обоената област ја означува областа што го исполнува третиот секундарен услов.

На Сет решенија на системот за линеарна нееднаквост.
\ (16x + 6y \ leq 252 \)
\ (4x + 12y \ leq 168 \)
\ (y \ leq 2x \)
.е обележано со боја во соседната графика.

Сега знаеме како графички изгледа изводливиот сет на решенија. Следниот чекор е да се побара оптимално решение. Ова можеме да го одредиме или графички или со пресметка.

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

Бидејќи оптималниот дел одговара на аголната точка од областа на решението, прво го читаме: \ (P_1 (0,0) \); \ (P_2 (6.12) \); \ (П_3 (12,10) \); \ (P_4 (15,75; 0) \);

Сега ги ставаме точките во објективната функција и го одредуваме максимумот.

\ (z (0,0) = 150 \ пати 0 + 100 \ пати 0 = 0 € \)

\ (z (6,12) = 150 \ пати 6 + 100 \ пати 12 = 2,100 € \)

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

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

одговор:
Фабриката ја максимизира својата продажба додека ги набудува ограничувањата ако произведува кабел од 12 x 100m од типот А и 10 x 100m кабел од типот Б.

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

Можете да го најдете графички максимум, со цртање на објективната функција и потоа паралелно префрлување додека не се означи права точка на последниот агол на областа на решението. Последниот агол тогаш одговара на оптималното решение.

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

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

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

Авиокомпанија сака да воспостави врска со летот помеѓу два града. Целта е да се пренесат 1.600 луѓе и 96 тони товар во одреден временски период. Во моментов има два вида авиони на располагање: 11 авиони од типот А и 8 авиони од типот Б. Типот А чини 4.000 евра по лет и може да пренесе 200 лица и 6 тони товар. Типот Б чини 1.000 евра по лет и може да пренесе 100 луѓе и 15 тони товар.

Како и многу авиони од секој тип, авиокомпанијата ќе работи под ограничувања за да ги минимизира своите трошоци?

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

\ започне
& \ текст & \ текст & \ текст \\ \ линија
\ текст & 200 & 100 & 1600 \\ \ линија
\ текст & 6 и 15 и 96 \\ \ линија
\ текст & 4.000 & 1.000 и
\ крај

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.) Графичко разгледување

Дали сакате 1-ва секундарна состојба
\ (200x + 100y \ geq 1600 \)
нацртај во координатниот систем, треба да се реши нееднаквоста за \ (y \) \ (100y \ geq -200x + 1600 \)
\ (y \ geq -2x + 16 \)
а потоа ја толкуваме нееднаквоста како права равенка
\ (y = -2x + 16 \)

Обоената област ја означува областа што го исполнува 1-от секундарен услов.

Дали би сакале 2-ри секундарен услов
\ (6x + 15y \ geq 96 \)
нацртај во координатниот систем, треба да се реши нееднаквоста за \ (y \) \ (15y \ geq - 6x + 96 \)
\ (y \ geq - 0,4x + 6,4 \)
а потоа ја толкуваме нееднаквоста како права равенка
\ (y = - 0,4x + 6,4 \)

Обоената област ја означува областа што го исполнува 2-риот секундарен услов.

3-ти секундарен услов
\ (x \ leq 11 \)
е паралелна со оската y со пресек на оската \ (x = 11 \).

Обоената област ја означува областа што го исполнува третиот секундарен услов.

4-ти секундарен услов
\ (y \ leq 8 \)
е паралелна со x-оската со пресек на оската \ (y = 8 \).

Обоената област ја означува областа што го исполнува 4-от секундарен услов.

На Сет решенија на системот за линеарна нееднаквост.
\ (200x + 100y \ geq 1600 \)
\ (6x + 15y \ geq 96 \)
\ (x \ leq 11 \)
\ (y \ leq 8 \)
.е обележано со боја во соседната графика.

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

Бидејќи оптималниот дел одговара на еден агол од областа на решението, прво го читаме: \ (P_1 (6,4) \); \ (P_2 (4.8) \); \ (П_3 (11,8) \); \ (P_4 (11.2) \);

Сега ги ставаме точките во објективната функција и го одредуваме минимумот.

\ (z (6,4) = 4,000 \ пати 6 + 1000 \ пати 4 = 28,000 € \)

\ (z (4.8) = 4.000 \ пати 4 + 1.000 \ пати 8 = 24,000 € \ квадрат \ праворое \ квад \ текст \)

\ (z (11,8) = 4,000 \ пати 11 + 1000 \ пати 8 = 52,000 € \)

\ (z (11,2) = 4,000 \ пати 11 + 1000 \ пати 2 = 46,000 € \)

одговор:
Авиокомпанијата ги минимизира своите трошоци во согласност со ограничувањата доколку работи со 4 авиони од типот А и 8 авиони од типот Б.

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

Можете да го најдете графички минимум, со цртање на објективната функција и потоа паралелно префрлување додека не се означи права точка на првиот агол на областа на решението. Првиот агол тогаш одговара на оптималното решение.

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

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

Можни решенија

Во примерите погоре, веќе видовме дека проблемот со оптимизација може да има единствено решение. Исто така е можно да има неколку решенија или воопшто да нема решение.

Во продолжение ќе најдете графички пример за секое решение. Целта е секогаш да се најде минимум.

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

. Веќе разгледавме детално два примери погоре.

Бесконечен број на оптимални решенија

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

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

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

Заклучок

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

Ако линеарната програма има само две варијабли, графичка анализа е погодна за решавање на задачата за оптимизација.

На максимум може да се најде графички со цртање во објективната функција и нејзино паралелно поместување се додека не достигне точка на последниот агол на областа на решението.
На минимум може да се најде графички со цртање во објективната функција и нејзино паралелно поместување се додека не достигне точка на првиот агол на областа на решението.

Во принцип, задачите за линеарна оптимизација можат да имаат јасен, бесконечен број или без (оптимално) решение.

За линеарни програми со повеќе од две варијабли, графички приказ (главно) не е можен. Во пракса, во овој случај оптималот се пресметува со употреба на т.н. алгоритам на симплекс.

Јас се викам Андреас Шнајдер и ја извршувам бесплатната и наградувана платформа за учење математика www.mathebibel.de со полно работно време од 2013 година. До 1 милион ученици, родители и наставници ги гледаат моите изјави секој месец. Објавувам нови содржини скоро секој ден. Претплатете се на мојот билтен сега и добијте 3 од моите 46 е-книги бесплатно!

ПС: Веќе ја видов тековната епизода од мојата серија #MatheAmMontag?