информатика

Для знаходження коефіцієнтів

	pq

при вільних змінних зіставимо кожному

пункту відправлення

Ai

деяку величину

u	i

(i

1,2,..., m)

, яку назвемо потенціалом

пункту Ai , і кожному пункту призначення		B j	величину v j потенціал пункту B j
. Зв'яжемо ці величини рівністю uk vl	ckl ,		де ckl вартість перевезення однієї
тонни вантажу з пункту Ak в пункт	Bl .	Доводиться, що сукупність рівнянь

u	k	v	l

c	kl

, складених для усіх базисних змінних, складає спільну систему ліній-

них рівнянь, причому значення однієї із змінних можна задавати довільно, і тоді значення інших змінних знаходяться з системи однозначно. Позначимо для віль-

них змінних суму відповідних потенціалів через c pq , тобто u p vq		c pq , і назвемо
/		/
її непрямою вартістю (на відміну від цієї вартості	c pq ). Тоді коефіцієнти при

вільних змінних в співвідношенні L pq x pq 0 визначаються за допомогою

pq

рівності

	pq

c	pq

	c	/
		pq

.

Якщо усі величини

	pq

ненегативні, то початкове рішення є оптимальним.

Якщо ж серед них є негативні, то переходимо до наступного базису шляхом збільшення члена з негативним коефіцієнтом, залишаючи інші змінні рівними нулю.

Скористаємося викладеними загальними поняттями і продовжимо рішення нашої задачі. Ми отримали початкове опорне рішення (дотримуючись правила

"мінімального елементу"): x11 60 , x12 0 , x13 90 , x21 0 , x22 70 , x23 20 ,

L

1020	. Для знаходження потенціалів необхідно вирішити систему
	u1 v1 c11 6 ,	u1 v3 c13 4 ,	u2 v2 c22 2 ,	u2 v3 c23

8

.

v	3

Значення одного з невідомих задамо довільно, наприклад											u1 1. Тоді
3 , u2 5, v2	3	. Далі обчислюємо непрямі вартості c pq :
									/
		c/	u v	2	2 ,	c / u	2	v 10 .
		12	1			21			1
Підрахуємо тепер різниці pq c pq c pq :
					/
12	c12	/	( 2) 12 ,						/	12 10 2 .
		c12 10					21		c21 c21

v1

5

,

Отже, вираження

L

через вільні змінні має вигляд

L 1020 12x12 2x21

. Се-

ред коефіцієнтів при змінних в правій частині немає негативних. Значить, початкове опорне рішення є оптимальним.

Вирішимо тепер це ж завдання за умови, що початкове рішення отримане за правилом "північно-західного кута", тобто x11 60 , x12 70 , x13 20 , x23 90 ,

L

1860

. Для знаходження потенціалів необхідно вирішити систему

	u1 v1 c11 6 ,		u1 v2 c12 10 ,
Вважаючи u1 1, отримаємо v1 5, v2
вартості	c pq :	c21 u2	v1 10 ,	c22 u2
	/	/		/

u1 v3

c13

4

,

u2

v3

c23

9 , v3 3 , u2 5. Обчислюємо v2 14 . Підрахуємо тепер

8 .

непрямі

різниці

pq c pq c /pq :

		c		c
				/
	21		21	21

12 10

2

,

22 c22 c22/ 2 14 12 .

Отже, вираження L через вільні змінні має вигляд L 1860 2x21 12x22 . Серед коефіцієнтів при змінних в правій частині негативний при x22 , отже, можна

10

спробувати зменшити

L , збільшивши

x22

(зберігши нульове значення

x21 ). Пок-

ладемо x22 . Оскільки суми значень невідомих по рядках і стовпцях повинні залишатися незмінними, треба виробити наступний балансовий перерахунок:

			60		70	20
					.		90
Додавання		до	x22	компенсується відніманням			з x12	, а це у свою чергу -
збільшенням	до	x13	і так далі до тих пір, поки ми не повернемося назад до							x22 .

Обходячи клітини по пунктирній ламаній лінії, в одній з вершин якої знаходиться вільна змінна x22 , а в інших вершинах - базисні змінні (причому не обов'язкове усе), ми отримаємо так званий цикл перерахунку (ламана називається циклом), що

відповідає вільній клітині			x22	. Як видно з таблиці, для позитивності змінних
можна збільшити до		70	, тоді отримаємо друге опорне рішення:
		60			0		90
		0			70		20
тобто x11 60 , x12 0 ,		x13 90 ,		x21 0 , x22 70,		x23 20 .

Значення функції	L для нього складає L 1860 12 70 1020
оптимальне рішення.
Таким чином, правила обчислень за методом потенціалів
ступного.
1. Знаходять потенціали u k		і vl	усіх пунктів відправлення
Bl .

, тобто отримали

зводяться до на-

Ak	і призначення

2.Вибирають яку-небудь вільну змінну, для якої сума потенціалів строга більше відповідної вартості, це відповідає елементу з негативним коефі-

цієнтом при вільній змінній в правій частині функції

L

.

3.Для вибраної в п. 2 змінною знаходять відповідний нею цикл перерахунку і виробляють зрушення по цьому циклу. Це зрушення призводить до нового допустимого рішення.

4.Вищезгадані операції 1-3 повторюють до тих пір, поки не отримають оптимальний базис, тобто ненегативні коефіцієнти при вільних змінних в

правій частині лінійної функції

L

.

11

Індивідуальне завдання №1.

1. Згідно варіанту обрати умову задачі:

Останні	00,	01,	02,	03,	04,	05,	06,	07,	08,	09,
цифри	30,	31,	32,	33,	34,	35,	36,	37,	38,	39,
заліко-	60,	61,	62,	63,	64,	65,	66,	67,	68,	69,
вої кни-	90	91	92	93	94	95	96	97	98	99
жки
Номер	01	02	03	04	05	06	07	08	09	10
варіанту
Останні	10,	11,	12,	13,	14,	15,	16,	17,	18,	19,
цифри	40,	41,	42,	43,	44,	45,	46,	47,	48,	49,
заліко-	70	71	72	73	74	75	76	77	78	79
вої кни-
жки
Номер	11	12	13	14	15	16	17	18	19	20
варіанту
Останні	20,	21,	22,	23,	24,	25,	26,	27,	28,	29,
цифри	50,	51,	52,	53,	54,	55,	56,	57,	58,	59,
заліко-	80	81	82	83	84	85	86	87	88	89
вої кни-
жки
Номер	21	22	23	24	25	26	27	28	29	30
варіанту

2.Сформулювати блок-схему розв’язання задачі

3.Визначити необхідні параметри в табличному процесорі MS Excel

4.Виконати перевірку отриманих результатів в MathCAD

5.Зробити висновок.

12

Вихідні дані для виконання індивідуального завдання

При будівництві земляного полотна автомобільної дороги є можливість для зведення насипу (5 ділянок з потребами (м3) В1, В2, В3, В4, В5) використовувати ґрунт виїмки (4 ділянки з запасами (м3) А1, А2, А3, А4). Собівартість транспортування наведена у таблиці. Визначити план перевезень ґрунту, забезпечивши мінімальні загальні транспортні витрати. Як зміниться план перевезень при введенні обмеження на об’єм кузова самоскида?

Варіант			Матриця					Ресурси
			перевезень
		собівартостей						Аі	Ві
	7		5	4	8		9	250	200
	9		6	7	5		4	300	250
01									300
	8		4	6	7		5	350	150
	4		7	8	9		6	200	200
	7		8	9	4		5	300	250
	6		5	4	8		9	200	230
03									270
	5		4	7	6		8	250	100
	9		7	8	5		4	150	50
	6		7	8	9		5	200	250
	7		5	6	4		8	250	230
05									270
	5		4	7	8		9	300	100
	4		9	8	7		6	250	150
	8		6	5	4		7	200	150
	6		4	7	8		5	250	100
07									260
	5		7	8	9		4	320	290
	4		9	6	7		5	230	200

Варіант			Матриця					Ресурси
			перевезень
		собівартостей						Аі	Ві
	7		6	8	9		5	300	250
	5		4	7	6		8	250	200
02									300
	6		5	4	8		7	350	200
	8		9	5	4		6	200	150
	7		9	8	5		4	300	250
	6		8	5	4		9	150	230
04									170
	5		4	6	7		8	200	100
	9		5	4	6		7	250	150
	6		8	7	5		9	200	150
	7		6	5	8		4	270	230
06									270
	5		7	4	9		8	300	250
	4		5	6	7		5	230	100
	8		7	5	4		6	320	250
	7		6	4	5		8	250	230
08									270
	9		5	6	7		4	230	150
	4		8	7	6		5	200	100

13

При будівництві об’єктів ЄВРО-2012 на будівельні майданчики (5 майданчиків з потребами (м3) В1, В2, В3, В4, В5) необхідно доставити бетонну суміш (4 заводи з потужностями (м3) А1, А2, А3, А4). Собівартість транспортування наведена у таблиці. Визначити план перевезень суміші, забезпечивши мінімальні загальні транспортні витрати. Як зміниться план перевезень при введенні обмеження на об’єм одного транспортуючого бетонозмішувача?

Варіант			Матриця					Ресурси
			перевезень
		собівартостей						Аі	Ві
	8		4	5	6		7	250	150
	7		5	4	8		6	200	260
09									240
	6		7	8	4		5	330	250
	5		8	6	7		4	220	100
	6		9	4	5		7	250	220
	8		7	6	4		5	350	280
11									200
	7		8	9	6		4	340	270
	5		4	7	8		6	260	230
	5		7	9	6		4	260	220
	6		8	5	4		7	340	180
13									300
	7		5	8	9		6	360	270
	8		4	6	5		9	240	230
	5		9	8	6		4	280	230
	4		7	5	8		6	320	270
15									300
	7		8	9	4		5	360	220
	6		5	4	7		8	240	180

Варіант			Матриця					Ресурси
			перевезень
		собівартостей						Аі	Ві
	8		5	7	4		6	200	150
	7		4	8	5		9	250	100
10									240
	5		7	4	8		6	220	260
	9		8	6	7		5	330	250
	6		5	9	4		7	350	280
	7		8	5	6		4	250	220
12									270
	5		4	7	8		9	260	230
	8		6	4	5		6	340	200
	5		8	6	9		4	360	300
	6		7	8	5		6	340	270
14									230
	7		6	5	8		9	260	220
	8		5	4	7		6	240	180
	5		7	8	4		6	320	300
	4		8	7	6		5	360	270
16									230
	7		9	6	5		4	280	220
	6		4	5	7		8	240	180

14

	4	6	8	9	7	350	230
	5	7	9	6	4	330	280
17							270
	6	5	7	4	8	320	220
	8	4	4	7	5	300	300
	4	9	6	7	8	250	220
	5	6	8	4	9	330	270
19							230
	6	5	4	9	6	320	280
	7	8	9	5	4	300	200
	6	7	8	9	5	200	250
	7	5	6	4	8	250	230
21							270
	5	4	7	8	9	300	100
	4	9	8	7	6	250	150

	4	8	5	9	6	330	300
	5	6	7	4	8	320	280
18							270
	6	5	4	7	9	350	230
	8	7	9	5	4	300	220
	4	5	6	8	7	340	280
	6	7	8	9	5	310	270
20							230
	8	6	5	4	9	300	220
	7	4	9	5	6	250	200
	6	8	7	5	9	200	150
	7	6	5	8	4	270	230
22							270
	5	7	4	9	8	300	250
	4	5	6	7	5	230	100

15

Асфальтобетонна суміш (4 заводи з потужностями (м3) А1, А2, А3, А4) доставляється на об’єкти будівництва (5 об’єктів з потребами (м3) В1, В2, В3, В4, В5) з відомою собівартістю транспортування. Визначити план перевезень суміші, забезпечивши мінімальні загальні транспортні витрати. Як зміниться план перевезень при введенні обмеження на об’єм кузова транспортуючого самоскиду?

	Варіант			Матриця					Ресурси
				перевезень
			собівартостей						Аі	Ві
		5		9	8	6		4	280	230
		4		7	5	8		6	320	270
	23									300
		7		8	9	4		5	360	220
		6		5	4	7		8	240	180
		6		9	4	5		7	250	220
		8		7	6	4		5	350	280
	25									200
		7		8	9	6		4	340	270
		5			7	8		6	260	230
		8		4	5	6		7	250	150
		7		5	4	8		6	200	260
	27									240
		6		7	8	4		5	330	250
		5		8	6	7		4	220	100
		8		6	5	4		7	200	150
		6		4	7	8		5	250	100
	29	5		7	8	9		4	320	210
										290
		4		9	6	7		5	230	250

	Варіант				Матриця								Ресурси
					перевезень
				собівартостей									Аі		Ві
			5		7		8	4			6		320		300
			4		8		7	6			5		360		270
	24														230
			7		9		6	5			4		280		220
			6		4		5	7			8		240		180
			6		5		9	4			7		350		280
			7		8		5	6			4		250		220
	26														270
			5		4		7	8			9		260		230
			8		6		4	5			6		340		200
			8		5		7	4			6		200		150
			7		4		8	5			9		250		100
	28														240
			5		7		4	8			6		220		260
			9		8		6	7			5		330		250
			8		7		5	4			6		320		250
			7		6		4	5			8		250		230
	30		9		5		6		7		4		230		270
															150
			4		8		7		6		5		200		100

Приклад реалізації задачі в Excel наведено на рис. 1.1-1.2, в MathCAD на рис.

1.3.

16

Рис.1.1 – Приклад реалізації транспортної задачі в Excel (фрагмент 1)

17

Рис.1.2 – Приклад реалізації транспортної задачі в Excel (фрагмент 2)

18

Рис.1.3 – Приклад реалізації транспортної задачі в MathCAD

19