уємо Другие нерівності:
l 2 В® 2x 1 + 0,5 x 2 = 240;
x 1 = 0, x 2 = 240/0,5 = 480; x 2 = 0, x 1 = 240/2 = 120;
l 3 В® x 1 + x 2 = 150; x 1 = 0; x 2 = 150; x 2 = 0, x 1 = 150;
l 4 В® x 1 + x 2 = 110; x 1 = 0; x 2 = 110; x 2 = 0, x 1 = 110;
l 5 В® 10x 1 + 20x 2 = 1400;
x 1 = 0, x 2 = 1400/20 = 70; x 2 = 0, x 1 = 1400/10 = 140;
альо точка (0,0) 10 Г— 0 + 20 Г— 0 = 0 Ві 1400 НЕ відповідає нерівності, тому нам потрібна півплощіна Вище граничної прямої.
Таким чином отриманий многокутнік розв'язків, до речі - опукло, як завжди.
З метою знаходження максимуму цільової Функції
Z = 10 x 1 + 20 x 2 побудуємо лінію уровня цільової Функції, поклал Z = 0,
10 x 1 + 20 x 2 = 10; x 1 = 0, x 2 = 40 ; x 2 = 0; x 1 = 80;
ЗРОСТАННЯ цільової Функції позначає паралельне зміщення самій Собі догори, доки остання крапка НŠ​​Вийди на границю многокутніка розв'язків.
Ця точка відповідає перетин прямих
х 1 + 3,5 х 2 = 350; - l 1 (Г—) C (70; 80)
х 1 + х 2 = 250; - l 3
х 1 = 70, х 2 = 80,
Z max (x) = 10 Г— x 1 + 20 Г— x 2 = 10 Г— 70 + 20 Г— 80 = 23000 грн.
слушно зауваження у підручніку - ЯКЩО Було б нужно найти мінімальне Значення цільової Функції, так лінію уровня нужно зміщуваті униз, доки остання крапка Вийди на границю многокутніка розв'язків - це l 5 , УСІ крапки Якої є розв'язком задачі - Нескінченна множини РІШЕНЬ.
У Розглянуто випадка многокутнік розв'язків НЕ Тільки опукло, а ще и є замкненим. Можливі Варіанти опукло многокутніка розв'язків, Який є НЕОБМЕЖЕНИЙ.
У первом випадка Можливо найти максимальне значення цільової Функції, а у іншому випадка - мінімальне значення. На Наступний малюнку наведень приклад многокутніка розв'язків несумісної системи обмежень - розв'язок задачі математичного програмування відсутній.
В
Малюнок. Многокутнік розв'язків несумісної системи обмежень
задачі лінійного програмування
Тема 3. Симплексному метод розв'язання задач лінійного програмування
Перша праця по лінійному програмування булу Надруковано Канторовичем у 1939 году, но позбав после Відкриття Данцігом у 1949 году симплекс-методу розв'язання задачі лінійного програмування до цього класу задач вінікла зацікавленість. Симплекс-метод Дає аналітичний розв'язок лінійної задачі математичного програмування.
симплексного методу розв'язання задачі лінійного програмування грунтується на переході від одного опорного плану до Іншого таким чином, что шкірного разу Значення цільової Функції зростає (за умов, что завдання має оптимальний план, та Кожний з опорних планів НЕ є надмірнім ). Під опорним планом мают на увазі невід'ємній базисних розв'язок задачі лінійного програмування. Нагадаємо - базисний план (розв'язок) - решение системи обмежень. у якому УСІ Вільні змінні дорівнюють нулеві, тоб геометрично базисних план відповідає одній з вершин або граней многокутніка розв'язків.
Розглянемо Використання симплекс-методом для Вирішення задачі лінійного програмування на прікладі задачі про планування випуску ПРОДУКЦІЇ малим підпріємством. У зв'язку з тим, что ця задача булу розв'язано раніше, и ми з'ясували, что функціональні планові обмеження віконуються автоматично, а такоже з метою Спрощення ПОШУК, розглянемо Тільки функціональні обмеження ресурсів.
х 1 + 3,5 х 2 ВЈ 350;
2 х 1 + 0,5 х 2 ВЈ 240;
х 1 + х 2 ВЈ 150;
х 1 Ві 0;
х 2 Ві 0.
Z = f (x) = 10 x 1 + 20 x 2 ; Z В® max;
(-Z = - f (x) = - 10 x 1 - 20 x 2 - 0 Г— x 4 - 0 Г— x 5 ; В® min).
розв'язок задачі. Перетворімо функціональні обмеження-нерівності на обмеження-рівності Шляхом введенні у обмеження-нерівності невід'ємніх вільніх невідоміх y 1 , y 2 , y 3 (хочай Можливо Було б і х 3 , х 4 , х 5 ).
х 1 ...
