Рішення задач лінійного програмування

Контрольна робота № 2
Завдання 1
Рішення задач лінійного програмування графічним методом
Мета завдання: придбати практичні навички вирішення завдань лінійного програмування графічним методом.
Індивідуальне завдання
Знайти максимум і мінімум лінійної форми графічним методом за вихідними даними завдання ЛП (таблиця 1).
Таблиця 1

Номер варіанта	Цільова функція	Обмеження задачі лінійного програмування
6

Рішення завдання
Побудуємо область L допустимих рішень. Замінимо в кожному нерівності завдання знак нерівності на знак рівності. Отримаємо рівняння прямих:
x ₁ +4 x ₂ = 8, 2x _{1-x 2} = 4, x ₁ + x ₂ = 1, x ₁ = 0, x ₂ = 0.
Область L визначається як загальна частина півплощини, відповідних нерівностей обмежень (малюнок 1).

X 1

Z = 0

D

III

minZ

V

Z max

IV

I

A

C

B

II

C

X 2

L

Малюнок 1. Графічне рішення задачі ЛП
У цьому завданню вона становить багатокутник ABCD. Для знаходження екстремуму функції Z =- 2x ₁ +4 x _2, будуємо роздільну пряму, прирівнюючи лінійну форму нулю: Z = 0. Будуємо градієнт цільової функції C (2, 4).
Мінімальне значення функції в точці D (4,5; 0,7), а максимальне в точці B.
Аналіз виконання завдання лінійного програмування
В результаті рішення задачі лінійного програмування були отримані мінімум і максимум аналізованої функції, внаслідок того, що область обмежень представляє собою замкнутий багатокутник, якщо б фігура області обмежень була не замкнута, функція могла б не мати одного або обох екстремумів в заданій області.

Завдання 2
Рішення задач ЛП симплексним методом з використанням симплекс-таблиць
Мета завдання: закріпити теоретичні відомості і набути практичних навичок вирішення завдань ЛЗ симплекс-методом.
Індивідуальне завдання
Знайти максимум лінійної форми
Z = c ₁ x ₁ + c ₂ x ₂
за умов:

Дані представлені в таблиці 2.

Номер варіанта	A 11	A 12	A 21	A 22	A 31	A 32	B 1	B 2	B 3	C 1	C 2
6	4	1	3	6	8	7	43	74	76	7	4

Наведемо завдання ЛП до канонічного вигляду:
-Z '=-Z =-7x _{1-4x 2}
при обмеженнях

x _3, x _4, x ₅ - додаткові змінні.
У другому рівнянні додаткова мінлива введена з коефіцієнтом -1 і рівняння помножена на -1.
Постановка задачі у вигляді матриці системи обмежень

Рішення задачі ЛП до складених симплекс-таблицями
Одиничні вектори A _3, A _4, A ₅ утворюють базис тривимірного простору (m = 3). Вирішувати це завдання алгоритмом симплекс-методу можна, оскільки змінні x _3, x _4, x ₅ входять з коефіцієнтом +1 відповідно в перше, друге і третє обмеження. Таким чином, x _3, x _4, x ₅ - базисні змінні, а інші небазисних. Вважаючи небазисних змінні в обмеженнях рівними нулю, отримаємо вихідне дозволене базисне рішення:
X ₀ = (0,0,43, -74,76).
Заповнюємо вихідну симплекс-таблицю (таблиця 2)
Таблиця 2. Нульова симплекс-таблиця

i	Б x	С б	A 0	-7	-4	0	0	0	T
				A 1	A 2	A 3	A 4	A 5
1	A 3	0	43	4	1	1	0	0
2	A 4	0	74	-3	-6	0	1	0
3	A 5	0	76	-8	7	0	0	1
4			0	7	4	0	0	0

Так як серед різниць є позитивні, то X ₀ не є оптимальним рішенням. Будуємо нове базисне рішення.
.
Виводимо з базису вектор A _3, так як
.
Дозволяє елемент таблиці x ₁₂ виділимо колом, а дозволяє стовпець і рядок стрілками.
Таблиця 3. Перша симплекс-таблиця

i	Б x	C б	A 0	-7	-4	0	0	0	T
				A 1	A 2	A 3	A 4	A 5
1	A 1	-7		1			0	0
2	A 4	0		0			1	0
3	A 5	0	162	0	9	2	0	1
4				0			0	0

Так як серед різниць є позитивні, то оптимальне рішення не отримано. Будуємо нове базисне рішення.
.
Виводимо з базису вектор A _4, так як
.
Таблиця 4. Друга симплекс-таблиця

i	Б x	C б	A 0	-7	-4	0	0	0	T
				A 1	A 2	A 3	A 4	A 5
1	A 2	-4	43	4	1	4	0	0
2	A 4	0	736	21	0		1	0
3	A 5	0	-225	-36	0	-34	0	1
4				-9	0		0	0

Так як всі різниці в другій таблиці (таблиця 4) непозитивно: , Т отримано оптимальне рішення:
min (-Z) = -225.
Тоді max (Z) =-min (-Z) = 225
Аналіз оптимального плану.
Використання змінної x ₁ недоцільно.

Завдання 3
Моделювання і рішення задач ЛП на ЕОМ
Мета завдання: придбати практичні навички моделювання задач ЛП і їх вирішення симплекс-методом з використанням прикладної програми SIMC.
Індивідуальне завдання
Підприємство може працювати по 5-ти технологічним процесам, причому кількість одиниць продукції, що випускається з різних ТП за од. часу відповідно рівні 300, 260, 320, 400, 450 шт. витрати виробничих факторів у гривнях при роботі з різних ТП протягом 1 од. часу і розташовуються ресурси цих факторів у табл.5.
Знайти програму максимального випуску продукції.
Таблиця 5.

фактори	Спосіб виробництва					Ресурси, грн
	1	2	3	4	5
Сировина	12	15	10	12	11	1300
Ел.енергія	0,2	0,1	0,2	0,25	0,3	30
Зарплата	3	4	5	4	2	400
Накладні витрати	6	5	4	6	4	800

Математична інтерпретація задачі

Вихідні масиви, записані у вигляді, придатному для вирішення завдання по програмі SIMC
5
4
12.000 15.000 10.000 12.000 11.000 <1300.000
0.200 0.100 0.200 0.250 0.300 <30.000
3.000 4.000 5.000 4.000 2.000 <400.000
6.000 5.000 4.000 6.000 4.000 <800.000
300.000 260.000 320.000 400.000 450.000
1
Малюнок 2. Вихідні масиви для вирішення задачі
Роздруківка ЕОМ з результатом рішення
Ітерація N = 1 РІШЕННЯ ЗНАЙДЕНО!
ПОТОЧНА СИМПЛЕКС-ТАБЛИЦЯ ЗАДАЧА НЕ виродилися
Бx Cб Po 1 2 3 4 травня
6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000
7 0.000 30.000 0.200 0.100 0.200 0.250 0.300
8 0.000 400.000 3.000 4.000 5.000 4.000 2.000
9 0.000 800.000 6.000 5.000 4.000 6.000 4.000
0.000 300.000 260.000 320.000 400.000 450.000
КОД ПОМИЛКИ = 0
ОПТИМАЛЬНИЙ ЗНАЧЕННЯ БАЗИС-ВЕКТОРА І РІШЕННЯ
Оптимум ЦІЛЬОВОЇ ФУНКЦІЇ = 0.0000
Ітерація N = 1 ПРОДОВЖЕННЯ РІШЕННЯ ПОТОЧНА СИМПЛЕКС-ТАБЛИЦЯ ЗАДАЧА НЕ виродилися
Бx Cб Po 1 2 3 4 травня
6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000
7 0.000 30.000 0.200 0.100 0.200 0.250 0.300
8 0.000 400.000 3.000 4.000 5.000 4.000 2.000
9 0.000 800.000 6.000 5.000 4.000 6.000 4.000
0.000 -300.000 -260.000 -320.000 -400.000 -450.000
У БАЗИС ВВОДИТЬСЯ 5 стовпець
З базису Висновок 7 стовпець
Ітерація N = 2 ПРОДОВЖЕННЯ РІШЕННЯ ПОТОЧНА СИМПЛЕКС-ТАБЛІЦАЗАДАЧА НЕ виродилися
Бx Cб Po 1 2 3 4 липня
6 0.000 200.000 4.667 11.333 2.667 2.833 -36.667
5 450.000 100.000 0.667 0.333 0.667 0.833 3.333
8 0.000 200.000 1.667 3.333 3.667 2.333 -6.667
9 0.000 400.000 3.333 3.667 1.333 2.667 -13.333
45000.000 -0.000 -110.000 -20.000 -25.000 1500.000
У БАЗИС ВВОДИТЬСЯ 2 Стовпець
З базису вивід 6 стовпець
Ітерація N = 3 ПРОДОВЖЕННЯ РІШЕННЯ ПОТОЧНА СИМПЛЕКС-ТАБЛІЦАЗАДАЧА НЕ виродилися
Бx Cб Po 1 3 4 6 липня
2 260.000 17.647 0.412 0.235 0.250 0.088 -3.235
5 450.000 94.118 0.529 0.588 0.750 -0.029 4.412
8 0.000 141.176 0.294 2.882 1.500 -0.294 4.118
9 0.000 335.294 1.824 0.471 1.750 -0.324 -1.471
46941.176 45.294 5.882 2.500 9.706 1144.118
КОД ПОМИЛКИ = 0
ОПТИМАЛЬНИЙ ЗНАЧЕННЯ БАЗИС-ВЕКТОРА І РІШЕННЯ
X2 = 17.6471
X5 = 94.1176
Оптимум ЦІЛЬОВОЇ ФУНКЦІЇ = 46941.1765
РІШЕННЯ ЗНАЙДЕНО!

Оптимальний план. Економічна інтерпретація оптимального рішення.
Відповідно до отриманого результату випуск продукції по 1,3 і 4 технологічним процесам недоцільний.
Завдання 4
Моделювання транспортних завдань та їх вирішення методом потенціалів
Мета завдання: придбати практичні навички моделювання і розв'язання транспортної задачі ЛП методом потенціалів.
Індивідуальне завдання
Скласти оптимальний розподіл трьох видів механізмів на чотирьох ділянках робіт, що забезпечують мінімальну собівартість виконання всієї роботи. Кількість одиниць механізмів, потреби ділянок у механізмах і собівартість виконання одиниці роботи кожним механізмом на відповідній ділянці наведені в таблиці 6.
Таблиця 6. 06 варіант транспортної задачі

Вид механізму	Собівартість виконання одиниці роботи механізму, гр.				Кількість одиниць a i механізмів
	B 1	B 2	B 3	B 4
A 1	11	4	3	1	15
A 2	6	8	9	7	10
A 3	4	8	4	2	35
Потреби b j ділянок у механізмах	25	20	10	5

Математичне формулювання транспортної задачі
Нехай x _ij - кількість одиниць роботи, виконаної механізмом виду a _i, на ділянці роботи b _j. Потрібно визначити план розподілу механізмів, здатний мінімізувати собівартість виконання всієї роботи:

при обмеженнях:
1) ; - Всі механізми повинні бути задіяні;
2) ; - Всі ділянки повинні бути завантажені;
3) ; - Кількість одиниць роботи не може бути негативним
Умова розв'язності задачі виконується:
25 +20 +10 +5 = 15 +10 +35; 60 = 60.
Вихідний опорний план, складений за методом північно-західного кута
Таблиця 7

I					a i
	B 1	B 2	B 3	B 4
A 1	11	4 15	3	1	15
A 2	6 5	8 5	9	7	10
A 3	4 20	8	4 10	2 5	35
b j	25	20	10	5

Рішення транспортної задачі методом потенціалів

Отже, видно що до числа зайнятих клітин слід ввести клітину (2,1).
Отримаємо новий покращений план - таблиця 8.
Таблиця 8

I					a i
	B 1	B 2	B 3	B 4
A 1	11	4 15	3	1	15
A 2	6 5	8 5	9	7	10
A 3	4 20	8	4 10	5 5	35
b j	25	20	10	5

Введемо в число зайнятих клітину (1,4). Отримаємо новий покращений план - Таблиця 9.
Таблиця 9

I					a i
	B 1	B 2	B 3	B 4
A 1	11	4 10	3 5	1	15
A 2	6	8 10	9	7	10
A 3	4 25	8	4 5	2 5	35
b j	25	20	10	5

Так як, - То даний план є оптимальним і значення собівартості за даним планом.
x ₁₂ = 15; x ₂₁ = 5; x ₂₂ = 5; x ₃₁ = 20; x ₃₃ = 10; x ₃₄ = 5.
Z = 15 * 4 +5 * 6 +5 * 8 +20 * 4 +10 * 4 +5 * 2 = 260.
Аналіз оптимального плану
Даний оптимальний план показує, як потрібно розподілити механізми по ділянках для отримання мінімальної собівартості виконаної роботи.

Завдання 5
Рішення транспортної задачі на ЕОМ
Мета завдання: придбати практичні навички вирішення транспортної задачі на ЕОМ з використанням прикладної програми TRAN2.
Індивідуальне завдання:
Скласти оптимальний розподіл трьох видів механізмів на чотирьох ділянках робіт, що забезпечують мінімальну собівартість виконання всієї роботи. Кількість одиниць механізмів, потреби ділянок у механізмах і собівартість виконання одиниці роботи кожним механізмом на відповідній ділянці наведені в таблиці 6.
Таблиця 10. 06 варіант транспортної задачі

Вид механізму	Собівартість виконання одиниці роботи механізму, гр.				Кількість одиниць a i механізмів
	B 1	B 2	B 3	B 4
A 1	11	4	3	1	15
A 2	6	8	9	7	10
A 3	4	8	4	2	35
Потреби b j ділянок у механізмах	25	20	10	5

Вихідні масиви для розв'язання транспортної задачі за програмою TRAN2

Роздруківка з ЕОМ з результатом рішення

Оптимальний план транспортної задачі
x ₁₂ = 15; x _{­ 21} = 5; x _{2 лютого} = 5; x ₃₁ = 20; x ₃₃ = 10; x ₃₄ = 5.
Z = 15 * 4 +5 * 6 +5 * 8 +20 * 4 +10 * 4 +5 * 2 = 260.
Аналіз результатів і висновки
Рішення транспортної задачі на ЕОМ автоматизує роботу з обчислення рішень транспортних задач і на тестованому вхідному умова виходить за 3 ітерації, як і при ручному обчисленні.

Завдання 6
Рішення багатоетапних задач методом динамічного програмування
Мета завдання: придбати практичні навички вирішення багатоетапних задач методом динамічного програмування.
Індивідуальне завдання.
У таблиці 11 наведені значення g _i (x) можливого приросту продукції на чотирьох підприємствах залежно від виділеної на реконструкцію і модернізацію виробництва суми x.
Розподілити між підприємствами наявні 100 тис. гр., Щоб загальний приріст f ₄ (100) випуску продукції був максимальним. Для спрощення обчислень значення x приймати кратними 20 тис. гр.
Таблиця 11

Підприємство	Приріст випуску продукції, тис. гр.	Засоби c, тис. гр.					Номер варіанта
		20	40	60	80	100
1	G 1 (x)	11	21	40	54	62	6
2	G 2 (x)	13	20	42	45	61
3	G 3 (x)	12	22	34	55	60
4	G 4 (x)	10	27	33	57	69

Функціональне рівняння Беллмана для розглянутої задачі
f ₁ (x) = max [g ₁ (x)] = g ₁ (x) - для першого підприємства;
- Для решти підприємств.
Рішення задачі оптимального розподілу коштів між підприємствами методом динамічного програмування

Таблиця 12

Кошти з, тис. гр.	Підприємство
	1	2	3	4
	G 1 (x)	G 2 (x)	G 3 (x)	G 4 (x)
20	11	13	12	10
40	21	20	22	27
60	40	42	34	33
80	54	45	55	57
100	62	62	60	69

Таблиця 13

X 1 * (c)	20	40	60	80	100
F 1 (c)	11	21	40	54	62

Таблиця 14

x З	0	20	40	60	80	100	F 2 (c)	X 2 * (c)
20	0 +13	12 +0					13	0
40	0 +24	12 +13	22 +0				25	20
60	0 +42	12 +24	22 +13	34 +0			42	0
80	0 +45	12 +42	22 +24	34 +13	55 +0		55	80
100	0 +67	12 +45	22 +42	34 +24	55 +3	60 +0	68	80

Таблиця 15

x З	0	20	40	60	80	100	F 3 (c)	X 3 * (c)
20	0 +13	10 +0					13	0
40	0 +29	10 +13	27 +0				27	40
60	0 +42	10 +25	27 +13	33 +0			42	0
80	0 +55	10 +42	27 +25	33 +13	57 +0		57	80
100	0 +68	10 +55	27 +42	33 +25	52 +13	69 +0	69	40

Таблиця 16

З	X 1 * (c)	F 1 (c)	X 2 * (c)	F 2 (c)	X 3 * (c)	F 3 (c)	X 4 * (c)	F 4 (c)
0	0	0	0	0	0	0	0	0
20	20	11	20	13	0	13	0	13
40	40	21	20	24	20	25	40	27
60	60	40	60	42	0	42	0	42
80	80	54	80	45	80	55	80	57
100	100	62	20	67	80	68	40	69

Отже, з таблиці 16 видно, що найбільший приріст випуску продукції, який можуть дати чотири підприємства при розподілі між ними 100 тис. грн. складає 69 тис. грн. При цьому четвертому підприємству потрібно виділити 40 тис. грн., А іншим 60 тис. грн.
Оптимальний розподіл залишилися 60 тис. грн. між ^3-ма підприємствами забезпечить приріст продукції на суму 42 тис. грн., за умови, що ^3-му підприємству не будуть виділені кошти. Залишається 60 тис. грн., Які треба розподілити між ^2-ма підприємствами. Виділивши всю суму, що залишилася (60 тис. грн.) Друге, прибуток становитиме 42 тис. грн. першому підприємству коштів не залишається.
Максимальний приріст випуску продукції на чотирьох підприємствах при розподілі між ними 100 тис. грн. складає 69 тис. грн. і буде отримана, якщо першому підприємству не виділяти коштів, другому - 60 тис. грн., третьому не виділяти, а четвертому - 40 тис. грн.
Це рішення можна записати у вигляді:
X ^* = (0,0,60,40); f ^* = f ₄ (100) = 69 тис. гр.