Курсовая работа: Решение задач линейного программирования в среде Maple
Клетка ( i , j ) таблицы соответствует коммуникации, связывающей i-го поставщика сj-м потребителем.
Построить начальный план перевозок означает - назначить объемы перевозок в клетки таблицы таким образом, чтобы:
а)число заполненных клеток было (m+n-1). (Тогда план перевозок будет отвечать базисному решению ЗЛП);
б)сумма перевозок в любой строке должна быть равна запасу соответствующего поставщика, а сумма перевозок в каждом столбце равна потребности потребителя. (Условие выполнения ограничений ТЗ). Существует несколько способов нахождения начального решения, которые отличаются только выбором клетки, в которую назначается очередная перевозка. Так, в способе северо-западного угла (СЗУ) для очередного назначения перевозки выбирается левая верхняя клетка таблицы (при этом никак не учитываются цены перевозок). Наоборот, в способе минимальной стоимости (МС) для заполнения выбирается клетка текущей таблицы с минимальной ценой перевозки, что в большинстве случаев (но не всегда) приводит к более дешевому (а значит и более близкому к оптимальному) начальному плану перевозок.
Мы будем пользоваться способом минимальной стоимости (МС).
Изложим теперь алгоритм нахождения начального решения .
ШАГ 1 . Определенным способом выбираем клетку в текущей таблице. Пусть она имеет индексы (i, j) (i -номер поставщика, j- номер потребителя).
ШАГ 2. В качестве перевозок в эту клетку назначаем наименьшую из ai и потребности bj.
xij = min{ai ,bj }
ШАГ З. Уменьшим запас ai и потребность bjна величину перевозки xij , т.е.
ai = ai - xij ,
bj =bj -xij
ШАГ 4. При исчерпании запаса (ai = 0) запрещаем к перевозке оставшиеся свободные клетки i-ой строки, а при исчерпании потребности
(bj =0) запрещаем такие же клетки вj-ом столбце.
В случае одновременного исчерпания запасов потребностей (ai =bj= 0) запрещаем перевозки или в строке (тогда считаем, что у потребителя осталась потребность в количестве равном нулю, которую необходимо удовлетворить), или в столбце (в этом случае считаем, что у поставщика остается запас равный нулю, который необходимо вывезти). Это делается для того, чтобы при одновременном запрещении перевозок в строке и столбце количество заполненных клеток таблицы не стало меньшим, чем m+n-1.
Получим новую текущую таблицу, в которую не входят заполненные и запрещенные клетки. Если таблица не пуста, переходим к шагу 1. (При исчерпании таблицы - конец).
Способ минимальной стоимости
1.Клетки с минимальной ценой (3,1), (3,2) и (3,3). Выбираем, например, (3,2). (Далее все шаги, как в предыдущем способе).
2 . x32 = min{50,60} = 50
3. a' 3 =50-50=0, b' 2 = 100-50=50
4.Запрещаем строку 3.
1. Клетка с min ценой ~ (2,3)
2. x23 = min{70,80} = 70
3. a2 =70-70=0, b'3 = 80-70=10
4. Запрещаем строку 2.
| 1 | 2 | 3 | |
| 60 |
5 60 | 10 | 12 |
| Χ |
К-во Просмотров: 256
Бесплатно скачать Курсовая работа: Решение задач линейного программирования в среде Maple
|