Тема 1 Лінійне програмування

Завдання 1. Розв´язання задачі лінійного програмування

У матричному вигляді задана задача лінійного програмування, З Л П, таблиця 1.

1. Методом Жордана-Гауса:

а) знайти початковий опорний план і обчислити Z();

б) перейти до іншого опорного плану й обчислити Z().

2. Для одного з опорних планів виразити базисні змінні через вільні, перейти від рівностей в обмеженнях задачі до нерівностей і розв´язати задачу геометрично.

3. Виходячи з опорного плану з «гіршою» функцією мети, замінити задачу лінійного програмування в канонічній формі та розв´язати її симплекс-методом.

4. Розв´язати вихідну задачу методом штучного базису.

Таблиця 1– Дані за варіантами

№ вар.	Z	Матриця А		№ вар.	Z	Матриця А
	max								max
						-1
-2	-1
			-1			-					-1		-
	min				-1				max
-2	-3					-1			-1
	-3	-4		-5		-		-1	-3				-
	min	-1	-1			-1			max
	-5	-1		-2	-7		-3
	-3					-					-1		-
	max		-1						min	-2	-1	-2	-1	-1	-18
	-1

Продовження таблиці 1

		-2		-5	-11		-23
			-1			-			-2		-1		-
	min			-1	-9				min		-2			-2	-1
	-2			-2	-2		-3			-3	-5
-3			-2				-3			-2
			-1			-					-1		-
	max		-2			-2	-2		min	-3			-2
	-3			-3	-6			-1	-9
	-3			-2			-2			-2	-1
				-1		-			-1			-1	-
	min	-2	-1	-2	-1	-1	-16		min		-1
							-1
						-2		-5	-11		-26
		-2				-				-1		-2	-
	max	-1							min		-1
								-1	-4	-1	-5
	-1							-2	-9	-3	-11
				-1		-			-2	-1			-
	max			-1	-4	-1	-4		min	-2	-3				-2
		-2	-9	-3	-9				-1
	-1
		-1			-1	-			-2		-1		-
	max	-1							min
						-2	-1
		-1		-1		-		-1				-2	-
	max								max		-1
			-1			-2		-5	-11		-24
		-1					-1
				-2	-1	-			-4			-2
	min		-1			-1			max
-5			-1
	-1					-2	-1
	-3	-2		-1	-2	-				-1		-1	-
	max								min	-1		-2
-1								-1
									-1

Продовження таблиці 1

			-4				-								-
	min			-2		-1			max	-3
	-2								-2	-2	-2
	-5									-1
		-1		-1		-				-3		-1	-
	min			-2					max		-3			-3	-8
			-1				-2			-2	-3
			-1		-1		-3			-2
			-1		-1	-			-4			-2	-

 

Література: [1, с. 37 – 68; 4, с. 49 – 75; 7, с. 5 – 31].

 

Завдання 2. Розв´язання задачі про розподіл ресурсів з економічним аналізом отриманих результатів

Підприємство може виготовляти чотири види продукції П-1, П-2, П-3, П-4. Збут будь-якого її обсягу забезпечений. Норми витрати ресурсів і прибуток від одиниці кожного виду продукції наведені в таблиці 2. Виконати економічний аналіз лінійної моделі:

1. Побудувати модель вихідної та двоїстої задач, знайти оптимальні плани x⁰ і y⁰.

2. Дати економічне тлумачення основних і додаткових змінних вихідної та двоїстої задач.

3. Проаналізувати доцільне розширення асортименту продукції за рахунок включення нової продукції П₅.

4. Установити діапазони зміни вихідних даних за ресурсами і ціною од. продукції, за яких структура оптимального плану не змінюється.

Таблиця 2– Дані за варіантами

№ вар.	Обсяг ресурсів: трудові, матеріальні, верстатні	Норми витрат ресурсів на одиницю продукції	Нова продукція П5
П1	П2	П3	П4
2.1
Ціна од. продукції
2.2

Продовження таблиці 2

Ціна од. продукції
2.3
Ціна од. продукції
2.4
Ціна од. продукції
2.5
Ціна од. продукції
2.6
Ціна од. продукції
2.7
Ціна од. продукції
2.8
Ціна од. продукції
2.9
Ціна од. продукції
2.10
Ціна од. продукції
2.11
	Ціна од. продукції
2.12
Ціна од. продукції
2.13
Ціна од. продукції
2.14

Продовження таблиці 2

Ціна од. продукції
2.15
Ціна од. продукції
2.16
Ціна од. продукції
2.17
Ціна од. продукції
2.18
Ціна од. продукції
2.19
Ціна од. продукції
2.20
Ціна од. продукції
2.21
Ціна од. продукції
2.22
Ціна од. продукції
2.23
Ціна од. продукції
2.24
Ціна од. продукції
2.25
Ціна од. продукції
2.26

Продовження таблиці 2

	Ціна од. продукції
2.27
Ціна од. продукції
2.28
Ціна од. продукції
2.29
Ціна од. продукції
2.30
Ціна од. продукції

 

 

Література: [1, с. 77 – 99; 4, с. 85 – 102; 7, с. 5 – 33].

Завдання 3. Розв´язання транспортної задачі з економічним аналізом отриманих результатів

Є три постачальники і чотири споживачі однорідного продукту. Потужності постачальників і попити споживачів, а також витрати на перевезення одиниці вантажу для кожної пари «постачальник-споживач» зведені в таблицю 3 постачань.

Задача полягає у наступному: знайти обсяги перевезень для кожної пари «постачальник-споживач» так, щоб:

1) потужності всіх постачальників були реалізовані;

2) попити всіх споживачів були задоволені;

3) сумарні витрати на перевезення були мінімальні.

 

Таблиця 3 – Дані для розв’язання транспортної задачі

1 a:={200, 270, 130} b:={120, 80, 240, 160}	16 a:={25, 25, 50} b:={15, 15, 40, 30}
2 a:={110, 190, 90} b:={80, 60, 170, 80}	17 a:={40, 27, 23} b:={30, 25, 15, 20}
3 a:={160, 140, 60} b:={80, 80, 60, 140}	18 a:={15, 58, 35} b:={30, 23, 35, 20}
4 a:={115, 145, 100} b:={70, 220, 40, 30}	19 a:={90, 60, 90} b:={24, 40, 80, 96}
5 a:={180, 100, 120} b:={110, 90, 120, 80}	20 a:={16, 28, 30} b:={22, 18, 13, 21}
6 a:={100, 150, 50} b:={75, 80, 60, 85}	21 a:={30, 25, 50} b:={15, 15, 45, 30}

Продовження таблиці 3

7 a:={45, 85, 20} b:={40, 30, 30, 50}	22 a:={50, 27, 23} b:={35, 30, 15, 20}
8 a:={50, 40, 20} b:={33, 22, 39, 16}	23 a:={25, 58, 35} b:={40, 23, 35, 20}
9 a:={35, 85, 60} b:={20, 60, 55, 45}	24 a:={85, 55, 90} b:={24, 40, 80, 86}
10 a:={16, 24, 30} b:={32, 14, 14, 10}	25 a:={20, 28, 30} b:={22, 18, 17, 21}
11 a:={180, 60, 80} b:={120, 40, 80, 80}	26 a:={100, 270, 130} b:={120, 80, 240, 60}
12 a:={80, 90, 70} b:={80, 50, 70, 40}	27 a:={110, 90, 60} b:={80, 60, 70, 50}

Продовження таблиці 3

13 a:={75, 200, 220} b:={180, 120, 90, 105}	28 a:={150, 140, 60} b:={70, 80, 60, 140}
14 a:={130, 80, 160} b:={70, 60, 120, 120}	29 a:={65, 85, 30} b:={50, 40, 30, 60}
15 a:={160, 140, 170} b:={120, 50, 190, 110}	30 a:={180, 200, 20} b:={110, 90, 120, 80}

Література: [1, с. 102 – 138; 4, с. 117 – 139; 8, с. 5 – 35].