лекція 3.Симплексні таблиці. Алгоритм симплексного методу.

§ 3 СИМПЛЕКСНИЙ МЕТОД

3.1. Загальна ідея симплекс-метода. Геометрична інтерпретація

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

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

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

Ідея послідовного покращення рішення лягла в основу універсального методу вирішення задач лінійного програмування – симплексного методу або методу послідовного покращення плану.

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

Вперше симплексний метод було запропоновано американським ученим Дж. Данцигом у 1949 р., проте ще 1939 р. ідеї методу розробили російським ученим Л.В. Канторович.

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

Для реалізації симплексного методу – послідовного покращення рішення – необхідно освоїти три основні елементи:

спосіб визначення будь-якого початкового допустимого базового рішення задачі;

правило переходу на краще (точніше, не гіршому) рішенню;

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

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

У літературі досить докладно описуються: знаходження початкового опорного плану (первісного допустимого базисного рішення), теж – методом штучного базису, перебування оптимального опорного плану, вирішення завдань з допомогою симплексних таблиць.

3.2. Алгоритм симплекс-метода.

Розглянемо рішення ЗЛП симплекс-методом і викладемо її стосовно завдання максимізації.

1. За умовою завдання складається її математична модель.

2. Складена модель перетворюється на канонічної форми. При цьому може виділитися базис із початковим опорним планом.

3. Канонічна модель завдання записується у формі симплекс-таблиці так, щоб усі вільні члени були невід'ємними. Якщо початковий опорний план виділено, переходять до пункту 5.

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

4. Знаходять початковий опорний план, виробляючи симплексні перетворення з позитивними роздільними елементами, що відповідають мінімальним симплексним відносинам, і не беручи до уваги знаки елементів
-Рядки. Якщо під час перетворень зустрінеться 0-рядок, всі елементи якої, крім вільного члена, нулі, система обмежувальних рівнянь завдання несовместна. Якщо ж зустрінеться 0-рядок, у якому, крім вільного члена, інших позитивних елементів немає, система обмежувальних рівнянь немає неотрицательных рішень.

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

5. Знайдений початковий опорний план досліджується оптимальність:

а) якщо в
-Рядці немає негативних елементів (крім вільного члена), то план оптимальний. Якщо при цьому немає нульових, то оптимальний план єдиний; якщо ж є хоча б один нульовий, то оптимальних планів безліч;

б) якщо в
-Рядку є хоча б один негативний елемент, якому відповідає стовпець непозитивних елементів, то
;

в) якщо в
-Рядку є хоча б один негативний елемент, а в його стовпці є хоча б один позитивний, то можна перейти до нового опорного плану, Ближчому до оптимального. Для цього зазначений стовпець треба призначити вирішальним, за мінімальним симплексним відношенням знайти роздільну здатність і виконати симплексне перетворення. Отриманий опорний план знову дослідити оптимальність. Описаний процес повторюється до отримання раціонального плану або до встановлення нерозв'язності завдання.

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

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

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

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

2) складають відношення елементів стовпця вільних членів до відповідних елементів роздільного стовпця, що мають однакові знаки (симплексні відносини);

3) із симплексних відносин вибирають найменше. Воно і визначить роздільну здатність. Нехай нею буде, наприклад, р-Рядок;

4) на перетині дозвільних стовпця та рядки знаходять роздільний елемент. Якщо роздільною здатністю виявився елемент -Рядки, то після симплексного перетворення вільний член цього рядка стане позитивним. В іншому випадку на наступному кроці знову звертаються до -Рядці. Якщо завдання можна розв'язати, то через кілька кроків у стовпці вільних членів не залишиться негативних елементів.

Якщо форму ЗЛП одягнена деяка реальна виробнича ситуація, то додаткові змінні, які доводиться вводити в модель у процесі перетворення її до канонічної формі, завжди мають певний економічний сенс.

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

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

Вихідні дані завдання на симплекс-метод

Підприємство випускає 4 види виробів, опрацьовуючи їх на 3-х верстатах.

Норми часу (хв./шт.) на обробку виробів на верстатах, задані матрицею A:

Фонд часу роботи верстатів (хв.) заданий у матриці B:

Прибуток від продажу кожної одиниці виробу (руб./шт.) заданий матрицею C:

Мета виробничого завдання

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

Розв'язання задачі табличним симплекс-методом

(1) Позначимо X1, X2, X3, X4 заплановану кількість виробів кожного виду. Тоді шуканий план: ( X1, X2, X3, X4)

(2) Запишемо обмеження плану як системи рівнянь:

(3) Тоді цільовий прибуток:

Тобто прибуток від виконання виробничого плану має бути максимальним.

(4) Для вирішення завдання на умовний екстремум, замінимо систему нерівностей системою лінійних рівняньшляхом введення до неї додаткових невід'ємних змінних ( X5, X6, X7).

(5) Приймемо наступний опорний план:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Занесемо дані в симплекс-таблицю:

В останній рядок заносимо коефіцієнти при цільовій функції та саме її значення з зворотним знаком;

(7) Вибираємо у останньому рядку найбільше (за модулем) від'ємне число.

Обчислимо b = Н / Елементи_вибраного_стовпця

Серед обчислених значень b вибираємо найменше.

Перетин вибраних стовпчиків і рядків дасть нам роздільну здатність. Змінюємо базис на змінну відповідну роздільну здатність ( X5 на X1).

• Сам роздільний елемент звертається до 1.
• Для елементів роздільної здатності – a ij (*) = a ij / РЕ ( тобто кожен елемент ділимо на значення роздільної здатності елемента і отримуємо нові дані).
• Для елементів роздільного стовпця – вони просто обнуляються.
• Інші елементи таблиці перераховуємо за правилом прямокутника.

a ij (*) = a ij - (A * B / РЕ)

Як бачите, ми беремо поточну комірку, що перераховується, і комірку з роздільним елементом. Вони утворюють протилежні кути прямокутника. Далі перемножуємо значення із осередків 2-х інших кутів цього прямокутника. Цей твір ( A * B) ділимо на роздільний елемент ( РЕ). І віднімаємо з поточного перерахованого осередку ( a ij) те, що вийшло. Отримуємо нове значення - a ij (*).

(9) Знову перевіряємо останній рядок ( c) на наявність негативних чисел. Якщо їх немає – оптимальний план знайдено, переходимо до останньому етапірозв'язання задачі. Якщо є – план ще не оптимальний, і симплекс-таблицю знову потрібно перерахувати.

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

(10) Так як в останньому рядку немає негативних елементів, це означає, що ми знайдено оптимальний план виробництва! А саме: випускати ми будемо ті вироби, які перейшли до колонки «Базис» – X1 та X2. Прибуток від виробництва кожної одиниці продукції нам відомий ( матриця C). Залишилося перемножити знайдені обсяги випуску виробів 1 та 2 з прибутком на 1 шт., отримаємо підсумкову ( максимальну! ) прибуток при цьому плані виробництва.

ВІДПОВІДЬ:

X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.

P = 48 * 32 + 33 * 20 = 2196 руб.

Галяутдінов Р.Р.

© Копіювання матеріалу допустиме лише при вказівці прямого гіперпосилання на

. Алгоритм симплекс-методу

Приклад 5.1.Розв'язати таке завдання лінійного програмування симплекс-методом:

Рішення:

I ітерація:

х3, х4, х5, х6 х1,х2. Висловимо базисні змінні через вільні:

Наведемо цільову функцію наступного виду:

На основі отриманого завдання сформуємо вихідну симплекс-таблицю:

Таблиця 5.3

Вихідна симплекс-таблиця

				Оціночні відносини

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

3 етап: перевірка сумісності системи обмежень ЗЛП.

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

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

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

6 етап: перевірка оптимальності.

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

Так як знайдене базисне рішення допустиме, то пошук колонки будемо проводити за наступною схемою: визначаємо колонки з негативними елементами в рядку цільової функції (крім колонки вільних чисел). Відповідно до таблиці 5.3 таких колонок дві: колонка « х1і колонка « х2». З таких колонок вибирається та, що містить найменший елемент у рядку цільової функції. Вона і буде вирішальною. Колонка « х2» містить найменший елемент (–3) у порівнянні з колонкою « х1

Для визначення роздільної здатності знаходимо позитивні оціночні відношення вільних чисел до елементів роздільної здатності колонки, рядок, якій відповідає найменше позитивне оцінне відношення, приймається як дозволений.

Таблиця 5.4

Вихідна симплекс-таблиця

У таблиці 5.4 найменше позитивне оцінне відношення відповідає рядку « х5», отже, вона буде вирішальною.

Елемент, розташований на перетин роздільної колонки і рядка, приймається як роздільна здатність. У нашому прикладі – це елемент, який розташований на перетині рядка. х5і колонки « х2».

Дозволяючий елемент показує одну базисну і одну вільну змінні, які необхідно поміняти місцями в симплекс-таблиці, для переходу до нового «поліпшеного» базового рішення. У даному випадкуце змінні х5і х2, у новій симплекс-таблиці (таблиці 5.5) їх міняємо місцями.

9.1. Перетворення роздільної здатності елемента.

Роздільний елемент таблиці 5.4 перетворюється таким чином:

Отриманий результат вписуємо до аналогічної клітини таблиці 5.5.

9.2. Перетворення роздільної здатності.

Елементи роздільної здатності таблиці 5.4 ділимо на роздільний елемент даної симплекс-таблиці, результати вписуються в аналогічні осередки нової симплекс-таблиці (таблиці 5.5). Перетворення елементів роздільної здатності наведено в таблиці 5.5.

9.3. Перетворення роздільної здатності колонки.

Елементи роздільної здатності колонки таблиці 5.4 ділимо на роздільний елемент даної симплекс-таблиці, а результат береться зі зворотним знаком. Отримані результати вписуються в аналогічні осередки нової симплекс-таблиці (таблиці 5.5). Перетворення елементів роздільної здатності колонки наведені в таблиці 5.5.

9.4. Перетворення інших елементів симплекс-таблиці.

Перетворення інших елементів симплекс-таблиці (тобто елементів не розміщених у роздільній здатності і колонці) здійснюється за правилом «прямокутника».

Наприклад, розглянемо перетворення елемента, розташованого на перетині рядка « х3» та колонки «», умовно позначимо його « х3». У таблиці 5.4 подумки викреслюємо прямокутник, одна вершина якого розташовується в клітці, значення якої перетворимо (тобто в клітці « х3»), а інша (діагональна вершина) – у клітці з роздільним елементом. Дві інші вершини (другий діагоналі) визначаються однозначно. Тоді перетворене значення клітини х3» дорівнюватиме колишньому значенню даної клітини мінус дріб, у знаменнику якої роздільний елемент (з таблиці 5.4), а в чисельнику добуток двох інших невикористаних вершин, тобто:

« х3»: .

Аналогічно перетворюються значення інших клітин:

« х3 х1»: ;

« х4»: ;

« х4 х1»: ;

« х6»: ;

« х6 х1»: ;

«»: ;

« х1»: .

В результаті даних перетворень отримали нову симплекс-таблицю(Таблиця 5.5).

II ітерація:

1 етап: складання симплекс-таблиці.

Таблиця 5.5

Симплекс-таблицяII ітерації

				Оціночні відносини

2 етап: визначення базового рішення.

В результаті проведених симплекс-перетворень отримали нове базове рішення (таблиця 5.5):

Як видно, при даному базисному рішенні значення цільової функції = 15, що більше, ніж при попередньому базисному рішенні.

Не сумісність системи обмежень відповідно до ознаки 1 у таблиці 5.5 не виявлено.

4 етап: перевірка обмеженості цільової функції.

Необмеженість цільової функції відповідно до ознаки 2 у таблиці 5.5 не виявлено.

5 етап: перевірка допустимості знайденого базисного рішення.

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

8 етап: визначення роздільної здатності елемента.

8.1. Визначення роздільної здатності колонки.

Знайдене базисне рішення припустиме, визначаємо колонки з негативними елементами рядку цільової функції (крім колонки вільних чисел). Згідно з таблицею 5.5, такою колонкою є лише одна колонка: « х1». Отже, її приймаємо як дозволену.

8.2. Визначення роздільної здатності рядка.

Згідно з отриманими значеннями позитивних оціночних відносин у таблиці 5.6, мінімальним є відношення, що відповідає рядку « х3». Отже, її приймаємо як дозволену.

Таблиця 5.6

Симплекс-таблицяII ітерації

				Оціночні відносини
				3/1 = 3 - min

9 етап: перетворення симплекс-таблиці.

Перетворення симплекс-таблиці (таблиці 5.6) виконуються аналогічно, як і попередньої ітерації. Результати перетворень елементів симплекс-таблиці наведено у таблиці 5.7.

III ітерація

За результатами симплекс-перетворень попередньої ітерації складаємо нову симплекс-таблицю:

Таблиця 5.7

Симплекс-таблицяIII ітерації

				Оціночні відносини

2 етап: визначення базового рішення.

В результаті проведених симплекс-перетворень отримали нове базове рішення (таблиця 5.7):

3 етап: перевірка сумісності системи обмежень.

Не сумісність системи обмежень відповідно до ознаки 1 у таблиці 5.7 не виявлено.

4 етап: перевірка обмеженості цільової функції.

Необмеженість цільової функції відповідно до ознаки 2 у таблиці 5.7 не виявлено.

5 етап: перевірка допустимості знайденого базисного рішення.

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

6 етап: перевірка оптимальності знайденого базового рішення.

Знайдене базисне рішення відповідно до ознаки 4 не оптимальне, оскільки у рядку цільової функції симплекс-таблиці (таблиця 5.7) міститься негативний елемент: –3 (вільне число цього рядка при розгляді даної ознаки не враховується). Отже, переходимо до 8 етапу.

8 етап: визначення роздільної здатності елемента.

8.1. Визначення роздільної здатності колонки.

Знайдене базисне рішення припустиме, визначаємо колонки з негативними елементами рядку цільової функції (крім колонки вільних чисел). Згідно з таблицею 5.7, такою колонкою є лише одна колонка: « х5». Отже, її приймаємо як дозволену.

8.2. Визначення роздільної здатності рядка.

Згідно з отриманими значеннями позитивних оціночних відносин у таблиці 5.8, мінімальним є відношення, що відповідає рядку « х4». Отже, її приймаємо як дозволену.

Таблиця 5.8

Симплекс-таблицяIII ітерації

				Оціночні відносини
				5/5 = 1 - min

9 етап: перетворення симплекс-таблиці.

Перетворення симплекс-таблиці (таблиці 5.8) виконуються аналогічно, як і попередньої ітерації. Результати перетворень елементів симплекс-таблиці наведено у таблиці 5.9.

IV ітерація

1 етап: побудова нової симплекс-таблиці.

За результатами симплекс-перетворень попередньої ітерації складаємо нову симплекс-таблицю:

Таблиця 5.9

Симплекс-таблицяIV ітерації

				Оціночні відносини
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

2 етап: визначення базового рішення.

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

3 етап: перевірка сумісності системи обмежень.

Не сумісність системи обмежень відповідно до ознаки 1 у таблиці 5.9 не виявлено.

4 етап: перевірка обмеженості цільової функції.

Необмеженість цільової функції відповідно до ознаки 2 у таблиці 5.9 не виявлено.

5 етап: перевірка допустимості знайденого базисного рішення.

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

6 етап: перевірка оптимальності знайденого базового рішення.

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

7 етап: перевірка альтернативності рішення.

Знайдене рішення є єдиним, оскільки у рядку цільової функції (таблиця 5.9) немає нульових елементів(Вільне число цього рядка при розгляді даної ознаки не враховується).

Відповідь: оптимальне значення цільової функції розглянутої задачі =24, яке досягається при.

Приклад 5.2.Вирішити наведене вище завдання лінійного програмування за умови, що цільова функція мінімізується:

Рішення:

I ітерація:

1 етап: формування вихідної симплекс-таблиці.

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

В отриманій системі рівнянь приймемо як дозволені (базисні) змінні х3, х4, х5, х6, тоді вільними змінними будуть х1,х2. Висловимо базисні змінні через вільні.

Для реалізації трьох груп товарів комерційне підприємствомає в своєму розпорядженні три види обмежених матеріально-грошових ресурсів у кількості b 1 = 240, b 2 = 200, b 3 = 160 одиниць. У цьому на продаж 1 групи товарів на 1 тис. крб. товарообігу витрачається ресурсу першого виду у кількості a 11 = 2 одиниці, ресурсу другого виду у кількості a 21 = 4 одиниці, ресурсу третього виду у кількості a 31 = 4 одиниці. Для продажу 2 та 3 груп товарів на 1 тис. руб. товарообігу витрачається відповідно ресурсу першого виду в кількості a 12 = 3, a 13 = 6 одиниці, ресурсу другого виду в кількості a 22 = 2, a 23 = 4 одиниці, ресурсу третього виду в кількості a 32 = 6, a 33 = 8 одиниць . Прибуток від трьох груп товарів на 1 тис. крб. товарообігу становить відповідно c1 = 4, c2 = 5, c3 = 4 (тис. руб.). Визначити плановий обсяг та структуру товарообігу так, щоб прибуток торговельного підприємствабула максимальною.

До прямого завдання планування товарообігу, розв'язуваний симплекс методом, скласти подвійне завданнялінійного програмування.
Встановити пов'язані пари зміннихпрямий і двоїстої задачі.
Згідно з парами змінних з вирішення прямого завдання отримати вирішення двоїстої задачі, в якій проводиться оцінка ресурсів, Витрачених на продаж товарів.

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

Нехай x 1 , x 2 , x 3 - кількість реалізованих товарів, у тис. руб., 1, 2, 3-ї груп, відповідно. Тоді математична модельзавдання має вигляд:

F = 4 · x 1 + 5 · x 2 + 4 · x 3 -> max

0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Вирішуємо симплекс методом.

Вводимо додаткові змінні x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, щоб нерівності перетворити на рівність.

Як базис візьмемо x 4 = 240; x 5 = 200; x6 = 160.

Дані заносимо в симплекс таблицю

Симплекс таблиця №1

Цільова функція:

0 · 240 + 0 · 200 + 0 · 160 = 0

Обчислюємо оцінки за формулою:

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

Оскільки є негативні оцінки, то план не є оптимальним. Найнижча оцінка:

Вводимо змінну x 2 в базис.

Визначаємо змінну, яка виходить із базису. Для цього знаходимо найменше невід'ємне відношення для шпальти x 2 .

= 26.667

Найменше невід'ємне: Q3 = 26.667. Виводимо змінну x 6 з базису

3-й рядок ділимо на 6.
З 1-го рядка віднімаємо 3-й рядок, помножений на 3
З 2-го рядка віднімаємо 3-й рядок, помножений на 2

Обчислюємо:

Отримуємо нову таблицю:

Симплекс таблиця №2

Цільова функція:

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Обчислюємо оцінки за формулою:

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Оскільки є негативна оцінка Δ 1 = - 2/3, то план не є оптимальним.

Вводимо змінну x 1 у базис.

Визначаємо змінну, яка виходить із базису. Для цього знаходимо найменше невід'ємне відношення для шпальти x 1 .

Найменше невід'ємне: Q 3 = 40. Виводимо змінну x 2 з базису

3-й рядок ділимо на 2/3.
З 2-го рядка віднімаємо 3-й рядок, помножений на 8/3

Обчислюємо:

Отримуємо нову таблицю:

Симплекс таблиця №3

Цільова функція:

0 · 160 + 0 · 40 + 4 · 40 = 160

Обчислюємо оцінки за формулою:

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Оскільки негативних оцінок немає, то план є оптимальним.

Рішення завдання:

Відповідь

x 1 = 40; x 2 = 0; x3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

Тобто необхідно реалізувати товар першого виду обсягом 40 тис. крб. Товар 2-го та 3-го видів реалізовувати не треба. При цьому максимальний прибутокскладе Fmax = 160 тис. руб.

Розв'язання двоїстої задачі

Подвійне завдання має вигляд:

Z = 240 · y 1 + 200 · y 2 + 160 · y 3 -> min

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3> = 0)))(~)">!}

Вводимо додаткові змінні y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, щоб нерівності перетворити на рівності.

Сполучені пари змінних прямої та двоїстої задач мають вигляд:

З останньої симплекс таблиці № 3 прямої задачі знаходимо рішення двоїстої задачі:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

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

Виходячи з цього поділу, умову задачі можна перефразувати таким чином: екстремум цільової функції Z(X) = f(x1, x2, … ,xn) → max (min) та відповідні змінні, якщо відомо, що вони задовольняють системі обмежень: Φ_i ( x1, x2, …, xn) = 0 при i = 1, 2, …, k;

Систему обмежень необхідно призвести до канонічного виду, тобто. до системи лінійних рівнянь, де кількість змінних більше числарівнянь (m>k). У цій системі обов'язково знайдуться змінні, які можна виразити через інші змінні, а якщо це не так, їх можна ввести штучно. У цьому випадку перші називаються базисом або штучним базисом, а другі – вільними.

Зручніше розглянути симплекс-метод на конкретному прикладі. Нехай дана лінійна функція f(x) = 6x1 + 5x2 + 9x3 і система обмежень: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; 4x1 + 3x3 ≤ 18. максимальне значенняфункції f(x).

Рішення На першому етапі задайте початкове (опорне) рішення системи рівнянь абсолютно довільним чином, яке при цьому має задовольняти цю систему обмежень. У разі потрібно введення штучного , тобто. базисних змінних x4, x5 і x6 наступним чином: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20; 4x1 + 3x3 + x6 = 18.

Як бачите, нерівності перетворилися на рівності завдяки доданим змінні x4, x5, x6, які є невід'ємними величинами. Таким чином, ви привели систему до канонічного вигляду. Змінна x4 входить у перше рівняння з коефіцієнтом 1, а два – з коефіцієнтом 0, те саме справедливо для змінних x5, x6 і відповідних рівнянь, що відповідає визначенню базису.

Ви підготували систему та знайшли початкове опорне рішення – X0 = (0, 0, 0, 25, 20, 18). Тепер подайте коефіцієнти змінних та вільні члени рівнянь (цифри праворуч від знака «=») у вигляді таблиці для оптимізації подальших обчислень (див. рис).

Суть симплекс-метода у тому, щоб привести цю таблицю до такого виду, у якому цифри у рядку L будуть неотрицательными величинами. Якщо ж з'ясується, що це неможливо, то система взагалі не має оптимального рішення. Для початку виберіть самий мінімальний елементцього рядка, це -9. Цифра стоїть у третьому стовпці. Перетворіть відповідну змінну x3 на базову. Для цього розділіть рядок на 3, щоб у комірці вийшло 1.

Тепер потрібно, щоб комірки і звернулися в 0. Для цього відніміть від відповідних цифр третього рядка, на 3. Від елементів другого рядка - елементи третього, помножені на 2. І, нарешті, від елементів рядка L - помножені на (-9). Ви одержали друге опорне рішення: f(x) = L = 54 при x1 = (0, 0, 6, 7, 8, 0).