ра решение ЗЛП ПОЧИНАЄТЬСЯ з Приведення ее до канонічної форми, тоб до стандартної форми Завдання, орієнтованої на розроблення самє для цієї форми метод решение. Завдання лінійного програмування в канонічній ФОРМІ має сенс за умови n> m. У цьом випадка Повністю опісується область допустимих РІШЕНЬ (ОДР) ЗЛП, что геометрично є опукло многогранником в просторі Евкліда Rn [1]. Опукло фігура, як відомо, характерізується тією властівістю, что, ЯКЩО Дві точки X1 и X2 належати Цій фігурі, то и увесь відрізок X1X2 захи їй. Крім того, доведено, что оптімальне решение ЗЛП всегда лежить На межі ОДР. Тому справедливий Висновок про ті, что, прінаймні, одна з Кутовий (опорних) точок опукло багатогранника ОДР є точкою оптимуму. Для того, щоб візначіті координати опорної точки, усю безліч змінніх X={xj}, j=звітність, розділіті на Дві підмножіні
:
підмножіна базисних змінніх
,
при цьом число m базисних змінніх дорівнює числу рівнянь (обмежується) за умови, что рівняння є НЕ-залежних; підмножіна других n - m вільніх (внебазісних) змінніх {xj}, j_Бі [1].
Кількість можливіть варіантів розподілу змінніх на базисних и вільніх (число базісів) дорівнює.
Найбільш очевидний метод решение ЗЛП Полягає в тому, щоб для шкірного з базісів найти координати відповідніх опорних точок, віділіті з них точки, что належати ОДР, а потім з них, у свою черго, вібрато ту, координат та Якої максімізувалі цільову функцію. На Відміну Від цього методу, что реалізовує, по суті, ідею полного перебору опорних точок ОДР, відомій ефектівнішій так звань симплекс-метод решение ЗЛП.
У Основі симплекс-методу лежить підхід, что Включає:
вибір опорної точки, что захи ОДР (вибір початкових допустимого базису);
перевірку опорної точки на оптімальність;
вибір нового базису, что дозволяє мінімізуваті число опорних точок на Траєкторії у разі невиконання умов оптімальності.
Приведення початкових завдань до канонічного виду.
Маємо початкова ЗЛП:
(x)=1141x1 +1040 x2 +1318 x3 +684 x4 +2757 x5 +466 x6
;
585;
390;
323;
525;
330;
451;
825;
960;
640;
1200;
380;
300;, x2, x3, x4, x5, x6 0
Пріведемо ЗЛП до канонічної форми. Приведення системи обмежень, заданість У ФОРМІ нерівностей, до канонічної форми рівності здійснюється за помощью відповідного Збільшення розмірності вектора X=(x1, x2, x3, x4, x5, x6) з урахуванням обов'язкової позітівності усіх его складових.
Таким чином, ЗЛП в канонічній ФОРМІ має вигляд:
max {1141x1 +1040 x2 +1318 x3 +684 x4 +2757 x5 +466 x6};
(7
Поиск допустимого базису.
Заповнення симплекс-таблиці.
ЗЛП в канонічній ФОРМІ можна записатися в матричному віді:
(8)
b=(1500, 585, 390, 323, 525, 330, 451, 825, 960, 640, 1200, 380, 300) T=(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) T=(1144,1040,1318,686,2757,466,0,0,0,0 , 0,0,0,0,0,0,0,0,0)
Поиск допустимого базису ПОЧИНАЄТЬСЯ з АНАЛІЗУ стовпців матріці A=(A1, A2,., A19), вікорістовуваної в запісі обмеження (8) канонічної форми ЗЛП. Як базісні слід вібіраті Такі +13 змінніх, Яким відповідає набор стовпців, что дозволяють Скласти одінічну матрицю P=(Aj1, Aj2,...
