Зміст
Визначення ЗЛП
Перший алгоритм симплекс - методу
Алгоритм зворотної матриці
Про кінцівки симплекс - методу
Алгоритм побудови початкового опорного плану
Алгоритм штучного базису
Список літератури
Визначення ЗЛП
Загальним завданням лінійного програмування називається задача, яка полягає у визначенні максимального (мінімального) значення функції
(9.1)
за умов
В
(9.2) (9.3) (9.4)
де - задані постійні величини і.
Функція (9.1) називається цільовою функцією (або лінійною формою) задачі (9.1) - (9.4), а умови (9.2) - (9.4) - обмеженнями даного завдання.
Канонічної або основним завданням лінійного програмування називається задача, яка полягає у визначенні максимального значення функції
(9.5)
при виконанні умов:
(9.6) (9.7) де.
Перший алгоритм симплекс методу
Наведемо опис алгоритму стосовно ЗЛП, записаної в канонічній формі з односторонніми обмеженнями:
В
Нехай відомий початковий опорний план з базисом, тобто - Базисні компоненти, - небазисні компоненти. p> Обчислення зручно виконувати, заповнюючи наступну симплекс-таблицю:
C ... ... № PB ... ... t1 ... ... ........................... ...... ........................... m ... ... ... ...
Порядок обчислень по першому алгоритмом:
Крок 1. Знайти обернену до матрицю. p> Крок 2. Обчислити коефіцієнти розкладання векторів умов по базису, використовуючи розрахункову формулу:
В
і заповнити ними стовпці симплекса-таблиці нульової ітерації.
Крок 3. Обчислити значення лінійної форми, як скалярний добуток відповідних стовпців симплекс-таблиці, і значення оцінок векторів умов щодо базису відповідно до формули як скалярний твір стовпців і симплекс-таблиці без коефіцієнта, тобто за розрахунковою формулою
Отриманими значеннями заповнити-й рядок симплекс-таблиці.
Крок 4. Перевірити оптимальність опорного плану. p> Якщо, то - оптимальний опорний план і, тоді, у стовпці симплекса-т...
