Главная->ЕММ->Содержание->4. Двоїста задача та аналіз лінійних моделей оптимізаційних задач . Приклад 5.

МЕТОДИЧНІ ВКАЗІВКИ до виконання розрахункової роботи з навчальної дисципліни “Економіко-математичні методи та моделі оптимізаційні методи та моделі”

4. Двоїста задача та аналіз лінійних моделей оптимізаційних задач . Приклад 5.

На виготовлення двох видів продукції П1 та П2 витрачаються три види ресурсів А1, А2, А3. Запаси ресурсів, норми їх витрат і прибуток від реалізації одиниці продукції задано в таблиці 8. За допомогою симплексного методу знайти такий план виробництва, який би забезпечував отримання найбільшого прибутку.

Таблиця 8

Вихідні дані задачі

Витрати ресурсі на 1-цю продукції	Наявність ресурсів	Прибуток на 1-цю продукції
А1	А2	А3	А1	А2	А3	П1	П2
2; 6	1; 3	6; 1	14	30	12	10	8

Для зручності побудови системи рівнянь запишемо наступну таблицю 9

Таблиця 9

Розподіл ресурсів на виготовлення продукції

Показник	П1	П3	Кількість
А1	2	6	14
А2	1	3	30
А3	6	1	12
Прибуток	10	8	Х

Позначимо за – кількість товару П1, – кількість товару П2.

1. Запишемо модель прямої задачі:

2. Знаходимо канонічну форму запису:

Опорний розв’язок (план) задачі: (0; 0; 14; 30; 12).

Подальшу перевірку опорного плану на оптимальність здійснюють за допомогою симплекс-таблиці (табл. 10).

Таблиця 10

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

Базисні змінні БЗ	Коефіцієнти при базисних змінних Сб	Значення БЗ в опорному розв’язку Ао						=
10	8	0	0	0
	0	14	2	6	1	0	0	14/2=7
	0	30	1	3	0	1	0	30/1=30
	0	12	[6]	1	0	0	1	12/6=2
Значення цільової функції при даному опорному розв’язку	0	-10	-8	0	0	0	X
Дана задача на пошук цільової функції, тому критерієм оптимальності розв’язку є відсутність від’ємних оцінок змінних. Обирається найбільше по модулю від’ємне значення серед оцінок змінних, якщо задача на -10. Розраховуємо значення симплексних відношень =: Визначаємо замість якої змінної введемо змінну , для цього числа в стовпчику Ао поділимо на додатні числа, що стоять в стовпчику : обирається найменше серед значень 12/6=2, відповідно вводиться нова базисна змінна на місце . Для зручності робимо одиницю на місці 6, тобто ділимо весь рядок на 6. Методом Жордана-Гаусса розраховуємо значення таблиці.
	0	14	2	6	1	0	0
	0	30	1	3	0	1	0
	0	2	[1]	1/6	0	0	1/6	Весь рядок/6
	0	-10	-8	0	0	0
	0	10	0	[17/3]	1	0	-1/3	30/17=1,8
	0	28	0	17/6	0	1	-1/6	168/17=10
	10	2	1	1/6	0	0	1/6	12
	20	0	-19/3	0	0	5/3	X
Від’ємна оцінка є =–19/3, необхідно зробити перетворення, помножити весь рядок на 3/17.
	0	30/17	0	[1]	3/17	0	-1/17
	0	28	0	17/6	0	1	-1/6
	10	2	1	1/6	0	0	1/6
	20	0	-19/3	0	0	5/3	X
	8	30/17	0	[1]	3/17	0	-1/17
	0	23	0	0	-1/2	1	0
	10	29/17	1	0	-1/34	0	3/17
	530/17	0	0	19/17	0	22/17	X

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

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

Висновок: тобто для отримання максимального прибутку необхідно виготовляти продукції П1 одиниць та одиниць продукції П2, при цьому прибуток складатиме гр. од.

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

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

Основні додаткові

додаткові основні

Оптимальний план двоїстої задачі , .

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

Статус ресурсів:

Якщо обмеження виконується як рівність, то ресурс дефіцитний, якщо ні – недефіцитний.

Рентабельність продукції:

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

Висновок: виготовлення продукції П1 і П2 є рентабельним для виробництва, при цьому ресурс А1 і А3 використовуються для виробництва повністю і є дефіцитними, а з ресурсу А 2 підприємство має запас.

Зауваження. При застосуванні симплекс-методу для розв’язування задач лінійного програмування можливі такі особливі випадки:

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Категорії

МЕТОДИЧНІ ВКАЗІВКИ до виконання розрахункової роботи з навчальної дисципліни “Економіко-математичні методи та моделі оптимізаційні методи та моделі”

Схожі підручники