3.5ТранспортнаязадачаЛп

Транспортнаязадача(ТЗ)ЛПможетбытьсформулированаследующимобразом.Имеет-сяmпунктовотправления(производства)A₁,...,A_m,вкоторыхимеетсятоварвколиче-ствеa₁,...,a_{mсоответственно.}Крометого,имеетсяnпунктовназначения(потребления)B₁,...,B_n,вкоторыхимеютсязаявкинаэтоттоварвколичествеb₁,...,b_{nсоответственно.}Предполагается,что

^m

i=1

a_i=

ⁿ

j=1

b_j,

т.е.все,чтопроизведено,должнобытьполучено.Приведенноеуравнениеназываетсяусло-виембаланса.

Известнастоимостьc_{ijперевозки}единицытовараизпунктаотправленияA_iвпунктпо-требленияB_j.Требуетсясоставитьтакойпланперевозоктовара,прикоторомвесьтоваризпунктовпроизводствавывезен,всезаявкивпунктахпотребленияудовлетвореныиобщаястоимостьперевозокминимальна.

МатематическаямодельТЗсостоитвследующем.Обозначимчерезx_ijколичествотовара,перевозимогоизA_iвB_j.СоставимзадачуЛП:

m n

^cij^xij^→min,

i=1j=1

n

j=1

mi=1

x_ij=a_i,i=1,...,m,

x_ij=b_j,j=1,...,n,x_ij≥0,∀i,j.

Напрактикеусловиебалансаможетневыполняться.Чтоделать?Если

m

i=1

a_i>

n

j=1

b_j,(производитсябольше,чемпотребляется),

товводимновыйпунктпотребленияB_n+1сзапросом

Полагаем

^bn+1⁼

mi=1

a_i−

nj=1

b_j.

Еслиже

mi=1

a_i<

nj=1

c_i,n+1=0,i=1,...,m.

b_j,(потребляетсябольше,чемпроизводится),

товводимновыйпунктпроизводстваA_m+1спредложением

^am+1⁼

nj=1

b_j−

mi=1

a_i.

Полагаем

c_m+1,j=0,j=1,...,n.

Вдальнейшембудемсчитать,чтоусловиебалансавыполнено.

^{Отметим,чторангсистемыограниченийТЗравенm+n−1(на1меньшеm+nзасчет}

связующегоусловиябаланса).Поэтомуколичествобазисныхпеременныхтакжеравно

^m+n−1.

ИсходныеданныеТЗудобнопредставлятьввидетранспортнойтаблицы(ТТ),см.ниже.

Ai/Bj	B1	B2	...	Bn	Запасыai
A1	c11	c12	...	c1n	a1
A2	c21	c22	...	c2n	a2
...	...	...	...	...	...
Am	cm1	cm2	...	cmn	am
Заявкиbj	b1	b2	...	bn	ai= bj

ОпорнымпланомТЗназываетсятакоераспределениеобъемовперевозоквТЗ,что

–этораспределениеявляетсядопустимым,

^{–числобазисныхпеременных(x}_ij^{>0)равноm+n−1,всеостальные(свободные)перемен-}

ныеравнынулю.Отметим,чтонекоторыебазисныепеременныетакжемогутравняться

нулю,

–несуществуетцикла,всевершиныкоторогосоответствуютбазиснымпеременным.ЦикломвТТназываетсянаборклеток,соединенныхзамкнутойломанойлинией,котораявточкахизломасовершаетповоротна90⁰.

МетодпотенциаловрешенияТЗ.Основныеэтапы:

Этап1.Отысканиеначальногоопорногоплана.

Этап2.Проверкатекущегоопорногоплананаоптимальность.

Этап3.Переходклучшемуопорномуплану.

Этап1.Известны2основныхметодаотысканияначальногоопорногоплана:методсеверо-западногоуглаиметодминимальнойстоимости.

Вметодесеверо-западногоуглакаждыйразопределяетсямаксимальныйобъемперевозок,соответствующийсеверо-западнойдопустимойклеткетаблицы.Приэтом,еслинеобходи-

мо,полагаемx_ij=0.Пояснимнапримере.

Ai/Bj	B1	B2	B3	B4	B5	Запасыai
A1	1810	278	35	6	9	48
A2	6	7	308	6	5	30
A3	8	7	910	128	67	27
A4	7	5	4	6	208	20
Заявкиbj	18	27	42	12	26	=125

c=1039

Вметодеминимальнойстоимостикаждыйразопределяетсямаксимальныйобъемперево-зок,соответствующийдопустимойклеткетаблицыснаименьшейстоимостьюc_ij.Пояснимнапримере.

Ai/Bj	B1	B2	B3	B4	B5	Запасыai
A1	1410	8	225	126	9	48
A2	46	7	8	6	265	30
A3	8	277	10	8	7	27
A4	7	05	204	6	8	20
Заявкиbj	18	27	42	12	26	=125

c=745

Вбазисввели7<m+n−1=8положительныхпеременных.Нужноввестиещеоднупеременную,равнуюнулю,так,чтобынеобразовалсяцикл.Например,x₄₂₌0.

Этап2.ПроверканаоптимальностьВметодепотенциаловвводятсяврассмотрениедвойственныепеременные–потенциалыu_i,i=1,...,m,(дополнительныйстолбецвматрицеТЗ)иv_j,j=1,...,n,(дополнительнаястрокавТТ).

Дляклеток,соответствующихбазиснымпеременным,должновыполняться

u_i+v_j=c_ij.

Вначалеодинизпотенциаловможновыбратьпроизвольно,например,u₁₌0,остальныеподсчитатьпоформулеu_i+v_j=c_ijдляклеток,соответствующихбазиснымпеременным.

Ai/Bj	B1	B2	B3	B4	B5	Запасыai	Потенциалыui
A1	+10	−148	+225	126	+9	48	0
A2	46	+7	+8	+6	265	30	-3
A3	148	137	+10	+8	+7	27	-1
A4	+7	−2+5	−204	+6	+8	20	-1
Заявкиbj	18	27	42	12	26	=125
Потенциалыvj	9	8	5	6	6

Критерийоптимальности:если

∆_ij=c_ij−(u_i+v_j)≥0длявсехклетокТТ,

топостроенныйопорныйпланявляетсяоптимальным.ВлевыйверхнийуголкаждойклеткиТТ,соответствующейнебазиснойпеременной,запишемзначение∆_ij.

^{Этап3.ПереходклучшемуопорномуплануЕслисуществует∆}_ij^{<0,топереходим}

клучшемуопорномуплануследующимобразом.

Определяемпеременную,котораябудетвведенавбазис,ипеременную,котораябудетизнеговыведена.Вбазисвведемпеременнуюx_i⁰_j^0такую,что

^∆_i⁰_j^0=min{∆_ij^|∀i,j}.

Ai/Bj	B1	B2	B3	B4	B5	Запасыai	Потенциалыui
A1	+10	8	365	126	+9	48	0
A2	46	+7	+8	+6	265	30	-1
A3	148	137	+10	+8	+7	27	1
A4	+7	145	64	+6	+8	20	-1
Заявкиbj	18	27	42	12	26	=125
Потенциалыvj	7	6	5	6	6

^{c=721−(8+4−5−5)·14=693}

Обозначимклетку(i⁰,j⁰)знаком“+”.Рассмотримцикл,образованныйэтойклеткойиклетками,соответствующимибазиснымпеременным.Припишемклеткамциклазнаки“+”и“-”так,чтооничередуютсяприкаком-либообходеэтогоцикла.Вычислим

x_i^∗_j^∗=Q=min{x_ij|клетка(i,j)отмечена“-”}.

Переменнуюx_i^∗_j^∗выводимизбазиса.

Еслиминимумдостигаетсянанесколькихпеременных,товыводимизбазисатолькооднупеременную.

Пересчитываемновыеобъемыперевозокдляэлементовцикла:

x_ij=x_ij+Q,есликлетка(i,j)помечена”+”,и

^xij^=xij^{−Q,есликлетка(i,j)помечена”-”.}

Дляновогоопорногопланаопределяемновыепотенциалыипроверяемегонаоптималь-

ность.Процессповторяемдотехпор,покаусловиеоптимальностинебудетвыполнено.

^{Внашемпримеременяетсялишьv}₂^=6.Все∆_ij^{≥0.Следовательно,построенноерешение}

оптимально.