Задача 2.

Знайти мінімальне і максимальне значення функції мети z при наявності системи обмежень:

Z= -2x₁ + 4x₂ +8 extr;

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

1. Будуємо граничні прямі:

I: -5x₁ + 2x₂ = 7;

1. x₁ = 0; x₂ =3,5; (0; 3,5);

2. x₂ = 0; x₁ = -1,4; (-1,4; 0);

II: x₁ -2x₂ =5;

1. x₁ = 0; x₂ = -2,5; (0;-2,5);

2. x₂ = 0; x₁ = 5; (5; 0);

III: x₁ + x₂ = 2;

1. x₁ = 0; x₂ = 2; (0;2);

2. = 0; x₁ = 2; (2;0);

IV: x₁ + x₂ = 6;

1. x₁ = 0; x₂ = 6; (0; 6);

2. x₂ = 0; x₁ = 6; (6; 0);

V: x₁ = 0;

VI: x₂ = 0;

2. Будуємо багатокутник розв’язків – ABCDEF.

3. Будуємо вектор мети

4. Проводимо лінії рівняння перпендикулярно Мінімуму можуть відповідати точки E і F, а максимуму точка A.

5. Визначаємо координати точок:

E: IIVI:;

Z min =

F: IIIV:

Z min =

A: IIV:

Z max =

Відповідь: на планах EF з координатамипри плані

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

Розв’язати графічно ЗЛП:

1. 2.

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

3. 4.

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

5. 6.

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

7. 8.

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

9. 10.

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

Тема : "Розв’язування ЗЛП симплекс-методом"

Задача 1.

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

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

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

(1)

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

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

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

. Ранг матриці А дорівнює тому, що, наприклад, визначник

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

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

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

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

№	Базис	Сі базис		14	12	0	0	0	Ci
1		0	99	3	2	1	0	0
2		0	74	2	2	0	1	0
3		0	101	2	3	0	0	1
4			0	-14	-12	0	0	0

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

Оцінки:

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

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

№	Базис	Сі базис		14	12	0	0	0	Сі
1		14	33	1	2/3	1/3	0	0
2		0	8	0	2/3	-2/3	1	0
3		0	35	0	5/3	-2/3	0	1
4			462	0	-8/3	14/3	0	0

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

№	Базис	Сі базис		14	12	0	0	0	Сі
1		14	25	1	0	-1	-1	0
2		12	12	0	1	-1	3/2	0
3		0	15	0	0	1	-5/2	1
4			494	0	0	2	4	0

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

Оцінки:

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

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

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

min,

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

тоді

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

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