Составители:
Рубрика:
153
Первая итерация заключается в определении исходного опорного плана и
проверке его на оптимальность.
Определение исходного опорного плана. Первый опорный план может быть
найден посредством различных способов: по правилу северо-западного угла, приоритету
ближайших пунктов, способу минимального элемента С=(c
ij
), способу Фогеля и, наконец,
по способу Лебедева-Тихомирова. Рассмотрим некоторые из них.
Самый простой (и в то же время самый плохой) способ называется правилом
северо-западного угла. Это формальный способ (порядок) распределения поставок между
потребителями, приводящий обычно к плану поставок, весьма далекому от
оптимального. Рассмотрим его на нашем примере. Для этого исходные условия задачи
представим в рабочей табл.4.2.
Т а б л. 4.2
Поставщики и
их мощности
Потребители и их спрос
В
1
В
2
В
3
В
4
200 200 250 200
Затраты на поставку 1м
3
, руб.
А
1
150 150
А
2
250 50
200
А
3
230
230
А
4
220
20 200
В соответствии c примером (табл.4.2) первый опорный план можно определить
следующим образом.
Согласно правилу северо-западного угла сначала находим значение x
11
(т.е. в
первую очередь заполняем поставкой клетку А
1
В
1
, расположенную в северо-западном
углу) из условия
x
11
=min(a
1
,b
1
).
Если a
1
≤ b
1
, то x
11
= a
1
и все остальные x
1j
=0; если же a
1
≥ b
1
, то x
11
= b
1
и остальные
x
i1
=0. Для данного примера x
11
=min (150,200)=150, x
12
=0, x
13
=0, x
14
=0. Поставку x
11
=150
записываем в табл. 4.2 в клетку А
1
В
1
.
После этого определяем значение x
21
по аналогичному правилу: x
21
=min (250,200-
150)=50. Тогда x
31
=0 и x
41
=0.
Иными словами, потребности потребителя В
1
b
1
=200 удовлетворяются частично за
счет поставщика А
1
-150 тыс.м
3
и частично поставщика А
2
– 50 тыс.м
3
, поскольку
мощность первого поставщика ограничена и оказалась меньше спроса потребителя В
1
.
Далее определяется значение x
22
для заполнения клетки А
2
В
2
. У поставщика А
2
нераспределенными остались 200 тыс.м
3
, потребителю В
2
необходимы также 200 тыс.м
3
,
следовательно x
22
=200, x
23
=0 и x
24
=0, x
32
=0 и x
42
=0.
Затем определяем значение x
33
в данном случае из условия x
33
= min(a
3
,b
3
), x
33
=
min(230,250)=230 и записываем его в клетку А
3
В
3
. При этом x
34
=0. Остались
незаполненными две клетки А
4
В
3
и А
4
В
4
. Для данного случая x
43
=20, x
44
=200.
Этот способ в некоторой литературе называется диагональным, поскольку
распределение поставок по клеткам производится последовательно, начиная с левой
5
3 2
3
3
4
5
4
2 5
6
5
1 2
3
6
Страницы
- « первая
- ‹ предыдущая
- …
- 151
- 152
- 153
- 154
- 155
- …
- следующая ›
- последняя »
