Опис методики рішення транспортної задачи

 

Рішення транспортної задачи розглядається на конкретному прикладі транспортної задачи на залізниці, у якій відшукується оптимальне розподілення товарного порожняка.

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

У таблиці 3.1. та 3.2. наведені умови задачи та питомі (на один товарний вагон) витрати на перегін.

У таблицы 3.1. вказано, що в пунктах S1, S2, S3, маємо залишки порожніх товарних вагонів у кількостях 9, 4 та 8 вагонів, відповідно, у пунктах D1, D2, D3, D4, D5 не вистачає, відповідно, 3, 5, 4, 6 та 3 вагонів. (для спрощення уявимо, що задача сбалансована, тобто сумарна кількість надлишкових вагонів дорівнюється сумарній кількості невистаючих вагонів).

 

Таблиця 3.1

Умови задачи

 

Пункти призначення	D1	D2	D3	D4	D5	Над - лишок
Пункти відправлення
S1	X11	X12	X13	X14	X15
S2	X21	X22	X23	X24	X25
S3	X31	X31	X33	X34	X35
Потреба

Таблиця 3.2

Питомі витрати

Пункти призначення	D1	D2	D3	D4	D5
Пункти відправлення
S1	С11 -10	С12 -20	С13 -5	С14 -9	С15 -10
S2	С21 -2	С22 -10	С23 -8	С24 -30	С25 -6
S3	С31 -1	С31 -20	С33 -7	С34 -10	С35 -4

 

У таблиці 3.2. наведени питомі витрати Cij на перегін одного порожнього вагона з пункту відправлення у пункт призначення J (i-строка, j-стовбець). Таким чином, треба визначити такі значення Xij (i=1, 2, 3; j=1, 2, 3, 4, 5) таблиці 3.1., щоб задовольнити наданим обмеженням та мінімізувати сумарні витрати.

 

МЕТОДИЧНІ ВКАЗІВКИ ДО ВИКОНАННЯ ЛАБОРАТОРНОЇ РОБОТИ

Для виконання пп.2.2, 2.3. необхідно ознайомитися із конспектом лекцій, вивчити методи лінійного програмування.

Для виконання пп.2.3., 2.4. необхідно отримати у викладача вихідні дані.

Отримати результати рішення на конкретних даних, отримати роздрук вихідних даних.

 

ЗМІСТ ЗВІТУ.

 

12.5.1 Мета роботи.

12.5.2 Опис метода рішення транспортної задачи.

12.5.3 Схема алгоритму.

12.5.4 Текст програми.

 

КОНТРОЛЬНІ ПИТАННЯ.

 

12.6.1 Сформулювати мету задачи лінійного програмування.

12.6.2 Методи рішення задач лінійного програмування на прикладі транспортної задачі.

12.6.3 Поняття цільової функції.

12.6.4 Принцип визначення обмежень у задачи лінійного програмування.

12.6.5 Поняття базисного рішення.

 

 

Додаток А

Експериментальні дані

Таблиця А.1 – Експериментальні дані

№	Y1	X1	Y2	X2	Y3	X3	Y4	X4	Y5	X5
	24.2	50.3	96.7	121.5	63.1	0.009	0.0	0.0	4.5	2.6
	22.3	42.7	102.3	130.3	56.7	0.007	0.011	0.012	0.0	0.0
	25.6	50.7	101.1	129.7	65.1	0.016	0.0	0.005	5.4	4.1
	24.8	47.9	100.3	127.1	63.9	0.016	0.010	0.0	4.8	3.1
	22.9	44.3	409.5	409.5	58.7	0.016	0.052	0.007	40.9	24.6
	22.9	43.1	89.5	108.7	55.5	0.017	0.078	0.007	18.8	7.7
	22.1	41.1	91.5	121.4	51.1	0.008	0.013	0.013	40.9	5.6
	22.9	42.7	94.7	233.1	55.1	0.007	0.0	0.0	40.9	6.4
	24.7	46.3	89.5	122.3	59.1	0.0	0.006	0.013	23.6	5.0
	23.2	44.3	90.3	110.3	56.7	0.007	0.013	0.010	9.3	5.7
	25.8	51.1	100.7	149.1	68.3	0.0	0.0	0.010	17.5	6.4
	26.0	51.1	109.1	150.3	67.5	0.009	0.0	0.0	4.9	3.2
	24.0	46.5	108.7	144.3	60.7	0.010	0.0	0.010	4.9	3.3
	23.9	47.9	106.7	147.1	60.7	0.007	0.0	0.011	6.0	5.9
	23.8	44.7	72.7	53.5	59.7	4.1	0.010	4.1	5.7	4.1
	21.9	40.7	98.7	125.5	58.3	0.0	0.0	0.012	5.1	3.3
	21.7	40.7	101.5	130.3	58.1	0.0	0.011	4.1	4.6	3.1
	22.6	42.7	102.3	134.3	60.7	0.016	0.013	0.0	5.1	3.4
	23.0	43.9	101.5	131.5	62.3	0.007	0.0	0.007	5.0	3.3
	22.3	41.5	102.3	133.5	58.1	0.011	0.0	0.012	4.6	2.9
	18.3	29.5	99.9	129.9	46.1	0.007	0.011	0.0	5.7	4.3
	19.7	31.5	102.3	135.5	49.1	0.0	0.006	0.007	4.8	3.0
	19.0	30.5	102.3	142.3	47.1	0.017	0.0	0.0	11.4	5.7
	17.6	28.3	102.3	147.1	43.3	0.0	0.009	0.007	17.2	6.4
	18.6	29.5	106.3	167.5	45.9	0.0	0.010	0.013	34.2	5.2
	24.5	47.7	97.3	122.7	65.7	0.017	0.010	0.0	4.5	2.8
	25.1	49.5	99.8	126.3	66.3	0.0	0.011	0.0	4.5	2.8
	24.3	47.5	100.7	127.9	64.7	0.0	0.007	0.013	4.5	2.8
	24.8	47.9	102.3	131.9	65.7	0.009	0.013	0.0	4.6	3.0
	26.1	51.1	102.3	133.5	70.3	0.010	0.0	0.013	4.7	3.0
	23.3	43.9	102.3	133.5	59.1	0.017	0.0	0.011	5.1	3.4
	24.7	47.1	101.5	132.7	63.1	0.0	0.0	0.012	11.1	7.6
	25.3	48.7	106.1	144.3	63.9	0.016	0.007	0.012	16.8	6.2
	22.3	42.1	109.3	143.5	55.9	0.014	0.007	0.012	5.9	4.2
	22.4	41.9	107.9	140.7	55.9	0.007	0.007	0.0	7.4	5.1

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

№	Y6	X6	Y7	X7	Y8	X8	Y9	X9	Y10	X10
	0.201	0.037	0.098	17.5	21.7	0.41	0.736	0.956	6.3	0.296
	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0
	0.215	0.042	0.123	18.6	22.1	0.484	0.618	0.802	6.3	0.484
	0.217	0.039	0.107	18.3	21.6	0.486	0.619	0.804	6.2	0.484
	0.217	0.034	0.089	17.5	20.4	0.488	0.62	0.804	5.8	0.488
	0.174	0.033	0.093	17.3	20.1	0.123	0.612	0.92	1.6	0.12
	0.179	0.031	0.097	17.6	20.1	0.488	0.62	0.797	6.1	0.486
	0.183	0.034	0.111	18.5	21.1	0.484	0.616	0.796	6.3	0.484
	0.173	0.037	0.093	17.9	21.3	0.485	0.618	0.794	8.0	0.485
	0.180	0.034	0.088	16.5	20.4	0.488	0.62	0.792	7.4	0.485
	0.223	0.040	0.115	18.0	21.9	0.495	0.628	0.8	6.2	0.342
	0.243	0.048	0.409	18.5	22.6	0.494	0.628	0.802	6.2	0.494
	0.246	0.041	0.131	17.8	21.3	0.493	0.625	0.802	6.4	0.49
	0.251	0.038	0.111	17.5	20.9	0.488	0.628	0.802	4.6	0.49
	4.1	0.011	0.013	40.9	40.9	0.432	0.744	1.068	6.3	0.0
	0.209	0.035	0.090	17.0	19.7	0.288	0.624	0.91	7.0	0.288
	0.219	0.037	0.1	17.2	19.9	0.489	0.621	0.795	6.6	0.488
	0.223	0.038	0.111	17.7	20.5	0.484	0.616	0.792	6.9	0.485
	0.223	0.037	0.095	17.4	20.3	0.484	0.617	0.793	7.8	0.482
	0.228	0.034	0.087	17.4	20.0	0.488	0.621	0.79	7.1	0.488
	0.219	0.027	0.058	16.2	17.7	0.444	0.736	1.015	6.1	0.444
	0.231	0.029	0.063	17.0	18.8	0.488	0.623	0.802	5.6	0.49
	4.1	0.028	0.06	16.5	18.1	0.488	0.622	0.801	6.0	0.488
	0.235	0.025	0.058	14.4	17.7	0.488	0.621	0.8	4.3	0.482
	0.235	0.028	0.059	17.3	18.7	0.49	0.623	0.8	6.1	0.491
	0.203	0.041	0.112	18.1	21.5	0.362	0.725	0.964	6.4	0.292
	0.211	0.039	0.105	18.2	21.8	0.488	0.622	0.792	6.1	0.489
	0.214	0.042	0.409	18.3	40.9	0.484	0.619	0.793	6.5	0.488
	0.221	0.044	0.134	18.3	21.7	0.487	0.619	0.793	6.6	0.487
	0.223	0.042	0.117	18.3	22.1	0.49	0.622	0.79	6.4	0.489
	0.222	0.037	0.101	18.1	21.3	0.439	0.697	1.017	6.0	0.438
	0.215	0.041	0.409	19.4	23.0	0.488	0.621	0.8	5.8	0.487
	0.237	0.037	0.097	18.7	22.5	0.486	0.621	0.8	6.1	0.488
	0.244	0.034	0.089	17.9	20.5	0.488	0.621	0.8	6.1	0.488
	0.237	0.037	0.104	17.9	20.5	0.49	0.623	0.795	6.2	0.49

 

 

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

№	Y11	X11	Y12	X12	Y13	X13	Y14	X14	Y15	X15
	0.628	0.788	0.549	0.674	0.753	8.6	0.772	0.004	0.0	2.4
	0.0	0.0	0.0	0.0	0.0	0.0	2.4	0.034	6.2	19.4
	0.616	0.749	0.517	0.661	0.747	8.5	1.0	0.056	7.7	40.9
	0.616	0.75	0.548	0.674	0.755	8.6	0.976	0.059	7.5	40.9
	0.616	0.749	0.549	0.674	0.755	8.6	0.951	0.054	11.5	40.9
	0.57	0.778	0.543	0.669	0.747	9.0	0.87	0.004	0.0	2.2
	0.616	0.745	0.543	0.669	0.751	8.9	1.2	0.058	8.8	26.6
	0.616	0.747	0.495	0.642	0.735	8.7	1.3	0.055	5.2	26.2
	0.613	0.744	0.491	0.642	0.735	8.7	1.2	0.057	9.5	21.7
	0.616	0.744	0.491	0.641	0.735	5.7	1.1	0.056	2.9	23.1
	0.623	0.75	0.549	0.676	0.759	8.6	1.2	0.057	8.7	11.6
	0.622	0.752	0.507	0.657	0.747	8.4	1.2	0.061	7.5	28.4
	0.62	0.752	0.503	0.656	0.747	8.5	1.2	0.061	20.5	27.5
	0.622	0.751	0.503	0.651	0.743	8.5	1.3	0.056	11.7	28.1
	0.184	0.848	0.547	0.675	0.755	8.6	0.915	0.004	0.0	2.3
	0.569	0.776	0.543	0.669	0.75	9.0	0.853	0.004	0.0	2.8
	0.617	0.746	0.493	0.645	0.735	8.7	1.1	0.061	8.0	40.9
	0.161	0.744	0.541	0.667	0.749	9.0	1.2	0.06	0.95	40.9
	0.612	0.745	0.487	0.643	0.735	8.8	1.1	0.063	6.4	40.9
	0.616	0.744	0.525	0.661	0.743	9.0	1.2	0.061	20.6	40.9
	0.642	0.808	0.511	0.653	0.735	8.2	0.758	0.003	0.0	2.2
	0.618	0.749	0.551	0.677	0.759	8.5	0.927	0.056	5.6	29.7
	0.617	0.749	0.527	0.667	0.754	8.3	0.967	0.059	5.9	30.1
	0.617	0.749	0.51	0.658	0.747	8.2	0.975	0.065	8.1	28.6
	0.62	0.749	0.511	0.661	0.751	8.2	0.923	0.056	7.3	28.9
	0.617	0.789	0.546	0.671	0.751	8.8	0.679	0.004	0.0	2.5
	0.618	0.745	0.487	0.646	0.741	8.6	0.389	0.052	10.6	40.9
	0.616	0.744	0.481	0.638	0.734	8.5	0.973	0.059	6.2	40.9
	0.616	0.746	0.503	0.654	0.743	8.6	1.0	0.061	7.3	40.9
	0.618	0.745	0.491	0.646	0.741	8.6	1.0	0.051	13.3	40.9
	0.628	0.797	0.529	0.668	0.751	8.3	0.647	0.004	0.0	2.5
	0.616	0.748	0.551	0.677	0.759	8.4	0.821	0.058	9.0	29.5
	0.616	0.748	0.497	0.653	0.745	8.0	0.807	0.063	5.0	29.6
	0.618	0.747	0.503	0.652	0.743	8.2	0.815	0.067	4.2	29.7
	0.618	0.746	0.503	0.654	0.746	8.1	0.823	0.057	5.1	29.3

 

 

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

№	Y16	X16	Y17	X17	Y18	X18	Y19	X19	Y20	X20
	19.7	81.9	110.5	1.8	4.7	4.0	6.4	27.0	81.9	113.4
	0.0	71.5	105.7	2.0	0.0	0.0	0.0	0.0	81.9	135,4
	17.3	81.9	107.3	2.1	4.8	3.9	6.4	26.3	81.9	108.3
	17.1	81.9	97.1	2.2	5.2	4.0	6.4	25.9	81.9	98.0
	16.5	81.9	123.7	2.3	4.3	4.0	6.4	26.6	81.9	125.9
	18.0	81.9	409.5	4.1	0.0	0.0	7.3	7.3	81.9	409.5
	16.9	81.9	409.5	4.1	0.8	0.8	6.7	8.1	81.9	345.1
	16.8	81.9	409.5	4.1	0.4	0.3	6.8	7.3	81.9	409.5
	15.9	81.9	409.5	4.1	0.0	0.0	8.2	8.2	81.9	409.5
	15.9	81.9	409.5	4.1	0.0	0.0	4.3	4.3	81.9	409.5
	15.4	81.9	102.3	2.1	5.1	4.0	6.4	26.8	81.9	107.0
	16.2	81.9	108.7	2.3	4.9	4.0	6.4	26.6	81.9	111.7
	16.3	81.9	195.3	3.3	2.5	3.8	6.5	17.9	81.9	176.7
	14.9	81.9	145.7	2.3	3.6	4.2	6.4	28.9	81.9	137.3
	16.8	81.9	123.9	1.9	4.2	4.0	6.4	27.4	81.9	125.8
	17.2	81.9	409.5	4.1	0.0	0.0	7.2	7.2	81.9	409.5
	15.5	81.9	336.3	4.1	1.2	1.5	6.6	9.5	81.9	265.5
	15.8	81.9	409.5	4.1	0.0	0.0	7.1	7.1	81.9	409.5
	15.8	81.9	409.5	4.1	0.0	0.0	8.2	8.2	81.9	409.5
	15.7	81.9	409.5	4.1	0.0	0.0	7.2	7.2	81.9	409.5
	18.4	81.9	83.7	1.3	6.0	4.2	6.3	24.5	81.9	88.3
	17.2	79.0	78.5	1.5	6.3	4.2	6.2	25.3	71.0	77.3
	17.0	78.7	78.6	1.6	6.2	4.2	6.3	24.2	81.9	80.7
	17.8	81.9	107.9	1.9	4.7	4.1	6.3	24.6	81.9	113.1
	15.5	81.9	104.6	1.0	1.0	2.8	6.3	16.2	81.9	110.5
	15.4	81.9	182.3	2.4	2.8	4.0	6.6	19.0	81.9	185.6
	15.8	81.9	134.3	2.5	3.9	4.0	6.5	27.7	81.9	135.1
	13.2	81.9	409.5	4.1	0.5	0.4	6.7	7.3	81.9	329.8
	15.9	81.9	409.5	4.1	0.04	0.01	6.8	6.8	81.9	409.5
	15.1	81.9	132.5	2.7	5.6	3.7	6.5	27.5	76.7	79.1
	18.4	61.4	68.2	1.3	7.2	4.0	6.2	23.7	71.4	71.0
	17.3	80.6	85.9	1.8	6.1	4.0	6.2	21.5	81.9	86.3
	16.9	59.6	65.6	1.7	7.2	4.0	6.2	23.1	63.4	66.9
	16.5	54.1	60.7	1.7	7.1	4.0	6.2	22.1	57.6	60.9
	15.0	68.5	70.3	1.7	7.2	4.0	6.2	25.3	72.7	73.5

 

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

№	Y21	X21	Y22	X22	Y23	X23	Y24	X24	Y25	X25
	1.2	0.663	0.725	0.942	0.658	0.722	0.985	27.3	6.5	3.5
	1.4	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0
	1.3	0.666	0.73	0.938	0.66	0.735	1.3	27.1	6.5	3.6
	1.6	0.664	0.73	0.934	0.66	0.724	1.0	26.2	6.5	3.5
	1.6	0.665	0.728	0.929	0.66	0.728	1.1	28.9	6.5	3.6
	4.1	0.645	0.71	0.904	0.648	0.714	1.1	7.5	7.5	0.0
	3.3	0.649	0.717	0.921	0.649	0.722	1.2	8.3	7.0	0.74
	3.9	0.648	0.715	0.922	0.648	0.72	1.2	7.1	7.0	0.0
	4.1	0.653	0.718	0.909	0.65	0.724	1.1	8.4	8.4	0.0
	4.1	0.653	0.718	0.912	0.65	0.72	1.0	8.0	8.0	0.0
	1.1	0.668	0.736	0.952	0.661	0.74	1.3	27.4	6.4	3.6
	1.1	0.672	0.738	0.953	0.668	0.748	1.4	26.7	6.4	3.6
	1.7	0.664	0.731	0.941	0.662	0.736	1.3	17.6	6.6	3.4
	1.2	0.672	0.737	0.96	0.668	0.748	1.4	22.4	6.5	3.4
	1.0	0.668	0.736	0.944	0.666	0.742	1.4	23.7	6.5	3.5
	4.1	0.654	0.716	0.9	0.649	0.715	0.934	7.3	7.3	0.0
	2.4	0.652	0.72	0.936	0.652	0.726	1.2	9.1	6.7	1.3
	4.1	0.65	0.717	0.922	0.651	0.72	1.1	7.3	7.2	0.0
	4.1	0.634	0.705	0.912	0.632	0.705	0.978	8.2	8.2	0.0
	4.1	0.646	0.712	0.917	0.644	0.712	0.993	7.3	7.3	0.0
	0.983	0.672	0.736	0.932	0.666	0.732	1.1	25.1	6.4	3.6
	1.1	0.672	0.736	0.94	0.666	0.736	1.3	25.2	6.4	3.7
	1.1	0.672	0.736	0.946	0.666	0.738	1.3	24.2	6.4	3.7
	1.4	0.669	0.734	0.943	0.666	0.736	1.2	25.2	6.4	3.7
	1.3	0.668	0.732	0.936	0.666	0.733	1.2	28.2	6.4	3.7
	1.7	0.656	0.721	0.912	0.656	0.656	0.943	19.6	6.8	3.7
	1.7	0.656	0.721	0.919	0.65	0.65	0.974	28.7	6.7	3.6
	4.1	0.65	0.718	0.92	0.65	0.65	0.982	7.4	6.9	0.29
	4.1	0.656	0.72	0.922	0.656	0.656	0.98	6.9	6.9	0.0
	0.323	0.626	0.704	0.96	0.594	0.594	0.966	29.1	6.5	4.3
	0.915	0.668	0.73	0.928	0.66	0.724	0.949	24.1	6.3	3.7
	1.2	0.666	0.73	0.936	0.66	0.724	1.0	25.4	6.4	3.7
	1.1	0.669	0.732	0.94	0.66	0.726	1.0	23.7	6.3	3.7
	1.1	0.67	0.734	0.941	0.66	0.728	1.0	22.5	6.3	3.7
	1.1	0.667	0.73	0.933	0.658	0.724	0.982	25.8	6.4	3.7

 

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

№	Y26	X26	Y27	X27	Y28	X28	Y29	X29	Y30	X30
	6.5	82.8	94.6	1.2	0.648	0.709	0.882	0.64	0.703	0.955
	0.0	81.9	123.9	1.6	0.0	0.0	0.0	0.0	0.0	0.0
	6.7	66.6	90.1	1.4	0.0	0.0	0.0	0.0	0.0	0.0
	6.8	71.6	84.1	1.5	0.648	0.712	0.893	0.637	0.704	0.968
	6.5	68.8	81.6	1.3	0.644	0.708	0.891	0.637	0.706	1.1
	0.0	81.9	409.5	4.1	0.176	0.384	0.869	0.174	0.389	1.1
	1.0	81.9	377.1	3.7	0.628	0.694	0.906	0.626	0.698	1.2
	0.0	81.9	409.5	4.1	0.626	0.693	0.877	0.624	0.697	1.1
	0.0	81.9	409.5	4.1	0.624	0.69	0.866	0.624	0.696	1.1
	0.0	81.9	409.5	4.1	0.626	0.692	0.869	0.624	0.693	0.957
	6.8	81.9	91.7	1.3	0.653	0.716	0.904	0.644	0.72	1.3
	6.6	81.9	98.3	1.5	0.652	0.717	0.904	0.648	0.726	1.3
	4.9	81.9	175.7	2.2	0.648	0.712	0.896	0.642	0.716	1.2
	5.8	81.9	124.3	1.6	0.648	0.714	0.9	0.644	0.724	1.3
	5.9	81.9	113.8	1.2	0.652	0.714	0.895	0.647	0.72	1.3
	0.0	81.9	409.5	4.1	0.628	0.693	0.869	0.623	0.693	0.901
	1.8	81.9	297.1	2.9	0.634	0.7	0.888	0.632	0.705	1.2
	0.0	81.9	409.5	4.1	0.629	0.694	0.88	0.629	0.697	1.0
	0.0	81.9	409.5	4.1	0.626	0.69	0.871	0.622	0.692	0.937
	0.0	81.9	409.5	4.1	0.622	0.689	0.874	0.62	0.688	0.954
	7.2	69.1	73.5	0.957	0.656	0.72	0.896	0.648	0.713	1.1
	7.6	64.7	68.2	1.2	0.656	0.72	0.908	0.648	0.716	1.2
	7.2	31.4	36.7	0.711	0.66	0.724	0.912	0.648	0.717	1.2
	6.2	81.9	87.5	0.879	0.632	0.701	0.912	0.61	0.693	1.2
	6.9	81.9	94.7	1.4	0.653	0.717	0.902	0.645	0.716	1.2
	4.9	81.9	166.2	1.6	0.64	0.704	0.879	0.632	0.698	0.912
	6.3	81.9	117.9	1.6	0.64	0.706	0.888	0.632	0.699	0.943
	0.44	81.9	409.5	4.1	0.637	0.701	0.885	0.636	0.7	0.946
	0.0	81.9	409.5	4.1	0.634	0.698	0.878	0.631	0.696	0.936
	8.4	81.9	128.5	1.7	0.635	0.701	0.884	0.628	0.694	0.926
	7.8	53.8	64.0	0.871	0.656	0.718	0.896	0.645	0.708	0.922
	7.6	69.1	69.8	1.1	0.65	0.716	0.92	0.642	0.708	0.98
	7.8	57.4	63.5	1.1	0.656	0.719	0.909	0.648	0.712	0.991
	7.5	54.7	57.8	1.1	0.656	0.72	0.904	0.648	0.709	0.98
	8.4	81.9	12.7	0.101	0.575	0.683	0.972	0.553	0.63	0.93

 

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