Allmath.ru

Вся математика в одном месте!

 

 

 

 



Rambler's Top100


Задачи по исследованию операций (СОДЕРЖАНИЕ)

 5. МЕТОДЫ НАХОЖДЕНИЯ ОПОРНЫХ ПЛАНОВ

5.1. Теоретическое введение

Опорный план является допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

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

Метод северо-западного угла

На каждом шаге метода северо-западного угла из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов.

Для того, чтобы заполнить клетку (i,j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке  с текущей потребностью в рассматриваемом j-м столбце .

Если существующий запас позволяет перевезти всю потребность, то

·        в клетку (i,j) в качестве перевозки вписывается значение потребности ;

·        j-й столбец вычеркивается, поскольку его потребность уже исчерпана;

·        от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т.е. .

Если существующий запас не позволяет перевезти всю потребность, то

·        в клетку (i,j) в качестве перевозки вписывается значение запаса ;

·        i-я строка вычеркивается, поскольку ее запас уже исчерпан;

·        от существующей потребности в j-й строке отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее записывается остаток, т.е..

Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы.

Метод минимального элемента

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

Метод Фогеля

На каждом шаге метода Фогеля для каждой i-й строки вычисляются штрафы  как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы  для каждого j-го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом .

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

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

5.2. Методические рекомендации

Формально и реальные и фиктивные столбцы и строки в транспортной матрице абсолютно равноправны. Поэтому при нахождении опорных планов фиктивные строки, столбцы и тарифы необходимо анализировать и использовать точно так же как и реальные. Но при вычислении значения ЦФ фиктивные перевозки не учитываются, поскольку они реально не были выполнены и оплачены.

Если величина фиктивных тарифов превышает максимальный из реальных тарифов задачи [], то методы минимального элемента и Фогеля позволяют получить более дешевые планы перевозок, чем в случае с нулевыми фиктивными тарифами.

Задача №5.01

Найти тремя методами опорный план ТЗ, в которой запасы на трех складах равны 210, 170, 65 ед. продукции, потребности четырех магазинов равны 125, 90, 130, 100 ед. продукции, тарифы перевозки в рублях за единицу продукции следующие:

.

Решение

Проверка сбалансированности задачи показывает, что суммарный объем запасов равен суммарному объему потребностей, т.е. введение фиктивных столбцов или строк не потребуется

.

Результаты нахождения опорного плана различными методами представлены в табл.5.1, 5.2 и 5.3.

Таблица 5.1

Транспортная таблица с опорным планом северо-западного угла

Пункты

отправления,

Пункты потребления,

Запасы,

ед. продукции

125

5

85

8

1

2

210/85/0

2

5

5

130

4

35

9

170/165/35/0

9

2

3

65

1

65/0

Потребность,

ед. продукции

125/0

90/5/0

130/0

100/65/0

Опорный план , найденный методом северо-западного угла

 [ед.товара].

Соответствующая ЦФ (общие затраты на перевозку)

 [руб.].


Таблица 5.2

Транспортная таблица с опорным планом минимального элемента

Пункты

отправления,

Пункты потребления,

Запасы,

ед. продукции

5

45

8

130

1

35

2

210/80/45/0

125

2

45

5

4

9

170/45/0

9

2

3

65

1

65/0

Потребность,

ед. продукции

125/0

90/45/0

130/0

100/35/0

Опорный план , найденный методом минимального элемента

 [ед.товара],  [руб.].

Таблица 5.3

Транспортная таблица с опорным планом Фогеля

Штрафы строк,

5

8

110

1

100

2

210/110/0

1

1

1

7

125

2

25

5

20

4

9

170/45/25/0

2

1

1

1

9

65

2

3

1

65/0

1

1

125/0

90/25/0

130/20/0

100/0

Штрафы столбцов,

3

3

2

1

3

2

1

3

3

7

3

3

На первом шаге нахождения опорного плана методом Фогеля возникает ситуация равенства значений максимальных штрафов транспортной матрицы (см. табл. 5.3)

.

Минимальные тарифы в этих столбцах также совпадают

.

Поэтому необходимо сравнить суммарные штрафы  клеток (2,1) и (3,2)

;

.

Т.к. , то выбираем на первом шаге для заполнения клетку (2,1).

Опорный план , найденный методом Фогеля

 [ед.товара],  [руб.].


Хотите публиковаться на портале? Присылайте свои предложения, книги, статьи на info@allmath.ru.

[Школьная математика][Высшая математика][Прикладная математика][Олимпиадная математика][Услуги][Лучшие книги][Ссылки]

 

Copyright (c) 2004, Allmath.ru. e-mail: info@allmath.ru