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

ДОПУСТИМИЙ РОЗВЯЗОК

1. Беремо будь-який від’ємний елемент у першому стовпчику таблиці початкової (за винятком першого). Якщо такого елемента немає, переходимо до виконання пункту ІV.

Нехай таким елементом є b_m < 0.

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

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

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

5. Усі елементи базового рядка ділимо на цей елемент, але обчислень ніяких не виконуємо; виписуємо з таблиці початкової.

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

7. Усі інші елементи табл. нової утворюються як результат додавання відповідного елемента табл. початкової та добутку відповідного елемента базового стовпчика табл. Нової на чисельник відповідного елемента базового рядка тієї самої таблиці.

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

9. Процедуру повторюємо доти, доки в першому стовпчику останньої таблиці (за винятком першого, знак якого не враховується) не зникнуть від’ємні елементи.

ОПТИМАЛЬНИЙ РОЗВЯЗОК ЗЛП

1. Знаходимо серед елементів першого рядка (крім першого елемента) додатні числа. Якщо таких елементів немає, переходимо до виконання п. V.

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

ВІДПОВІДЬ Усі вільні змінні (змінні, які стоять у верхній частині останньої симплекс-таблиці) покладаємо рівними нулю. Усі базові змінні (змінні, які стоять у лівій частині таблиці) покладаємо відповідно числам, які стоять у першому стовпчику останньої симплекс-таблиці. означає, що змінна, яка стоїть у першому рядку таблиці (після ) покладається рівною першому числу цього рядка першого стовпчика, друга змінна – другому числу першого стовпчика і т.д. покладається рівним , де дорівнює числу, яке стоїть у першій верхній лівій клітинці фінальної симплекс-таблиці.

10. Критерій оптимальності,розв’язності.

Опорний план , за якого цільова функція max(min) Z = c ₁ x ₁ +……c _n x _n досягає масимального (чи мінімального) значення, називається оптимальним розв’язком (планом) задачі лінійного програмування.

12-13. Теореми двоїстості

Перша теорема двоїстості. Якщо одна з пари спряжених задач має оптимальний план,то й друга задача також має розв’язок причому для оптимальних розв’язків значення цільових функцій обох задач збігаються. Тобто maxF=minZ якщо цільова функція однієї із задач необмежена,то спряжена задача також немає розвязку

Економічний зміст першої теореми двоїстості. Максимальний прибуток(Fmax)підприємство отримує за умови виробництва продукції згідно з оптимальним планом Х*=(х1*,х2*,..,Хп*),однак таку саму суму грошей(Zmin=Zmax)воно може мати,реалізувавши ресурси за оптимальними цінами Y*=(y1*.y2*,..,ym*)ЗА УМОВ використання інших планів Хнедорівнює Хоптим,Унедорів Уоптим на підставі основної нерівності теорії двоїст задачі можна стверджувати,що прибутки від реалізації продукції завжди менші,ніж витрати на її виробництво.

Друга теорема двоїстості для симетричних задач. Для того, щоб плани X* та Z* відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості:

.

Економічний зміст другої теореми двоїстості стосовно оптимального плану Х* прямої задачі. Якщо для виготовлення всієї продукції в обсязі, що визначається оптимальним планом Х*, витрати одного і-го ресурсу строго менші, ніж його загальний обсяг b_i, то відповідна оцінка такого ресурсу (компонента оптимального плану двоїстої задачі) буде дорівнювати нулю, тобто такий ресурс за даних умов для виробництва не є «цінним».

Якщо ж витрати ресурсу дорівнюють його наявному обсягові b_i, тобто його використано повністю, то він є «цінним» для виробництва, і його оцінка буде строго більшою від нуля.

Економічне тлумачення другої теореми двоїстості щодо оптимального плану Y* двоїстої задачі: у разі, коли деяке j-те обмеження виконується як нерівність, тобто всі витрати на виробництво одиниці j-го виду продукції перевищують її ціну сj, виробництво такого виду продукції є недоцільним, і в оптимальному плані прямої задачі обсяг такої продукції дорівнює нулю.

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