- матриця розмірності m 'п.
Задачу лінійного програмування, записану у формі (1.1) - (1.3), називають загальною задачею лінійного програмування (ОЗЛП). p> Якщо всі обмеження в задачі лінійного програмування є рівняннями і на всі змінні x j накладені умови невід'ємності, то вона називається завданням лінійного програмування в канонічній формі, або канонічної завданням лінійного програмування (КЗЛП). У матричній формі КЗЛП можна записати у наступному вигляді:
(1.7)
Оскільки будь оптимізаційна задача однозначно визначається цільовою функцією f і областю D, на якій відшукується оптимум (максимум), будемо позначати це завдання парою (D, f).
Домовимося щодо термінології, яка використовується в Надалі і є загальноприйнятою в теорії лінійного програмування.
Планом ЗЛП називається всякий вектор х з простору R n .
Припустимим планом називається такий план ЗЛП, який задовольняє обмеженням (1.2) - (1.3), тобто міститься в області D. Сама область D називається при цьому областю допустимих планів. Оптимальним планом х * називається такий допустимий план, при якому цільова функція досягає оптимального (у нашому випадку - максимального) значення, тобто план, що задовольняє умові
max f (x) = f (x * ).
Величина f * = f (x * ) називається оптимальним значенням цільової функції.
Рішенням завдання називається пара (х * , f * ), що складається з оптимального плану і оптимального значення цільової функції, а процес рішення полягає у знаходженні безлічі всіх рішень ЗЛП.
В В
1.2 Перехід до канонічної формі
Переважна більшість відомих методів розв'язання задач лінійного програмування призначені для канонічних завдань. Тому початковий етап рішення всякої загальної задачі лінійного програмування звичайно пов'язаний з приведенням її до деякої еквівалентної канонічної задачі.
Загальна ідея переходу від ОЗЛП до КЗЛП досить проста:
Г?ограніченія у вигляді нерівностей перетворюються на рівняння за рахунок додавання фіктивних невід'ємних змінних, які одночасно входять в цільову функцію з коефіцієнтом 0, тобто не роблять впливу на її значення;
Г?переменние, на які не накладено умова позитивності, представляються у вигляді різниці двох нових невід'ємних змінних:
В
Г?переменние, на які накладено умова непозитивним, представляються у вигляді нової неотрицательной змінної помноженої на -1:
В
Неважко помітити, що В«платоюВ» за перехід від загальної форми завдання лінійного програмування до канонічної є зростання її розмірності, що, за інших рівних умов, є чинником, що ускладнює процес рішення.
В В
2. СІМПЛЕКС-МЕТОД
В
2.1 Теоретичні основи симплекс-методу
Виходячи з властивостей лінійних екстр...
