Симплексний метод розв’язування задач лінійного програмування

Снігур В.Л.

Вінницький національний аграрний університет.

Постановка проблеми. На сучасних підприємствах, що випускають високотехнологічну продукцію, для збирання і монтування продукції в основному використовуються автоматизовані лінії. Кожна з таких ліній може бути використана для виготовлення декількох різних видів продукції. В більшості випадків досить точно відомий штатний час виготовлення одиниці продукції кожного виду на деякій автоматизованій лінії. Кожна з ліній має обмежений фонд робочого часу за певний плановий період. А підприємство, у свою чергу, планує випуск кожного виду продукції за той же період.Для цього підприємство використовує різні методи математичного програмування, одним з таких є симплексний метод.

Мета даної роботи полягає в тому,щоб показати на скільки просто і доступно можна вирішити задану задачу таким методом.

Виклад основного матеріалу. Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану.

Перша праця з лінійного програмування була надрукована Л.В. Конторовичем у 1939 році, але лише після відкриття Дж. Данцигом у 1947 (1949) році симплекс-методу (симплекс – від лат. simplex –простий) розв’язання задачі лінійного програмування до цього классу задач виникла зацікавленість.

Симплекс-метод розв’язання задачі лінійного програмування ґрунтується на переході від одного опорного плану до іншого таким чином, що кожного разу значення цільової функції зростає (за умов, що задача має оптимальний план та кожний з опорних планів не є надмірним).

Під опорним планом розуміють невід’ємний базисний розв’язок задачі лінійного програмування. Нагадаємо: базисний план (розв’язок) – рішення системи обмежень, у якому всі вільні змінні дорівнюють нулю, тобто геометрично базисний план відповідає одній з вершин або граней багатокутника розв’язків.

Ідея методу полягає у тому, що:

· знаходять будь-яку вершину багатогранника розв’язків;

· рухаються вздовж того з ребер, по якому функція зменшується

· (збільшується) до іншої вершини багатогранника розв’язків;

· мінімум (максимум) функції знаходять при потраплянні у вер-

· шину, з якої у всі боки функція зростає (спадає).

Нагадаємо ще раз:

· вектор розв’язків, що задовольняє всім обмеженням, називається планом;

· план, що відповідає вершині багатогранника розв’язків (всі вільні змінні дорівнюють нулю), називається опорним планом;

· опорний план, що відповідає екстремальному значенню цільової функції, називається оптимальним планом.

Опорний план є оптимальним, якщо форма мінімізується (максимізується) і у рядку цільової функції відсутні додатні числа (від’ємні числа), за винятком стовпчика опорного розв’язку (b_i).

Коефіцієнти рядка цільової функції інтерпретують як приріст цільової функції при збільшенні вільної невідомої на одиницю. Приріст додатній, якщо коефіцієнт від’ємний, і навпаки – від’ємний, якщо коефіцієнт додатній.

Стовпчик “j” є вирішальним, коли у цьому стовпчику оцінка коефіцієнта при відомій у цільовій функції найбільша за модулем, тобто |C_j| = max.

Змінну “x_j” у вирішальному рядку знаходять за співвідношенням min{b_i/a_ij} = ᶿ, (a_ij > 0; b_j ≥ 0), яке має назву симплекса, що і дає, у свою чергу, назву методу. Відповідний елемент a_ij має назву ключового елементу, або центру таблиці.

Вільну змінну, яка відповідає вирішальному стовпчику, залучають до базисних змінних, а базисну змінну, яка відповідає мінімальному симплексу, відповідно перетворюють на вільну змінну.

Елементи симплексного рядка нової таблиці дорівнюють елементам старої таблиці, поділеним на “a_ij” – ключовий елемент (центр). Всі інші елементи вирішального стовпчика прирівнюють до “0” (за виключенням ключового, який дорівнює одиниці) шляхом жорданового перетворення; це стосується також цільової функції.

Нескінченна множина оптимальних планів можлива, якщо у рядку цільової функції оптимального плану хоча б одна вільна змінна має нульову оцінку (обмеження паралельне цільовій функції). Оптимальне рішення у цьому випадку вироджене, тобто ранг системи рівнянь-обмежень більший за кількість ненульових координат вектора розв’язків.

Висновки.У даній роботі воказаний процес побудови симплексної моделі, що дозволяє проаналізувати та, при необхідності, зробити корекцію планування процессу виробництва при наявності виробничих ліній, що можуть виготовляти декілька видів продукції. Причому відносно просто можна визначити неможливість виконання запропонованого плану, а також отримати рекомендації щодо модифікації процесу виробництва з використанням двох різних шляхів: збільшення лімітів робочого часу ліній, зменшення обсягів плану випуску продукції.

Список використаних джерел

1. http://ru.wikipedia.org

2. http://matmetod-popova.narod.ru/theme24.htm

3. Математичне програмування - Наконечний С.І.