Составители:
Рубрика:
154
верхней клетки и далее уступами по диагонали к нижней правой, в нашем примере с А
1
В
1
к А
4
В
4
.
В результате такого распределения получен опорный план (табл.4.2),
удовлетворяющий условиям (4.2, 4.3, 4.4), однако очень далекий, как будет видно
дальше, от оптимального.
Значение целевой функции (4.1) для этого опорного плана равно
F=5⋅150+3⋅50+4⋅200+6⋅230+3⋅20+6⋅200=4340.
Таким образом, если бы осуществить поставки пиловочника по этому опорному
плану, общие затраты на поставку составили бы 4340 тыс.руб.
Запомним значение целевой функции, характеризующее опорный план,
найденный по правилу северо-западного угла. Сам же план оставим, и отыщем иное
исходное решение задачи, но на этот раз посредством лучшего способа, называемого
способом минимального элемента (или наименьшего элемента в матрице С(c
ij
)).
Способ минимального элемента позволяет в малой и большой задаче отыскать
исходный опорный план, очень близко стоящий к оптимальному, иногда – сразу
оптимальный.
Однако использование этого способа требует большого внимания. Поэтому
рассмотрим его детально на том же примере. Сущность его заключается в следующем.
В матрице стоимостей поставки С=(c
ij
) отыскивается клетка, содержащая
наименьший элемент c
ij
, затем в эту клетку записывается поставка x
ij
=min(a
i
,b
j
). Если
матрица содержит несколько одинаковых значений c
ij
, тогда выбирают любое одно
(безразлично какое) и заполняют эту клетку поставкой.
После занесения поставки x
ij
в клетку с минимальным c
ij
вычеркивают
(мысленно) столбец или строку (или то и другое). Если a
i
>b
j
, вычеркивается столбец. При
a
i
<b
j
, вычеркивают строку и при a
i
=b
j
вычеркивают и столбец и строку.
Далее процесс (шаги) повторяется до тех пор, пока не будут распределены все
поставки.
Если матрица большая, и в уме трудно держать разбитые в процессе
распределения на части значения a
i
и b
j
, в конце каждого шага вычисляют остаточные
(нераспределенные) мощности поставщиков и неудовлетворенные емкости потребителей.
В табл.4.3 запишем исходные данные рассматриваемого примера и определим
исходный опорный план по способу минимального элемента матрицы С(c
ij
).
Т а б л. 4.3
Поставщики и Потребители и их спрос Нераспределенные мощности
на
В
1
В
2
В
3
В
4
шагах
их мощности 200 200 250 200 2-м 3-м 4-м 5-м 6-м
А
1
150
150
3
150 150 0 0 0
А
2
250 180
4
70
5
250 250 250 70 0
А
3
230 100
7
130
6
230 230 230 230 0
А
4
220
200
1
20
2
20 0 0 0 0
Не-
удов.
спрос
на
2-м
0 200 250 200 650 - - - -
3-м
0 180 250 200 - 630 - - -
5
3
2
4
3
3
4
5
2
5 6
5
1 2
3
6
Страницы
- « первая
- ‹ предыдущая
- …
- 152
- 153
- 154
- 155
- 156
- …
- следующая ›
- последняя »
