Задача 2

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

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

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

z = 10x₁ + 8x₂ max,

(1)

Опорний розв‘язок (2) отримаємо, наприклад, при х_{3 =} х₄ = 0;

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

z = 10x₁ +8x₂ max,

(2)

тоді х₁ = 73; х₂ = 27; х₅ = 253, тобто х* (73; 27; 0; 0; 273).

Основна матриця системи обмежень (2):

має ранг r (A) = 3, бо, наприклад, .

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

Базисна матриця .

Будуємо обернену матрицю . Визначник

Алгебраїчні доповнення:

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

Перевірка:

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

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

№	Ба - зис	Сі базис		10	8	0	0	0	Сі
1		10	73	1	0	1	-2	0
2		8	27	0	1	-1	3	0
3		0	253	0	0	1	-4	1
4			946	0	0	2	4	0

Знаходимо:

Оцінки:

Усі оцінки невід’ємні (). Даний опорний розв’язок оптимальний.

при оптимальному плані Подвійна задача до (1):

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

,тоді:

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

Задачі для самостійної роботи.

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

1. 2.

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

3. 4.

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

5. 6.

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

Тема: "Транспортна задача. Метод потенціалів" Задача 1

Знайти оптимальний план транспортної задачі за даною таблицею, де - матриця вартості перевезення одиниці вантажу;- запаси,- потреби вантажу (у.о.), де.

.

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

Знаходимо:

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

b а	220	190	310	170
400	11 150	10 ө 20	7 60	9 170
250	8	5	4 ө 250	13
170	4	3 170	14	15
70	0 70	0	0	0

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

Базис складають вектори:

Він невироджений, бо що дорівнює кількості базисних векторів.

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

Система для визначення потенціалів має вигляд:

Задаючи отримаємо розв’язок системи:

Обчислимо оцінки небазисних векторів:

Так як оцінка >0, то даний опорний розв’язок є неоптимальним. Вводимо в базис вектор. Невідомий об’єм переведень за маршрутомпозначимо. Складаємо компенсаторний ланцюг. ВизначаємоНова таблиця, яка відповідає новому опорному розв’язку, має вигляд:

b a	220	190	310	170
400	11 ө 150	10	7 80	9 170
250	8	5 20	4 ө 230	13
170	4	3 ө 170	14	15
70	0 70	0	0	0

Базисні вектори: Система для визначення потенціалів має вигляд:

Звідси отримаємо:

Оцінки небазисних векторів:

У базис вводимо вектор

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

b a	220	190	310	170
400	11	10	7 230	9 170
250	8	5 170	4 80	13
170	4 150	3 20	14	15
70	0 70	0	0	0

Базис складають вектори:

Система для потенціалів має вигляд:

Звідси:

Оцінки небазисних векторів:

Всі оцінки недодатні. Даний опорний розв’язок оптимальний. Оптимальне значення функції мети:

.

Перевіряємо нульову оцінку на оптимальність. В базис вводимо вектор (4,4). Нова таблиця, яка відповідає новому опорному розв’язку, має вигляд:

b a	220	190	310	170
400	11	10	7 250	9 150
250	8	5 190	4 60	13
170	4 170	3	14	15
70	0 50	0	0	0 20

тобто план перевезень також оптимальний.

Відповідь: при слідуючих оптимальних планах перевезень: І план -при цьому I споживач не отримає 70 одиниць продукції;

ІІ план – при цьому I споживач не отримає 50 одиниць продукції, а ІІ - 20.