Нахождение первоначального опорного плана транспортной задачи линейного программирования

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ АВИАЦИОННЫЙ  ИНСТИТУТ

(Государственный Технический  Университет)

филиал «Восход»

 

 

 

Кафедра ИТИиУ        «Утверждаю»

Преподаватель _________ Максин А.П.

«___»  _____________ 2008 г.

 

 

 

 

Лабораторная работа  № 2

 

на тему: Нахождение первоначального  опорного плана транспортной задачи линейного программирования

 

 

 

по дисциплине: ТОПУ

 

 

 

 

 

 

Выполнил ст. гр. ВА4-56:

_______  Маркина М.А.

«____» _________ 2008 г.

 

 

 

 

 

 

 

 

 

 

 

 

Байконур 2008 г.

Цель работы: Получение практических навыков применения методов нахождения опорного плана транспортной задачи и проведение их сравнительного анализа.

Задание: Построить опорный план транспортной  задачи с помощью применения следующих методов:

- метода северо-западного угла;

- метода минимального элемента (стоимости);

- метода двойного предпочтения;

- метода аппроксимации Фогеля.

 

Запасы   6 34 23 28 17

Заказы 26 17 23 28 14

 

Матрица стоимости

20 20 47 29 21

49 41 46 43 42

12  2 17 35 41

20 16 22 33 35

33 31 44 3 1

 

 

 

Метод северо-западного  угла

 

 

ПН ПО	В1	В2	В3	В4	В5	ai
A1	6  20	20	47	29	21	6
A2	20  49	14  41	46	43	42	34	2
A3	12	3  2	20 17	35	41	23	4
A4	20	16	3   22	25  33	35	28	6
A5	33	31	44	3  3	14 1	17	8
bj	26	17	23	28	14	108
	1	3	5	7	9

 

 

Т.к. выполняется m и n условия, то  полученный план является допустимым.

 

Определим теоретическое  и фактическое число базисных ячеек:

r=m+n-1=5+5-1=9=r

=9=r

 

Т.к. =r, то допустимый полученный план является опорным.

 

L=6*20+20*49+14*41+3*2+20*17+3*22+25*33+3*3+14*1=2934

 

Метод минимального элемента

 

ПН ПО	В1	В2	В3	В4	В5	ai
A1	6    20	20	47	29	21	6	2
A2	9   49	41	46	25  43	42	34	9
A3	12	17   2	6   17	35	41	23	5
A4	11 20	16	17 22	33	35	28	7
A5	33	31	44	3  3	14   1	17	4
bj	26	17	23	28	14	135
	8	3	6		1

 

 

 

Т.к. выполняется m и n условия, то  полученный план является допустимым.

 

Определим теоретическое и фактическое  число базисных ячеек:

r=m+n-1=5+5-1=9=r

=9=r

 

Т.к. =r, то допустимый полученный план является опорным.

 

L=6*20+49*9+25*43+17*2+6*17+11*20+17*22+3*3+14*1=2389 
Метод двойного предпочтения

 

ПН ПО	В1	В2	В3	В4	В5	ai
A1	6   20	20	2 47	29	21	6	5
A2	49	41	9    46	25  43	42	34	9
A3	6   12	17   2	17	35	41	23	3
A4	14  20	16	14 22	13  33	35	28	7
A5	13   33	31	44	3   3	14   1	17	4
bj	26	17	23	28	14	108
	6	2	8		1

 

 

Т.к. выполняется m и n условия, то полученный план является допустимым.

 

Определим теоретическое и фактическое  число базисных ячеек:

r=m+n-1=5+5-1=9=r

=9=r

 

Т.к. =r, то допустимый полученный план является опорным.

 

L=6*20+9*46+25*43+6*12+17*2+14*20+14*22+3*3+14*1=2446

 

Метод Аппроксимации Фогеля

ПН ПО	В1	В2	В3	В4	В5	ai
A1	20	20	47	42	29	6	20-20=0	20-20=0
A2	49	41	46	43	42	34	42-41=1	42-41=1	1	1
A3	6 12	17 2	17	35	8 41	23	12-2=10	12-2=10	5	-
A4	20	16	8 22	33	35	28	20-16=4	20-16=4	2	33-22=11
A5	33	31	44	17 3	1	17	3-1=2	-	-	-
bj	26	17	23	28	14	108
	20-12=8	16-2=14	22-17=5	29-3= 26	21-1=20
	20-12=8		22-17=5	33-29=4	35-21=14
	49-20=29	-	46-22=24	43-33=10	42-35=7
	-	-	46	43	42
	-	-		-	-

 

Т.к. выполняется m и n условия, то  полученный план является допустимым.

Определим теоретическое  и фактическое число базисных ячеек:

r=m+n-1=5+5-1=9

=9=r

Т.к. =r, то допустимый полученный план является опорным.

L=6*21+15*46+11*43+8*42+6*12+17*2+20*20+8*22+17*3=2358

 

 

Представим математическую модель транспортной задачи в векторной  форме.

L=20*х₁₁+20*х₁₂+47*х₁₃+29*х₁₄+21*х₁₅+49*х₂₁+41*х₂₂+46*х₂₃+43*х₂₄+42*х₂+

+12*х₃₁+2*х₃₂+17*х₃₃+35*х₃₄+41*х₃₅+20*х₄₁+16*х₄₂+22*х₄₃+33*х₄₄+35*х₄₅+

33*х₅₁++31*х₅₂+44*х₅₃+3*х₅₄+1*х₅₅→min

Запишем m условие:

х₁₁+ х₁₂+ х₁₃+ х₁₄+ х₁₅=26

х₂₁+ х₂₂+ х₂₃+ х₂₄+ х₂₅=20

х₃₁+ х₃₂+ х₃₃+ х₃₄+ х₃₅=29

х₄₁+ х₄₂+ х₄₃+ х₄₄+ х₄₅=47

х₅₁+ х₅₂+ х₅₃+ х₅₄+ х₅₅=13

 

Запишем n условие:

х₁₁+ х₂₁+ х₃₁+ х₄₁+ х₅₁=27

х₁₂+ х₂₂+ х₃₂+ х₄₂+ х₅₂=27

х₁₃+ х₂₃+ х₃₃+ х₄₃+ х₅₃=44

х₁₄+ х₂₄+ х₃₄+ х₄₄+ х₅₄=13

х₁₅+ х₂₅+ х₃₅+ х₄₅+ х₅₅=24

x_ij≥0, i=1,5; j=1,5

а¹¹*х₁₁+а¹²*х₁₂+а¹³*х₁₃+а¹⁴*х₁₄+а¹⁵*х₁₅+а²¹*х₂₁+а²²*х₂₂+а²³*х₂₃+а²⁴*х₂₄+а²⁵*х₂₅+а³¹*х₃₁+а³²*х₃₂+а³³*х₃₃+а³⁴*х₃₄+а³⁵*х₃₅+а⁴¹*х₄₁+а⁴²*х₄₂+а⁴³*х₄₃+а⁴⁴*х₄₄+а⁴⁵*х₄₅+а⁵¹*х₅₁++а⁵²*х₅₂+а⁵³*х₅₃+а⁵⁴*х₅₄+а⁵⁵*х₅₅=а⁰

*х₁₁+ *х₁₂+ * х₁₃+ * х₁₄+ * х₁₅+ * х₂₁+ * х₂₂+ * х₂₃+ * х₂₄ + * х₂₅+ * х₃₁+ * х₃₂+ * х₃₃+ * х₃₄+ * х₃₅+ * х₄₁+ * х₄₂ + *х₄₃+ * х₄₄+ * х₄₅+ * х₅₁+ * х₅₂+ * х₅₃+ * х₅₄+ * х₅₅=

x_ij≥0, i=1,5; j=1,5

 

 

 

 

 

 

 

Вывод: С помощью четырех методов найдены 4 допустимых плана транспортных задач. Выяснено, что допустимые планы являются опорными, т.к. число теоретических и фактических ячеек равно во всех этих планах.

Главная цель в ТЗ получить наименьшую стоимость перевозок. Самым близким к оптимальному плану является найденный опорный план методом аппроксимации Фогеля, при котором значение целевой функции L=2358. Вторым по близости к оптимальному плану является план, найденный методом минимального элемента, значение целевой функции L=2389. Третьим по близости к оптимальному плану является план, найденный методом двойного предпочтения, значение целевой функции L=2446. Метод северо-западного угла дал значение целевой функции L=2934. Таким образом, при решении поставленной задачи лучше использовать метод аппроксимации Фогеля, при котором значение целевой функции L=2358.