Задача 1. На виготовлення двох видів продукції виділяється три види ресурсів

На виготовлення двох видів продукції виділяється три види ресурсів. Запаси ресурсів: 99, 74 і 101 у.о. відповідно до норми їх витрат:

3 і 2 у.о. – 1 ресурсу; 2 і 2 у.о. – 2 ресурсу; 1 і 2 у.о. – 3 ресурсу відповідно на одиницю продукції кожного виду і прибуток 14 і 12 у.о. від реалізації одиниці продукції кожного виду відповідно. Знайти симплекс-методом такий план виробництва, який забезпечував би найбільший прибуток. Скласти подвійну задачу до вихідної і виписати її оптимальний план з останньої симплекс-таблиці розв‘язку вихідної задачі.

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

Відповідно до умови задачі отримаємо слідуючу математичну модель:

max;

(1)

Канонічний вид задачі (1):

max;

Опорний розв’язок, наприклад, можна отримати при . Тоді , тобто

Основна матриця системи обмежень: Ранг матриці А дорівнює r (А) = 3, бо, наприклад, визначник

Так як кількість додатних координат опорного розв’язку дорівнює рангу матриці А, то даний опорний розв’язок є невиродженим. Базис складають вектори Базисна матриця має вигляд:

. Обернена матриця .

Розкладаємо небазисні вектори А₁, А₂ по векторам базиса Для скорочення запису зробимо це у вигляді однієї матричної формули:

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

№	Ба- зис	Сі базис		14					Ci
1				3
				-14	-12

Обчислимо значення функції мети:

Оцінки:

Так як оцінки і від’ємні: 0 і 0, то даний опорний розв’язок не оптимальний. В базис вводимо вектор , бо його оцінка найменша із від’ємних. Із базиса виводимо вектор , бо відношення координат стовпчика до стовпчика : 99/3 = 33; 74/2 = 37; 101/2 = 50,5 – найменше із додатних для вектора . Розрахунковий елемент “3” отримаємо на перетині продовжень стрілок.

Обчислюємо нові елементи симплекс-таблиці, яка відповідає новому опорному розв’язку. Елементи рядка, який містить розрахунковий елемент ділимо на нього. Інші елементи таблиці отримаємо за правилом “хрест-на-хрест”. Наприклад, для нового значення в клітині з числом 74 маємо:

і т. д. Нова симплекс-таблиця, яка відповідає новому опорному розв’язку має вид:

№	Ба-зис	Сі базис							Сі
					2/3	1/3
2					2/3	-2/3
					5/3	-2/3
					-8/3	14/3

Так як оцінка від’ємна: 0, то даний опорний розв’язок не оптимальний. В базис вводимо вектор , бо його оцінка 0. Із базиса виводимо вектор бо відношення координат стовпчика до стовпчика : 33: 2/3 = 49,5; 8: 2/3 = 12; 35: 5/3 = 21 – найменше із додатних для вектора . Розрахунковий елемент “2/3” отримаємо на перетині продовжень стрілок. Аналогічно попередньому отримаємо нову симплекс-таблицю, яка відповідає новому опорному розв’язку.

№	Ба-зис	Сі базис							Сі
						-1	-1
						-1	3/2
							-5/2

Обчислимо значення функції мети:

Оцінки:

Так як всі оцінки невід’ємні, то даний опорний розв’зок оптимальний:

z max = 494 при плані .

Подвійна задача до (1):

min,

Із останньої симплекс-таблиці:

тоді

чого й треба було чекати.

Відповідь: при .

Розв’язати ЗЛП симплекс – методом.

1. 2.

Відповідь: Відповідь:

Тема: «Побудова подвійних (спряжених) задач»

Теоретичні питання:

1. Подвійні (спряжені) ЗЛП.

2. Правила складання подвійних задач.

3. Основні теореми подвійних задач та їх наслідки.

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

Скільки одиниць продукції кожного j -го виду слід випустити за плановий період, щоб максимізувати загальний прибуток підприємства:

(1),

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

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

Уявимо, що організація "В" може придбати у "А" наявні ресурси для своїх потреб. Нехай ціни одиниць відповідних ресурсів .

Організація "В" прагне купити згадані ресурси якнайдешевше, тобто:

(4)

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

Ціни додатні

Задача (4-6) подвійна, або спряжена до задачі (1-3).

Date: 2015-12-11; view: 992; Нарушение авторских прав