Пример нахождения оптимального плана

Выбор переменной, которая будет выводиться из базиса.

Для того, чтобы найти новый план перевозок необходимо составить цикл пересчета.

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

Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.

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

(См. Пример нахождения опорного плана.)

Рассчитаем потенциалы пунктов отправки и пунктов доставки и . Для этого составьте систему для заполненных клеток плана перевозок: . Решим данную систему, полагая =0.

2. Вычислим коэффициенты изменения стоимости для незаполненных клеток плана: c_i,j’ = u_{i +} v_j - c_i,j.

Таблица 2

Поставщики и их ресурсы

Потребители и их спрос

B1

B2

B3

B4

A1

-7

-2

-13

A2

	[-6]

	[+6]

-13

-4

A3

	[+6]

-3

	[-6]

Стоимость перевозок по данному плану составляет: 1681.

F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 =1681

Получим потенциалы и .. Рассчитаем коэффициенты изменения стоимости перевозок.

Составим цикл пересчета: Опорная клетка: (3:1), далее (3:3) [-6], (2:3) [+6], (2:1) [-6]. Количество единиц изменения плана: 6. Потенциалы, коэффициенты и цикл пересчета указаны в таблице 2. Получим следующий план перевозок (Табл.3).

Таблица 3.

Поставщики и их ресурсы

Потребители и их спрос

B1

B2

B3

B4

A1

	[-20]

-1

	[+20]

-7

A2

-6

-13

-10

A3

	[+20]

-3

	[-20]

Стоимость перевозок по данному плану составляет: 1645.

F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *0 + 17 *13 + 15*7 + 24 *0 + 14 *6 + 30 *0 +25*20 + 21 *17 =1645

Получим потенциалы и . Рассчитаем коэффициенты изменения стоимости перевозок. Составим цикл пересчета: Опорная клетка: (1:3), далее (1:1) [-20], (3:1) [+20], (3:3) [-20]. Количество единиц изменения плана: 20
Потенциалы, коэффициенты и цикл пересчета указаны в таблице 3. Получим следующий план перевозок (Табл.4).

Таблица 4.

Поставщики и их ресурсы

Потребители и их спрос

B1

B2

B3

B4

A1

-5

-7

A2

-2

-9

-6

A3

-7

-4

Стоимость перевозок по данному плану составляет: 1565.

F=14 *7 + 28* 0 + 21*20 + 28*0 + 10 *0 + 17 *13 + 15*7 + 24 *0 + 14 *26 + 30 *0 +25*0 + 21 *17 =1565

Получим потенциалы и . Рассчитаем коэффициенты изменения стоимости перевозок. Потенциалы и коэффициенты указаны в таблице 4. Полученный план оптимальный, т.к. все коэффициенты изменения стоимости отрицательны или равны нулю.

Дата добавления: 2014-11-29