Экономико-математические методы и модели

Имеем транспортную задачу с избытком запасов:

å аi > å bj ( где i=1 m ; j=1 n ).

490+270+380>180+190+110+210+200+120

>1010

C max = 150;

Требуется найти такой план перевозок (X), при котором все заявки будут выполнены, а общая стоимость перевозок минимальна. Очевидно, при этой постановке задачи некоторые условия-равенства транспортной задачи превращаются в условия-неравенства, а некоторые - остаются равенствами.

n

å Xi,j ? ai (i=1, . , m);

j=1

m

å Xi,j = bj (j=1, . , n).

i=1

Мы получаем следующую задачу:

х11+х12+х13+х14+х15+х16 ? 490

х21+х22+х23+х24+х25+х26 ? 270

х31+х32+х33+х34+х35+х36 ? 380

х11+х21+х31 = 180

х13+х23+х33 = 190

х14+х24+х34 = 110

х12+х22+х32 = 210

х15+х25+х35 = 200

х16+х26+х36 = 120

хij 0 для i = 1,2,3; j = 1,2,3,4,5,6;

Кmin=5х11+7х12+8х13+4х14+6х15+9х16+7х21+2х22+5х23+8х24+6х25+7х26+5х31+4х32+7х33+ +6х34+9х35+8х36;

Решение задачи

.

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

Для этого, сверх имеющихся n пунктов назначения В1, B2, . , Bn, введём ещё один, фиктивный, пункт назначения Bn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

ит+1 = å аш - å и ( где ш=1бюююбь ж о=1бюююбт ) б

b7 = 1140 - 1010= 130,

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения b7 будем считать равным нулю. Введением фиктивного пункта

назначения Bn+1 с его заявкой bn+1 мы сравняли баланс транспортной задачи и теперь его можно решать как обычную транспортную задачу с правильным балансом.

Первоначальный опорный план поставок построим на основе метода северо-западного угла: