Математична модель задачі 10.4

Позначимо – кількість корму P₁, – кількість корму P₂, – кількість корму P₃, – кількість корму P₄. Тоді отримаємо математичну модель задачі:

(15)

(16)

(17)

Канонічна форма задачі

Домножуємо нерівності (15) і цільову функцію (17) на (-1)

Введемо нові невід’ємні змінні , і додамо їх до лівих частин нерівностей. Отримаємо систему недоозначених рівнянь (3 рівняння, 7 невідомих).

Складаємо симплекс – таблицю 1.

с имплекс - таблиця 1

Базис	Ci	P0	P1	P2	P3	P4	P5	P6	P7
			-200	-50	-70	-100
P5		-100	-150	-15	-5	-80
P6		-100	-150			-10
P7		-300	-25	-80	-120	-500
D j

-оцінка невідомого .

Вибір розв’язуючого елемента

1. Розв’язуючий елемент повинен бути від’ємним!

2. Розв’язуючий рядок – P7 знаходимо з умови min (P0). min (-100;-100;-300) = -300.

3. Розв’язуючий стовпець – P4 знаходимо з умови min (|Dj/aij|), тут i – номер розв’язуючого рядка. min (200/25; 50/80; 70/120; 100/500) = 100/500.

4. Вектор P7 виходить з базису, Вектор P4 входить у базис.

5. Розв’язуючий елемент – число -500 – знаходиться на перетині розв’язуючого рядка P7 і розв’язуючого стовпця P4.

Алгоритм двоїстого симплекс-методу

1. Розв’язуючий рядок P7 ділимо на розв’язуючий елемент – число -500;

2. Базисні стовпці P5, P6 i P7 повинні бути одиничними векторами;

3. Усі інші елементи таблиці (стовпці P0 - P4 крім рядка P7) перераховуються згідно правила прямокутника:

. (18)

Тут розв’язуючий елемент; елемент, який перераховується.

В результаті отримуємо наступну симплекс-таблицю 2.

симплекс - таблиця 2

Базис	Ci	P0	P1	P2	P3	P4	P5	P6	P7
			-200	-50	-70	-100
P5		-52	-146	-2,2	14,2				-0,16
P6		-94	-149,5	1,6	2,4				-0,02
P4	-100	0,6	0,05	0,16	0,24				-0,002
D j		-60							0,2

План, який представлений у цій таблиці не є оптимальним, оскільки серед вільних членів P0 є від’ємні. За описаним вище алгоритмом знаходимо розв’язуючий рядок – P6 та розв’язуючи стовпець – P1. Змінна P6 виходить з базису, змінна P1 входить у базис. Застосовуючи алгоритм двоїстого симплекс-методу отримуємо наступну симплекс-таблицю 3.

симплекс - таблиця 3

Базис	Ci	P0	P1	P2	P3	P4	P5	P6	P7
			-200	-50	-70	-100
P5		39.80	0.00	-3.76	11.86	0.00	1.00	-0.98	-0.14
P1	-200	0.63	1.00	-0.01	-0.02	0.00	0.00	-0.01	0.00
P4	-100	0.57	0.00	0.16	0.24	1.00	0.00	0.00	0.00
D j		-182.61	0.00	36.09	49.13	0.00	0.00	1.30	0.17

5. Оскільки всі P0 ³ 0, отримано оптимальний розв’язок задачі. Оптимальні значення параметрів x1, x4 i x5 знаходимо у стовпчику P0. Невідомі x2, x3, x6 i x7 яких немає у базисі є вільними і дорівнюють нулю.

Відповідь. Оптимальний харчовий раціон має вигляд: x1 = 0.63; x2 = 0; x3 = 0; x4 = 0.57; x5 = 39.8; x6 = 0; x7 = 0. Fmin (сумарна вартість) = 182,61.

Таблиця 4. В а р і а н т и з а в д а н ь д о т е м и 1 0

a11

a12

a13

a14

b1

a21

a22

a23

a24

b2

a31

a32

a33

a34

b3

c1

c2

c3

c4

N

a11

a12

a13

a14

b1

a21

a22

a23

a24

b2

a31

a32

a33

a34

b3

c1

c2

c3

c4

 

 

Тема 11

Задача лінійного програмування: задача про розріз труб

11.1. Завдання. Побудувати математичну модель задачі лінійного програмування (задача на мінімум відходів). Звести задачу до канонічної форми. Розв’язати задачу двоїстим симплекс-методом.

11.2. Постановка задачі:

В обробку поступила партія труб довжиною L = 7.5 м кожна. Необхідно розрізати труби, отримавши N1= 50 заготовок довжиною L1 = 3.5 м, N2= 30 заготовок довжиною L2 = 2.5 м і N3= 40 заготовок довжиною L3 = 2.0 м. Побудувати оптимальний план розрізу при якому сумарна довжина відходів буде мінімальною.

Таблиця 5. Таблиця варіантів розрізу

N	Lі	В а р і а н т и
	3.5		-	-			-	-
	2.5	-		-		-
	2.0	-	-		-
Відходи	0.5		1.5	1.5		0.5	1.0

Математична модель задачі

Позначимо x _і – кількість труб, розрізаних згідно і – го варіанту. Тоді отримаємо математичну модель задачі у наступному вигляді:

(19)

(20)

. (21)

Канонічна форма задачі

Домножимо нерівності (19) і цільову функцію (21) на (-1). Введемо нові невід’ємні змінні і додамо їх до лівих частин нерівностей. Отримаємо систему недоозначених рівнянь (3 рівняння, 10 невідомих).

Задача розв’язується двоїстим симплекс – методом.

Таблиця 6. В а р і а н т и з а в д а н ь д о т е м и 1 1

Варіант	L	L1	L2	L3	N1	N2	N3
1	120	50	40	55	35	45	40
2	110	35	50	45	30	50	20
3	110	40	30	55	45	20	25
4	110	50	45	30	25	30	35
5	120	50	45	65	30	40	25
6	125	40	60	55	45	30	20
7	125	50	60	35	30	45	50
8	95	40	30	50	20	25	30
9	125	45	65	50	40	30	50
10	105	30	35	50	40	30	50
11	100	30	40	55	50	20	35
12	120	35	45	50	30	50	40
13	100	40	35	45	25	45	35
14	100	40	55	35	25	40	30
15	105	40	50	35	30	40	20
16	115	45	35	55	50	30	45
17	130	65	45	50	40	30	50
18	105	40	55	30	60	50	40
19	105	55	40	30	20	35	40
20	115	45	50	60	30	10	40
21	115	50	40	45	20	45	30
22	115	45	55	65	50	30	40
23	125	45	50	35	40	30	50
24	115	45	55	40	25	30	40
25	110	45	60	35	30	40	50
26	115	50	40	55	25	35	40
27	115	65	30	45	10	30	40
28	125	55	60	40	40	30	45
29	120	50	35	60	45	35	40
30	115	40	50	30	30	20	50
31	125	50	35	45	45	30	25
32	115	40	45	30	35	30	25
33	135	50	45	65	40	30	25
34	130	35	50	55	45	20	30
35	125	40	60	35	40	45	20
36	95	40	30	35	40	25	30
37	135	45	65	50	30	30	40
38	110	35	30	50	50	30	20
39	105	30	40	50	30	20	45
40	130	35	45	50	40	50	30
41	95	40	35	25	45	25	35
42	110	50	40	35	35	20	30
43	125	40	50	65	20	40	30
44	115	40	35	55	25	30	45
45	125	45	65	40	50	30	20
46	105	35	55	40	30	50	40
47	115	55	45	30	40	35	30
48	125	45	50	60	35	10	40
49	120	45	55	65	20	30	40
50	130	35	50	45	50	30	40

Тема12

Транспортна задача

Постановка задачі.

Три бригади за тиждень виробляють корми в кількостях a₁, a₂ i a₃ відповідно. Їх необхідно розвезти на 5 ферм, згідно з поданими заявками, у кількостях b₁, b₂, b₃, b₄, b₅. Вартість перевезення вважається пропорційною до кількості завантаженого корму x_ij і відстані від постачальника (бригади) до споживача (ферми) c_ij. Необхідно скласти такий план перевезень кормів, загальна вартість якого буде мінімальною. Необхідні для розрахунку параметри представлені у наступній Таблиці 7.

Таблиця 7. Технологічні параметри транспортної задачі.

Ферми® Бригади¯	B1	B2	B3	B4	B5	Запаси
A1		4		3		2		2		4
A2		1		4		8		4		1
A3		9		7		3		7		2
Потреби	60	70	120	130	100	480

Необхідно скласти оптимальний план закріплення бригад за фермами з умовою мінімальної вартості перевезення кормів.

 

12.2. Математична модель транспортної задачі

Позначимо x_ij – кількість одиниць корму, який планується перевезти від i – го постачальника (сівозміни) до j – го споживача (ферми). Оскільки всі вантажі повинні бути вивезені, то мають місце такі рівності:

(22)

Оскільки всі потреби споживачів повинні бути задоволені, то мають місце такі рівності:

(23)

Оскільки вантажі перевозяться лише в одну сторону, очевидно, що:

(24)

Загальна вартість перевезення вважається пропорційною до кількості перевезених вантажів та відстані від постачальника до споживача і повинна бути мінімальною:

(25)

Якщо виконується умова , задача називається закритою.

 

12.3. Алгоритм розв’язування ТЗ

Потрібно:

1. скласти початковий опорний план задачі методом північно-західного кута;

2. скласти початковий опорний план задачі методом мінімального тарифа;

3. вибравши кращий з побудованих початкових планів, виконати його оптимізацію методом потенціалів за такою схемою:

3.1. скласти систему рівнянь (по базисних клітинах) для визначення потенціалів рядків U_i та стовпців V_j та, прийнявши U₁=0, розв’язати отриману систему;

3.1.1. визначити характеристики вільних клітин за формулою

; (26)

3.2. якщо всі характеристики є невід’ємні, завершити розв’язування задачі. Виписати оптимальний план перевезень у вигляді матриці, а також мінімальне значення вартості перевезень F_min;

3.3. якщо не всі характеристики є невід’ємні, необхідно вибрати найбільшу додатну характеристику і побудувати для відповідної вільної клітини таблиці цикл. Позначити вершини циклу умовними знаками “+” (збільшити вантажо-потік) i “-” (зменшити вантажопотік). Початкова вільна вершина позначається знаком “+”, а всі інші – по черзі “-” i “+”; серед всіх вершин, позначених знаком “-”, вибрати найменше перевезення – m. Для всіх вершин, позначених знаком “+”збільшити перевезення на m, для вершин, позначених знаком “-” зменшити перевезення на m. Перейти до пункту 3.1

 

12.4. Побудова початкового опорного плану ТЗ

Таблиця 8. Метод північно – західного кута

	B1	B2	B3	B4	B5	Запаси
A1		4		3		2		2		4	140
60		70		10
A2		1		4		8		4		1	180
				110		70
A3		9		7		3		7		2	160
						60		100
Потреби

F = 60*4 + 70*3 + 10*2 + 110*8 + 70*4 + 60*7 + 100*2 =

240 + 210 + 20 + 880 + 280 + 420 + 200 = 2250 – вартість перевезень

 

Таблиця 9. Метод мінімального тарифа

	B1	B2	B3	B4	B5	Запаси
A1		4		3		2		2		4	140
				10		130
A2		1		4		8		4		1	180
60		20						100
A3		9		7		3		7		2	160
		50		110
Потреби

F = 10*2 + 130*2 + 60*1 + 20*4 + 100*1 + 50*7 + 110*3 =

20 + 260 + 60 + 80 + 100 + 350 + 330 = 1200 – вартість перевезень

 

12.5. Метод потенціалів

За основу виберемо план, складений по методу мінімального тарифа. Оптимізуємо даний план за методом потенціалів. Для кожного i – го рядка та j – го стовпця введемо певну їх ознаку – потенціал. Складаємо систему рівнянь (по базисних клітинках плану) для визначення потенціалів рядків і стовпців, використовуючи наступну формулу .

U₁ + V₃ = 2;

U₁ + V₄ = 2;

U₂ + V₁ = 1;

U₂ + V₂ = 4;

U₂ + V₅ = 1;

U₃ + V₂ = 7;

U₃ + V₃ = 3.

Приймемо U₁ = 0. Тоді отримаємо наступний розв’язок системи:

U₁ =0; V₃ = 2;

U₁ =0; V₄ = 2;

U₂ =-2; V₁ = 3;

U₂ =-2; V₂ = 6;

U₂ =-2; V₅ = 3;

U₃ =1; V₂ = 6;

U₃ =1; V₃ = 2.

Для кожної вільної клітинки введемо поняття її характеристики , яку будемо обчислювати за формулою:

. (27)

Тут та - потенціали відповідних рядка і стовпця, - тариф даного перевезення. Додатна характеристика вільної клітини свідчить про неоптимальність плану і є підставою для включення даної клітини в новий план. Обчислимо характеристики вільних клітин:

D₁₁ = u₁ + v₁ – c₁₁ = 0 + 3 – 4 = -1;

D₁₂ = u₁ + v₂ – c₁₂ = 0 + 6 – 3 = +3;

D₁₅ = u₁ + v₅ – c₁₅ = 0 + 3 – 4 = -1;

D₂₃ = u₂ + v₃ – c₂₃ = -2 + 2 – 8 = -8;

D₂₄ = u₂ + v₄ – c₂₄ = -2 + 2 – 4 = -4;

D₃₁ = u₃ + v₁ – c₃₁ = 1 + 3 – 9 = -5;

D₃₄ = u₃ + v₄ – c₃₄ = 1 + 2 – 7 = -4;

D₃₅ = u₃ + v₅ – c₃₅ = 1 + 3 – 2 = +2.

Характеристики D₁₂ і D₃₅ є додатніми. Це свідчить про неоптимальність плану. Клітинку A₁B₂ необхідно включити в план. Деяку клітинку необхідно виключити з базису. Для цього складаємо цикл вільної клітини. Клітина A₁B₂ буде початком циклу.

 

12.6. Перерозподіл вантажопотоків по вершинах циклу - 1

	B1	B2	B3	B4	B5	Запаси
A1		4	+	3	-	2		2		4	140
				10		130
A2		1		4		8		4		1	180
60		20						100
A3		9	-	7	+	3		7		2	160
		50		110
Потреби

Будуємо цикл. Це є ламана лінія, вершини якої розташовані у клітинах таблиці, а ланки – вздовж рядків, чи стовпців. В кожній вершині циклу зустрічається дві ланки, одна з яких знаходиться у рядку, а друга у стовпці. Початковою вершиною завжди виступає вільна клітина. Всі інші вершини – це базисні клітини. Форма циклу – це прямокутник, “чобіт”, або ”вісімка”. Якщо ламана лінія, що утворює цикл перетинається, то точки самоперетину не є вершинами.

Початкову клітину циклу A₁B₂ помічаємо знак “+”. Всі інші кутові вершини циклу по черзі помічаємо знаками “-” i ”+”. В якості перерозподілюваного елемента вибираємо число 10 (мінімальний вантаж серед усіх клітин помічених знаком “-”). До клітинок помічених знаком “+” додаємо число 10, від клітин помічених знаком “-” віднімаємо число 10. Клітина A₁B₂ входить у базис, клітина A₁B₃ виходить з базису. Отримуємо новий план

Види циклів.

 

 

прямокутник “чобіт” ”вісімка”

 

12.7. Метод потенціалів. Другий крок