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

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

Допустимим рішенням задачі ЛП назвемо всяке рішення системи обмежень (4.3), що задовольняє умовам нейтрально

У виробничих завданнях, математичні моделі яких досліджуються методами ЛП, завжди на змінні Xj (j =) накладається вимога не заперечності змінних.

Симплекс - метод заснований на тому, що якщо в матриці обмежень є m рядків і вони лінійно незалежні, то існує набір з m стовпців, які називаються базисними, які також лінійно незалежні. Сукупність значень змінних, відповідних базисним стовпцями, називається базисним рішенням (опорним рішенням, опорним планом). Якщо в системі обмежень - рівнянь міститься n змінних Xj (j =) і ранг її дорівнює m, то в симплексному методі на кожній ітерації відшукуються значення m базисних змінних, які відповідають m лінійним обмеженням, а решта n - m змінних називаються вільними і покладаються рівними нулю .

Симплексний метод дозволяє перехід від одного базисного рішення до іншого за допомогою заміни за кожну ітерацію одного стовпчика в базисі на один небазисной стовпець до тих пір, поки не буде знайдено допустиме рішення, яке задовольняє max (min) цільової функції. Це рішення називається оптимальним.

Геометрична інтерпретація симплекс - методу: якщо умови задачі ЛП несуперечливі, то область її допустимих рішень утворює опуклий багатогранник в I вимірному просторі. При цьому оптимальне рішення, якщо воно існує, обов'язково досягається в деякій вершині многогранника. Щоб знайти рішення задачі ЛП, досить перебрати лише плани, що відповідають вершинам багатогранника допустимих рішень (опорні, базисні плани).

З - метод дозволяє здійснити упорядкований перебір вершин багатогранника. Після визначення однієї з вершин цей метод допомагає встановити, чи є знайдений план оптимальним, т. Е. Чи досягнуто в цій вершині екстремум цільової функції. Якщо план неоптимальний, то проводиться перехід до такої сусідній вершині багатогранника, яка забезпечує не менше (не бiльше) значення цільової функції.

Робочим апаратом С - методу є сімплексні таблиці. Послідовно переходячи від однієї таблиці до іншої, в результаті отримаємо оптимальне рішення.

Щоб вирішити задачу табличним симплекс-методом, необхідно представити її в канонічній формі, т. Е. В системі обмежень повинні бути знаки «дорівнює», праві частини невід'ємними числами і на всі змінні накладено вимога не заперечності.

Якщо в системі обмежень містяться нерівності, то кожне нерівність потрібно перетворити в рівняння шляхом введення додаткових або балансових змінних. Вони вводяться по одній змінній в кожне нерівність зі знаком «+», якщо нерівність має знак £, і зі знаком «-», якщо нерівність має знак ³. Зазвичай нумерація балансових змінних продовжує нумерації основних змінних задачі. Ці ж змінні з нульовими коефіцієнтами вводяться в цільову функцію.

Вихідну систему рівнянь корисно записати у векторній формі:

Для побудови 1 симплексной таблиці з векторів j потрібно вибрати кілька векторів, компоненти яких утворюють одиничну матрицю Е.

Якщо немає таких векторів, то можна використовувати один з наступних способів:

1. Провести m перетворень за схемою Жордана - Гаусса системи обмежень (4.3) для дозволу щодо m будь-яких змінних. В результаті отримаємо в матриці системи (4.3) m базисних вектор - стовпців j. тобто векторів, у яких одна координата дорівнює 1, а інші - нулю, причому одиниці знаходяться в різних рядках матриці. Відповідні базисні змінні записують в стовпець баз першої симплексной таблиці.

2. Якщо вихідна система обмежень задачі ЛП містить нерівності зі знаком £, то при введенні додаткових невід'ємних змінних для перетворення нерівностей в рівняння ми відразу отримуємо ті базисні вектори, які і утворюють перший базис в симплексній таблиці.

3. Якщо у вихідній системі обмежень нерівностей є знаки ³, то балансові змінні вводяться в ліву частину нерівності зі знаком «-». Відповідний вектор - стовпець такої змінної матиме наступні координати:

У цьому випадку буде бракувати векторів, координати яких можуть утворити одиничну матрицю Е для першого базису. У кожне таке нерівність разом з балансової змінної вводиться ще одна змінна (штучна): Х # 945; 1. Х # 945; 2.

На ці змінні теж накладається вимога не заперечності: Х # 945; 1 ³ 0, Х # 945; 2 ³ 0.

У цільову функцію в цьому випадку вводиться додаткове доданок виду: ± М (Х # 945; 1 + Х # 945; 2 +. + Х # 945; m), де знак «+» використовується в задачах на мінімум (F®min) , знак «-» в задачах на максимум (F®max). М ³0 - дуже велике число. У розрахунках на ЕОМ зазвичай приймають М = 10 17.

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

Послідовність розрахунків по сімплексному методу розглянемо на наступному прикладі.

Підприємство має в своєму розпорядженні ресурсами сировини, устаткуванням і робочою силою, необхідними для виробництва будь-якого з чотирьох видів користуються попитом товарів.

Вихідна інформація задачі

Вид товару Вид ресурсу

Відомі витрати ресурсів на виготовлення одиниці кожного виду товару, запаси ресурсів, а також величина прибутку, яку підприємство отримує за одиницю товару (табл. 4.1.).

Визначити оптимальний асортимент товарів, що максимізує прибуток і оцінки всіх чотирьох видів ресурсів щодо оптимального асортименту.

Введемо змінні х1. х2. х3. х4. - відповідно кількість виробленого товару виду А, Б, В, Г, тоді математична модель запишеться у вигляді

Для вирішення завдання симплекс - методом перетворимо нерівності в рівняння, отримаємо:

За економічним змістом змінні х5. х6. х7. х8 позначають неиспользуемое кількість відповідного ресурсу кожного виду, тому в цільову функцію ці додаткові змінні входять з нульовими коефіцієнтами.

Першу симплексну таблицю заповнюють наступним чином:

1. У верхньому рядку таблиці виписують коефіцієнти при невідомих змінних цільової функції вихідної задачі.

2. У стовпці 1. 2. n виписують коефіцієнти при змінних х1. х2. хn в рівняннях системи обмежень.

3. У стовпець записують праві частини рівнянь системи обмежень.

4. У стовпець баз вписують ті вектори, координати яких утворюють одиничну матрицю Е (базис.).

5. У стовпець баз вписують коефіцієнти при базисних змінних з цільової функції.

6. Нижня рядок таблиці Zj - Cj = Jбаз # 8729; j - Cj називається індексного рядком або рядком оцінок і служить для перевірки отриманого в черговий таблиці рішення на оптимальність.

Перший план симплексной таблиці - перший опорний план завдання:

Це відповідає тому, що нічого не виробляється, ресурси не використовуються, прибуток - цільова функція дорівнює нулю і не основні змінні приймають свої граничні значення. З геометричної точки зору отримані координати вершини багатогранника (0, 0, 0, 0, 360, 400, 134, 96).

Рішення завдання полягає в послідовному введенні в план основних змінних, по одній на кожному етапі розрахунку, поки не буде отримано оптимальне рішення.

Спочатку визначається, яка саме з чотирьох змінних вводиться в базис. Так як завдання вирішується на максимум, то доцільніше розпочати з більш прибуткового товару. Найприбутковішим є товар В, в індексному рядку симплексній таблиці йому відповідає найбільше по абсолютній величині число (50).

Визначимо, в якій кількості передбачено випуск товару В, це залежить від обсягу ресурсів і нормативів їх витрат. Сировини 1 виду досить на 180 одиниць товару В (360 кг. 2 кг). Сировини 2 види - на 20 одиниць товару В (400. 20). Фонду часу обладнання вистачить на 16 (134. 8) одиниць, робочої сили - 8 (96. 12) одиниць товару В. Очевидно, що більше 8 одиниць товару В виготовити не вдасться. Тому змінна х3 в плані дорівнює 8 і вводиться на місце змінної х8. яка виключається з базису і приймає нульове значення. Підкреслимо число 12, що знаходиться на перетині стовпця 3 введеної перемінної х3 і рядки х8 виведеної змінної.

Це число називається що дозволяє, ключовим, напрямних елементом.

Розглянемо другий етап розрахунку таблиці 4. 2. Перш за все, розраховується рядок введеної перемінної, зазначена в таблиці стрілкою. Цей рядок виходить з рядка х8 початкового варіанту шляхом ділення всіх елементів на направляючий елемент, так як в цьому відношенні (1. 12) змінна х3 заміщає змінну х8. У стовпці баз проставляється прибуток за одиницю товару В (50).

Після розрахунку рядки х3 перераховується стовпець ресурсів.

Сировина 1 виду зменшиться, спочатку воно становило 360 кг, на кожну одиницю сировини товару В витрачається 2 кг. всього виробляється (96. 12) 8 одиниць товару В, отже, залишається невикористане сировину 1 виду складе 344 кг, тобто 360 - 96/12 # 8729; 2 = 344.

Аналогічно: 400 - 96/12 # 8729; 20 = 240 кг - невикористане сировину 2 види, 134 - 96/12 # 8729; 8 = 70 станко - ч. - залишається невикористаним фонд часу обладнання.

Після стовпчика ресурсів перераховуються інші стовпці симплексной таблиці.

Схема перерахунку (правило Жордана - Гаусса)

j - стовпець s- стовпець

Елемент аij після перерахунку за правилом Жордана - Гаусса перетворюється в елемент а'ij. де.

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

Рішення завдання симплексним методом

Елементи в індексному рядку можна розраховувати або безпосередньо за формулою Jбаз # 8729; j - Сj. або за правилом Жордана - Гаусса. Одне з правил слід використовувати для розрахунку, інше - в якості контролю. В результаті отримаємо другий опорний план: х1 = 0, х2 = 0, х3 = 8. х4 = 0, х5 = 344, х6 = 240, х7 = 70, х8 = 0 і значення прибутку - 400 д. Од. З геометричної точки зору здійснений перехід в вершину багатогранника з координатами (0,0,8,0,344,240,70,0). Потім необхідно перевірити даний план на оптимальність. Для цього проглядається індексна рядок і, якщо вона містить негативні елементи, то план можна поліпшити. Як бачимо, вона містить два від'ємних числа, які вказують що прибуток може бути збільшена введенням в базис змінної х1 або х4. Мінлива х4 вводиться в базис, так як їй відповідає найбільше по абсолютній величині негативне число - 27,5.

Якщо по індексному рядку визначено ключовий стовпець j. в якому всі елементи негативні, то задача ЛП не має рішення.

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

х1 = 0, х2 = 0, х3 = 6,25, х4 = 7, х5 = 319,5, х6 = 65, х7 = 0, х8 = 0, тобто в даних умовах виробництва можна отримати прибутку більш 592,5 д. од. При цьому випуск товару В повинен становити 6,25 одиниці і товару Г- 7 одиниць, залишок сировини першого виду 319,5 кг і другого виду - 65 кг.