а) Строим в исходной матрице контур перераспределения ресурсов. Начало контура - клетка с максимальным нарушением условия оптимальности (клетка Х15). В новом плане эта клетка из незаполненной становится заполненной. Далее строим замкнутый многоугольник с вершинами в загруженных клетках, за исключением начала контура. Число вершин контура должно быть четным. Половина из них загружается и помечается знаком «+», другая половина- разгружается и помечается знаком «-.». в каждой строке и в каждом столбце имеется две вершины.
В контуре допускаются только вертикальные и горизонтальные линии.
В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных Хij ни одно из этих значений не должно превращаться в отрицательное число. Поэтому, с точки зрения переноса ресурсов по контуру анализируются только клетки, помеченные знаком «-.», из них выбирается клетка с минимальным объемом перевозок, и этот объем переносится по контуру.
Таблица5
| П. наз П. отпр | В1 | В2 | В3 | В4 | В5 | Gi | ai |
| А1 | 270 150 | 190 80 | 290 20 - | 180 + | |||
| А2 | 200 240 + | 185 120 | 200 90 - | -90 | |||
| А3 | 325 100 | ||||||
| Vj | |||||||
| bj |
Таблица6
| П. наз П. отпр | В1 | В2 | В3 | В4 | В5 | Gi | ai |
| А1 | 270 150 | 190 80 | 180 20 | ||||
| А2 | 200 260 | 185 120 | 200 70 | ||||
| А3 | 325 100 | ||||||
| Vj | |||||||
| bj |
F=L11x11+ L12x12+ L12x12+ L13x13+ L14x14+ L15x15+ L21x21+ L22x22+ L23x23+ L24x24+L25x25+ L31x31+ L32x32+ L33x33+ L34x34 + L35x35 =150*270+80*190 +0*290+ +0*190+20*180+0*175+0*350+260*200+120*185+70*200+0*230+0*310+0*295+0*200+100*325=180000
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
aij+bij=Lij
а1=0=L11-a1=270-0=270=L12-a1=190-0=190=L15-a1=180-0=180=L25-b5=200-180= 20=L23-a2=200-20=180
b4=L24-a2=185-20=165=L35-b5=325-180=145
б) проверяем условия оптимальности плана.
aij+bij 
Lij+b3=180<190+b4=165<190+b1=290>175! 
=115+b2=210<350+b1=415>230! =185+b2=335>310! =25+b3=325>295! 
=30+b4=310>200! =110
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
Перераспределение ресурсов
Клетка с максимальным нарушением условия оптимальности- Х31
Таблица 7
| П. наз П. отпр | В1 | В2 | В3 | В4 | В5 | Gi | ai |
| А1 | 270 150 - | 190 80 | 180 20 + | ||||
| А2 | 200 260 | 185 120 | 200 70 | ||||
| А3 | 230 + | 325 100 - | |||||
| Vj | |||||||
| bj |
Таблица8
| П. наз П. отпр | В1 | В2 | В3 | В4 | В5 | Gi | ai |
| А1 | 270 50 | 190 80 | 180 120 | ||||
| А2 | 200 260 | 185 120 | 200 70 | ||||
| А3 | 230 100 | -40 | |||||
| Vj | |||||||
| bj |
F=L11x11+ L12x12+ L12x12+ L13x13+ L14x14+ L15x15+ L21x21+ L22x22+ L23x23+ L24x24+L25x25+ L31x31+ L32x32+ L33x33+ L34x34 + L35x35 =50*270+80*190 +0*290+ +0*190+120*180+0*175+0*350+260*200+120*185+70*200+100*230+0*310+0*295+0*200+0*325=161500
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
aij+bij=Lij
а1=0=L11-a1=270-0=270=L12-a1=190-0=190=L15-a1=180-0=180=L25-b5=200-180= 20=L24-a2=185-20=165
b3=L23-a2=200-20=180=L31-b1=230-270=230-270=-40
б) проверяем условия оптимальности плана.
aij+bij Lij+b3=180<290+b4=165<180+b1=290>175! =115+b2=210<350+b2=150<310+b3=140<2953+b4=125<200
a3+b5=140<325
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
Перераспределение ресурсов
Клетка с максимальным нарушением условия оптимальности- Х21
Таблица9
| П. наз П. отпр | В1 | В2 | В3 | В4 | В5 | Gi | ai |
| А1 | 270 50 - | 190 80 | 180 120 + | ||||
| А2 | 175 + | 200 260 | 185 120 | 200 70 - | |||
| А3 | 230 100 | -40 | |||||
| Vj | |||||||
| bj |
Таблица10
| П. наз П. отпр | В1 | В2 | В3 | В4 | В5 | Gi | ai |
| А1 | 190 80 | 180 170 | |||||
| А2 | 175 50 | 200 260 | 185 120 | 200 20 | |||
| А3 | 230 100 | ||||||
| Vj | |||||||
| bj |
F=L11x11+ L12x12+ L12x12+ L13x13+ L14x14+ L15x15+ L21x21+ L22x22+ L23x23+ L24x24+L25x25+ L31x31+ L32x32+ L33x33+ L34x34 + L35x35 =0*270+80*190 +0*290+ +0*190+170*180+50*175+0*350+260*200+120*185+20*200+1000*230+0*310+0*295+0*200+0*325=155750
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
aij+bij=Lij
а1=0=L12-a1=190-0=190=L15-a1=180-0=180=L25-b5=200-180=20=L21-a2=175-20= 155=L23-a2=200-20=180
b4=L24-a2=185-20=165=L31-b1=230-155=75
б) проверяем условия оптимальности плана.
aij+bij 
Lij+b1=155<270+b3=180<290+b4=165<190+b2=210<350+b2=265<310+b3=255<295
a3+b4=240>200! 
=40+b5=255<325
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.