Экономика и менеджмент \ Модели и моделирование на транспорте

Постановка транспортной задачи в матричной форме. Симплекс метод решения задачи линейного программирования, страница 9

а₁=150	1		7		11		6		9		9
а₁=150		119						24				7
а₂=170	8		3		5		11		6		8
а₂=170				23		7				140
а₃=120	5		4		12		9		8		16
а₃=120				14		106
а₄=130	12		8		6		2		5		4
а₄=130												130
а₅=130	9		10		3		1		12		7
а₅=130						38		92
700/700	b₁=119		b₂=37		b₃=151		b₄=116		b₅=140		b₆=137

Найдем целевую функцию F:

F==

=2771

Полученное значение целевой функции совпадает с найденным ранее значением Fметодом потенциалов стр. 6.

2. Сетевая задача в транспортной постановке.

Задача сетевой постановки преимуществом по сравнению с матричной поскольку для отдельных участков указываются ограничения пропускной способности. С другой стороны имеет более громоздкий способ представления информации и поэтому применяется чаще всего с помощью компьютеров.

Алгоритм решения:

Шаг 1. Составляем допустимый план, где n = 1 число потоков (элементов),

n - число узлов, d_ij – ограничение потока, если x_ij=d_ij – такое звено не является базисным.

Шаг 2. Расстановка потенциалов Р_i,Р_j(только по базисным звеньям)

Шаг 3. Проверка. Получен ли план оптимальности. Да, если все потенциалы в свободных от потока звеньях . Если имеется звено, где x_ij= d_ij, то для него . Если условие оптимальности не выполняется, то переход к шагу 4.

Шаг 4. Из звеньев с нарушением условия оптимальности отыскивается наибольшее нарушение. Это звено становится базисным на следующей итерации, после корректировки базисного плана.

Шаг 5. Корректировка базисного плана.

Сначала для нового звена, которое войдет в базис задачи формируется путь обхода от меньшего потенциала к большему. Далее составляется замкнутый контур обхода, в который включается это звено и некоторые из базисных звеньев. В соответствии с заданными направлениями обхода, отыскиваются противопоточные обходу звенья из них выбирается звено с наименьшими потокам. Величина этого потока присваивается новому базисному звену. Остальные звенья с потоками по контуру корректируются. Если поток на звене совпадает с направлением потока, то к нему добавляется найденное значение потока и вычитается, если направление обхода противоположно потоку.

Переход к шагу 2.

Условие:

Данные по ресурсам поставщиков:

A=90

B=180

C=70

D=80

E=60

Данные по спросу потребителей:

F=43

G=23

H=31