2 курс. Ден. ФК, УП, ЕП 12 / Економіко математичні методи та моделі (Оптимізаційні методи) Ч.1 Ден. 2010

За оптимальним планом перевезень перший замовник отримує 90 тис. од. продукції з першої фабрики та 20 тис. од. –.з третьої. Другий споживач задовольняє свій попит за рахунок виробництва та перевезення 40 тис. од. продукції з третьої фабрики і т. д. Мри цьому загальна вартість виробництва та перевезення всієї продукції є найменшою і становить 720 ум. од.

Завдання для самостійного розв’язання

2. Розв`язати лінійну транспортну задачу (при необхідності попередньо перейти до закритої задачі)

			1		8	2	3		30								8	7	11			5		300
2.1. С =			4		7	5	1		50			2.2. С =					6	9	10			8		350
			5		3	4	4		20							11		12	7			6		300
		15			15	40		30					200				220		210				230
				2	6	3	4	8			40				1		8	2	3			30
2.3.	C =			1	5	6	9	7			30	2.4. С =			4		7	5	1			50
				3	4	1	6	10			35				5		3	4	1			20
		20			34	16	10			15			15				15	40			30

Питання для самоконтролю

1.Сформудюйте алгоритм розв’язання откритої транспортної задачі.

2.Які ви знаєте методи побудови опорного плану?

Порівняйте ці плани.

3.Що означає «виродження» опорного плану? Як його позбутися?

4.Назвіть етапи розв’язування методом потенціалів. Як обчислюють потенціали?

5.Сформудюйте умову оптимальності транспортної задачі.

Бібліографічний список до практичного заняття

[1], [3], [4], [5], [6], [7], [8], [10], [13], [14], [15], [16].

120

Змістовий модуль №2. Спеціальні методи математичного програмування в оптимізації процесів й прийняття рішень

Практичне заняття № 10

Тема 6. Цілочислове програмування

Мета заняття: Набути практичні навички розв'язання задач цілочислового програмування.

План заняття

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

2.Геометрична інтерпретація розв’язків на площині.

3.Розв’язання цілочислових задач лінійного програмування методом Гоморі.

Методичні рекомендації до практичного заняття

При виконанні завдань необхідно звернутися до методичних рекомендацій до самостійної роботи з даної теми.

Завдання для практичного заняття

Навчальні завдання

2. Знайти розв’язок задачі

Z = −3x1 +5x2 + 4x3 → max

за умов

5x1 +3x2 ≤13,

4x1 −2x2 + x3 ≤ 7,

61 +4x2 ≤15,

x1, x2 , x3, x4 ≥ 0, i цілі.

Розв'язання. Введемо в систему обмежень додаткові невідомі x4 , x5 , x6 :

121

5x1 +3x2 + x4 =13,

4x1 −2x2 + x3 + x5 = 7,61 +4x2 + x6 =15,

x1,..., x6 ≥ 0.

Хід розв'язування задачі відображено в табл. 6. У рядках 1-12 подано розв’язування задачі симплексним методом і отримано

	нецілочисловий											оптимальний											план		Xr* = (0;3		3	;4	1	;0;10		1	;0) ,
	Z (Xr* )=36																									4		3			6
								1		. Побудуємо									додаткове					обмеження.		Знайдемо					дробові
							12
	частини					чисел,						які				розташовані								В-стовпці		в		рядках			9-11:
	13			=	1	,			61			=	1		,	15					=	3	.	Для	побудови				правильного
					3								6									4
	3									6						4
	обмеження виберемо число																	15			,	у якого дробова частина найбільша і
																			4

запишемо дробові частини коефіцієнтів рівняння, розташованих у рядку

		3		=	1	,		1		=	1
	11:											. Отримуємо правильне обмеження як
		2			2			4			4

нерівність

34 ≤ 12 x1 + 14 x6 ,

а, ввівши додаткову невідому x7 , – як рівняння

	−	3	≤ −	1	x	−	1	x	6	+ x	7	.	(35)
		4		2			4
					1

Долучаємо це рівняння до системи обмежень (35).

Розширюємо симплексну таблицю, записавши в додатковому рядку 13 коефіцієнти рівняння (35). А в додатковому стовпці (у рядках 9,

10, 11, 13) – компоненти вектора A7 = (0;0;0;1) , який відповідає

122

невідомій x7 . У запис цільової функції аргумент x7 входитиме з коефіцієнтом c7 = 0 .

Далі до розв’язування застосовуємо двоїстий симплексний метод. Доповнюємо таблицю рядком 14, за допомогою якого визначаємо в

		−	1
	рядку 13 розв’язувальний елемент			, в рядках 15-19 записуємо
			4

результат відповідного симплексного перетворення і знаходимо новий

	оптимальний план Xr	1* = (0;3;	13		;0;	26	;3) ,	Z (Xr	1* )= 32	1		. Оскільки
				3		3				3

план Xr1* не цілочисловий, то алгоритм пошуку цілочислового розв’язку потрібно застосувати повторно. Для побудови правильного обмеження

вибираємо компоненту x3 = 133 плану Xr1*, яка знаходиться в В-

стовпці в рядку 15. Коефіцієнти відповідного правильного обмеження запишемо в додатковому рядку 20 (як від’ємні дробові частини чисел, що

	розташовані в	рядку	15),			а	компоненти	додаткового		вектора
	A8 = (0;0;0;0;1)	– в додатковому стовпці для невідомої								x8 . Далі
	вводимо рядок	21, за	допомогою якого у					рядку	20	виділяємо
				1
	розв’язувальний	елемент	−				результат відповідного		симплексного
				3

перетворення записуємо в рядках 22-27. З них отримуємо оптимальний цілочисловий розв’язок початкової задачі X 0 = (0;3;4) , Z (X 0 )= 31.

Завдання для самостійного розв’язання

2. Розв`язати задачу цілочислового лінійного програмування.

	2x		+		4x		≤17
2.1. z = x1 + 4x2		1				2
	→ max за обмежень 10x1 +3x2 ≤15.
	x , x			2	≥ 0,цілі
		1

123

	x1 + 2x2			≤16
		2x2		≥ 2
2.2. z = 2x1 + x2	x1 +				.
	→ max за обмежень
	2x1 + x2			≤16
	x , x	2	≥ 0,цілі
	1

			2x1+2x2 ≤ 7
2.3.	z =x1+2x2 → max	за обмежень				−5x2 ≤9 .
			4x1
				,x2 ≥ 0,цілі
			x1
			3x1+5x2 ≤11
2.4.	z =8x1+6x2 → max	за обмежень				+x2 ≤8 .
			4x1
				,x2 ≥ 0,цілі
			x1
			2x			+ 4x			− 7	≤ 0
2.5.	z = x1 + 4x2 → min	за обмежень		1				2
			10x1 + 3x2 ≤15 .
			x x		2		≥ 0,цілі
			1

Питання для самоконтролю

1.Сформулюйте алгоритм Гоморі розв’язування цілочислових задач ЛП.

2.Сформулюйте метод віток і меж розв’язування цілочислових задач ЛП.

Бібліографічний список до практичного заняття

[1], [3], [4], [5], [6], [7], [8], [10], [13], [14], [15], [16].

124

Таблиця 4.6

	Базис	Сб		В								-3							5	4	0						0	0					0	0
												x1							x 2	x 3		x 4					x 5		x 6				x 7	x 8
	x 4	0					13								5				0	3			1				0			0
	x 5	0							7						4				-2	1			0				1			0
	x 6	5					15								6				4	0			0				0			1
		j							0						3				-5	-4			0				0			0
	x 4	0					13								5				0	3			1				0			0
	x 5	0		29											7				0	1			0				1			1
							2																							2
	x 2	5						15								3			1	0			0				0			1
							4								2															4
		j						75					21						0	-4			0				0			5
							4					2																		4
	x 3	4					13									5			0	1				1			0			0			0
							3								3								3
	x 5	0						61				16							0	0		−	1				1			1			0
								6							3									3						2
	x 2	5		15											3				1	0			0				0			1			0
							4									2														4
		j		36				1				17				1			0	0	1			1			0	1		1			0
							12								6								3							4
	x 7	0			−				3			−				1			0	0			0				0		−	1			1
									4						2															4
	−d j	aij		103																										5
							2
	x 3	4						13									5		0	1				1			0			0			0	0
							3								3								3
	x 5	0					26						13						0	0		−		1			1			0			2	0
							3								3								3
	x 2	5							3						1				1	0			0				0			0			1	0
	x 6	0							3						2				0	0			0				0			1			-4	0
		j		32						1		14				2			0	0			4				0			0			5	0
									3						3								3
	x 8	0				−				1		−				2			0	0		−		1			0			0			0	1
									3						3								3
	−d j	aij										22											4
	x 3	4							4						1				0	1			0				0			0			0	1
	x 5	0							9						5				0	0			0				1			0			2	-1
	x 2	5							3						1				1	0			0				0			0			1	0
	x 6	0							3						2				0	0			0				0			1			-4	0
	x 4	0							1						2				0	0			1				0			0			0	-3
		j					31					12							0	0			0				0			0			5	4

125

Практичне заняття № 11 Тема 7. Нелінійні оптимізаційні моделі економічних систем

Мета заняття: Набути практичні навички розв'язання задач нелінійного програмування графічним методом.

План заняття

1.Постановка задач дробово-лінійного програмування (ДЛП).

2.Основні методи розв’язування задач ДЛП.

3.Розв’язання задач ДЛП графічним методом.

4.Розв’язання задач ДЛП графічним методом.

5.Розв’язання задач ДЛП зведенням до ЗЛП.

Методичні рекомендації до практичного заняття

При виконанні завдань необхідно звернутися до методичних рекомендацій до самостійної роботи з даної теми.

Завдання для практичного заняття

Навчальні завдання

1. Розв'язати графічно задачу дробово-лінійного програмування:

Z = 5x1 − 2x2 → max(min) 2x1 + x2

за умов

2x1 + 3x2 ≥12,

− x1 + 2x2 ≤ 6,2x1 − 2x2 ≤ 8,

x ≥ 0, j =1,2.

j

Розв'язання. Побудуємо на площині область допустимих розв'язків задачі — трикутник АВС (рис. 3)

126

Рис. 3.

Цільова функція задачі являє собою пряму, яка обертатиметься навколо початку системи координат залежно від змінюваних параметрів x1, x2 так, що точки А і С будуть точками максимуму і мінімуму функції.

Виразимо x

2

із цільової функції: x

2

= x

5 − 2Z

.

1

Z + 2

Кутовий коефіцієнт цільової функції RZ =

5 −2Z

.

Z +2

Розглянемо похідну

∂R

5 −

2Z

′

(5 +

′

′

9

Z

=

2Z ) (Z + 2) −

(Z + 2) (5 − 2Z )

=

=

(Z + 2)2

(Z + 2)2

∂Z

Z

+ 2

Оскільки при будь-якому значенні Z вона від'ємна, то функція RZ є

спадною (зі зростанням Z кутовий коефіцієнт RZ

зменшується), а графік

цільової функції обертатиметься навколо початку координат за годинниковою стрілкою. Отже, точка С є точкою максимуму, а точка А —

	мінімуму досліджуваної задачі.
	Знайдемо координати цих точок.
	2x		+ 3x		=12,			6			24
	Точка А:	1		2		x1	=		, x2	=
		− x1 + 2x2 = 6.						7			7
						127

Точка А має координати (6/7; 24/7).

	2x		+ 3x		=12,			9
	Точка С: :	1		2		x1	=		, x2 =1.
		2x1 − x2			= 8.			2

Точка С має координати (9/2; 1).

Знайдемо значення цільової функції в цих точках:

Z A = −12 ; ZC = 2041

Відповідь: максимум досягається в точці С, а мінімум — у точці А. 2. Задача про рентабельність підприємства. Для виготовлення двох видів виробів П1 і П2 на підприємстві використовують чотири типи обладнання. У таблиці вказано час обробки одиниці виробу кожного виду на обладнанні різного типу, а також витрати, пов’язані з виготовленням одиниці продукції кожного виду. Обладнання типу І повинно працювати не менше ніж 36 год., а типу ІІ, ІІІ і ІV відповідно не більше ніж 70, 30 і 36 год. Скільки виробів кожного виду потрібно запланувати до випуску, щоб їх собівартість була найменшою?

	Вироби	Час використання обладнання, год.
		П1	П2
	Тип І	6	6
	Тип ІІ	10	7
	Тип ІІІ	6	0
	Тип ІV	0	9
	Витрати на виробництво, од.	4	3

Розв’язання. Нехай на підприємстві планують виготовляти x1

одиниць виробів виду П1 і x2 одиниць – другого виду П2 . Тоді взагалі витрати на їх виробництво складають 4 x1 + 3 x2 , а собівартість одного виробу –

F = 4x1 +3x2 . x1 + x2

Згідно з даними таблиці обладнання типу І працюватиме (6 x1+6 x2 ) год.,

типу ІІ – (10 x1+7 x2 ) год., типу ІІІ - 6 x1 год. і типу ІV - 9 x2 год. Беручи

128

до уваги обмеження на загальний час використання обладнання і економічний зміст змінних x1 і x2 , отримуємо систему нерівностей

	6x1 +6x2 ≥ 36,
10x1 +7x2 ≤ 70,
	6x	≤ 30,
	1
	9x2	≤ 36,

x1 , x2 ≥0

Математична модель задачі має вигляд:

F =

4x1 +3x2

→ min

(36)

x + x

2

1

за обмежень

x1 + x2 ≥ 6,

10x1 +7x2 ≤ 70,

(37)

0 ≤ x

≤ 5,

1

0 ≤ x2 ≤ 4,

Розв’язання. За допомогою замін

y0

1

, y j = y0 x j , x j

y j

=

=

, j =1,2,

(38)

x1

y0

+ x2

і співвідношення y1 + y2 =1 зведемо задачу (36)- (37) до задачі

Ф = 4y1 + 3y2 → min

y

+ y

2

≥ 6y

0

,

1

10y1 + 7 y2 ≤ 70y0 ,

≤5y0

y1

y

2

≤ 4 y

0

,

+ y2

=1,

y1

y0 ≥ 0, y1 ≥ 0, y2 ≥ 0.

Очевидно, що ця система обмежень еквівалентна системі

129