Главная | Обратная связь
МегаЛекции

Распределительный метод решения ТЗ

1. Проверяем, является ли ТЗ задачей с правильным балансом.

2. Находим исходное допустимое базисное решение ТЗ методом СЗУ или МНС.

3. Рассматриваем все свободные клетки таблицы перевозок,составляем для них циклы пересчета и находим оценки свободных клеток . Выбираем ту клетку, которая имеет наибольшую по моду-
лю отрицательную оценку .

4. Производим сдвиг по циклу пересчета этой свободной клетки. Получаем новую таблицу перевозок.

5. Операции 3, 4 повторяем до тех пор, пока для всех свободных клеток не будет выполняться .

Пример. Построить оптимальное решение ТЗ. исходное допустимое решение которой, построенное методом СЗУ, задано в таблице 5.

Решение. Проверяем выполнение критерия оптимальности, начиная с первой строки:

Единственная свободная клетка с номером (2,1) имеет отрицательную оценку. Проводим сдвиг по циклу на число e, где e =min(40,60) = 40. После сдвига по циклу базисная клетка (1, 1) станет свободной (х11 = О), свободная клетка (2,1) станет базисной со значением х21 = 40. В соответствии с определением операции сдвига по циклу на число e = 40: х12 = 60. х22 = 20 (табл. 7).

Таблица 7

Пункт отправления Пункт назначения B1 B2 B3 B4 запасы
A1 5 40 2 20 5 6
A2 3 1 60 3 20 7
A3 5 5 4 30 6 40
потребности

 

В результате получаем новую таблицу перевозок (табл. 8)

Таблица8

Пункт отправления Пункт назначения B1 B2 B3 B4 запасы
A1 5 2 60 5 6
A2 3 40 1 20 3 20 7
A3 5 5 4 30 6 40
потребности

 

Проверяем справедливость критерия оптимальности для данного распределения поставок:


Итак, для всех свободных клеток имеем. Следовательно, распределение поставок оптимально.

Ответ:

.

fmin=2*60 + 3*40 + 1*20 + 3*20 + 4*30 + 6*40 = 680.

Замечания о выборе числа e, на которое производится
сдвиг по циклу пересчета свободной клетки

1. По определению e= min(из значений хij в отрицательных вершинах цикла пересчета данной свободной клетки).

2. Может оказаться, что e = О. В этом случае значения поставок в вершинах цикла не изменяются, значение целевой Функции при переходе к новому решению не изменяется, но бывшая свободная
клетка станет базисной с нулевой поставкой.

3. Может случиться, что минимум достигается одновременно для нескольких значений, стоящих в отрицательных клетках. После сдвига по циклу в этих клетках будут нулевые поставки. Однако, свободной считаем только одну из этих клеток. остальные считаются базисными с нулевыми поставками.

4.5. ТЗ по критерию стоимости с неправильным балансом

Задача с неправильным балансом сводится к задаче с правильным балансом путем введения так называемых фиктивныхпунктов отправления и фиктивныхпунктов назначения.
Случай 1
. Пусть

то есть суммарная мощность поставщиков больше суммарной мощности потребителей.

Вводим фиктивный пункт назначения Bn­+1. потребности в грузе
которого составляют

Стоимости перевозок из всех пунктов отправления в фиктивный пункт назначения Bn­+1 полагаем равными нулю: c1n­+1, c2n­+1, … cmn­+1=0.

Получим ТЗ с правильным балансом:

Пример. Найти оптимальное распределение поставок для Т3, заданной таблицей 11.

 

Таблица 11

Пункт отправления Пункт назначения B1 B2 B3 запасы
A1 1 3 2
A2 2 1 3
потребности

 

Решить задачу самостоятельно.

Ответ.

, fmin=42.

Из пункта А2 будет отправлено 5 единиц груза.

Случай 2. Пусть

Вводим фиктивный пункт отправления Am­+1, запас груза в котором:

,

Стоимости перевозок из фиктивного пунктa отправления Am­+1 во все пункты назначения полагаем равными нулю: c1m­+1, c2m­+1, … cm­+1n=0.

Получим ТЗ с правильным балансом:

Пример. Найти оптимальное распределение поставок для ТЗ, заданной таблицей 12.

 

таблица 12.

Пункт отправления Пункт назначения B1 B2 B3   запасы
A1 3 1 5 2
A2 4 6 7 3
A3 2 8 4 5
потребности

Задачу решить самостоятельно.

Ответ.

, fmin=162.

Потребности пункта B3 будут не удовлетворены на 5 единиц.

Замечание. При нахождении исходного решения ТЗ с неправильным балансом МНС следует фиктивные пункты учитывать в самую последнюю очередь, то есть выбирать наименьшую стоимость в первую очередь среди стоимостей реальных пунктов.

Внимание к ТЗ обусловлено тем, что задачи подобного типа и многие другие ЗЛП, во-первых, часто встречаются в практических расчётах, и, во-вторых, к ним сводятся многие другие задачи линейного программирования: сетевая задача, задача о назначениях, задача календарного планирования.

 

 





©2015- 2017 megalektsii.ru Права всех материалов защищены законодательством РФ.