Быстрый поиск

Контрольная работа: Розв'язок задачі лінійного програмування

Задача 3

Для задачі побудувати двоїсту, розв’язати і за розв’язком знайти розв’язок двоїстої:

Розв’язання:

Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею.

Економічну інтерпретацію кожної з пари задач розглянемо на прикладі виробничої задачі.

Початкова задача:

max z = c1x1 + c2x2 + … + cnxn

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

Розглянемо тепер ту саму задачу з іншої точки зору. Припустимо, що за певних умов доцільно продавати деяку частину чи всі наявні в господарстві ресурси. Необхідно визначити цінність ресурсів. Кожному ресурсу поставимо у відповідність його оцінку . Умовно вважатимемо, що – ціна одиниц -го ресурсу.

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

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

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

Отже в результаті маємо двоїсту задачу:

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

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

Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами:

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

2. Кожній змінній прямої задачі відповідає обмеження двоїсто задачі, причому кількість обмежень дорівнює кількості невідомих прямої задачі.

3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки.

4. Коефіцієнтами при змінних в цільовій функції двоїсто задачі є вільні члени системи обмежень прямої задачі.

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

6. Матриця

що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів в системі обмежень двоїстої задачі

утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками.

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

Якщо цільова функція однієї із задач не обмежена, то інша задача також не має розв’язку.

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

Пряма задача: Двоїста задача:

Для розв’язування задач симплексним методом необхідно привести їх до канонічної форми, для чого в систему обмежень задачі необхідно ввести m невід’ємних змінних, а в систему обмежень – n невід’ємних змінних. Поставимо обмеженням кожної задачі у відповідність змінні двоїстої.

Аналогічно:

Отримали наступну відповідність між змінними спряжених задач:

Основні змінні прямої задачі Додаткові змінні прямої задачі

Додаткові змінні двоїстої задачі Основні змінні двоїсто задачі

Наступна теорема в літературі як правило має назву теореми про доповнюючу нежорсткість.

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

Більш очевидно взаємозв’язок між оптимальними планами прямо та двоїстої задач встановлює наслідок другої теореми двоїстості.

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

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

Побудуємо двоїсту:

Побудуємо симплекс таблиці для прямої задачі:

	1	3	0	0	0
	x1	x2	x3	x4	x5	B	T
x3	4	3	1	0	0	12	4
x4	-1	2	0	1	0	4	2	**
x5	2	-1	0	0	1	4	###
F	-1	-3	0	0	0	0	0
		**

	1	3	0	0	0
	x1	x2	x3	x4	x5	B	T
x3	5,5	0	1	-1,5	0	6	1,09	**
x2	-0,5	1	0	0,5	0	2	###
x5	1,5	0	0	0,5	1	6	4
F	-2,5	0	0	1,5	0	6	0
	**

	1	3	0	0	0
	x1	x2	x3	x4	x5	B	T
x1	1	0	0,18	-0,27	0	1,09	1,09
x2	0	1	0,09	0,36	0	2,55	###
x5	0	0	-0,27	0,91	1	4,36	4
F	0	0	0,45	0,82	0	8,73	0