Задачі лінійного програмування постановка задачі: методи рішення і формування
Симплексний метод для максимізації
Постановку задачі лінійного програмування з математичною моделлю для максимізації можна виконати із застосуванням симплекс-методу:
Перетворюють дані в систему рівнянь, вводячи слабкі змінні, щоб перетворити обмеження в рівняння, і переписують функцію в стандартну форму.
Записують початкову таблицю.
Вибирають стовпець розвороту, від’ємне число з найбільшою величиною в нижньому ряду, виключаючи крайню праву запис. Його стовпець є зведеним. Якщо є два кандидати, які вибирають один. Якщо всі числа в нижньому ряду дорівнюють нулю або позитивні, виключаючи крайню праву запис, то все готово і базове рішення максимізує цільову функцію.
Вибирають стрижень у стовпці. Вісь завжди має бути додатним числом. Для кожної позитивної запису «b» у стовпці зведених даних обчислюють відношення «a/b», де “a” є відповіддю у цьому рядку. З тестових коефіцієнтів вибирають мінімальне, тоді відповідне число «b» буде віссю.
Використовують стрижень, щоб очистити стовпець звичайним способом, стежачи за тим, щоб точно виконувати приписи для формулювання операцій зі рядками, описаним у керівництві за методом Гауса-Джордана, а потім міняють місцями стовпчик з міткою з колонки.
Змінна, спочатку позначає рядок зведення, є вихідною, а змінна, що позначає стовпець, є вхідною.
Для того щоб отримати базове рішення, відповідне до будь-якої таблиці в симплекс-методі, встановлюють в нуль всі змінні, які не відображаються, як мітки рядків. Значення відображається мітки рядка (активна змінна) — число в крайньому правому стовпці в рядку, поділена на число в цьому рядку в стовпці з номером тієї ж змінної.
