Материал: 5462

56

Затраты по перевозке 1 т топлива:

10. Определить оптимальный план снабжения бензином и дизельным топливом трех автопарков В1,В2,В3 двумя базами снабжения А1,А2. Мощности баз снабжения:

А1 – 200 т бензина, 250 т дизельного топлива; А2 – 400 т бензина, 300 т дизельного топлива.

Потребности автопарков:

В1 – 250 т бензина, 150 т дизельного топлива; В2 – 140 т бензина, 200 т дизельного топлива; В3 – 150 т бензина, 210 т дизельного топлива.

Известно, что 5 л бензина заменяют 1 л дизельного топлива. Затраты на перевозку 1 т топлива составляют в руб.

Глава 7. Транспортные задачи с ограничениями по пропускной способности

Пусть дополнительно к закрытой модели транспортной задачи (1.1)-

приводит к увеличению целевой функции. Достаточным условием разрешимости задачи является существование хотя бы одного допустимого решения. Дополнительные ограничения (xij dij ) в задаче могут быть

учтены в алгоритме метода потенциалов путем некоторого его видоизменения:

а) при определении величины поставки, перемещаемой по контуру

57

разность сравнивается с поставками в вершинах со знаком (-) и выбирается минимум из рассматриваемых чисел;

б) условие оптимальности решения устанавливается наличием системы потенциалов ui и v j , удовлетворяющим трем условиям

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

d22 150; d42 180; d44 90.

В связи с ограничениями по пропускной способности в таблице транспортной задачи число заполненных клеток может оказаться больше чем (m n 1) . Поэтому при решении системы уравнений относительно

потенциалов возникнет неопределенность в определении ui и v j , т.к. в задаче базисных переменных будет больше чем (m n 1) . Исходя из

этого, условимся обозначать кружками тарифы занятых клеток без ограничений и тех занятых клеток, для которых xij dij . Если число

кружков окажется меньше числа (m n 1) , то их можно вводить из числа занятых клеток без кружков, т.е. клеток, для которых xij dij , но так,

чтобы занятые клетки с кружками не образовывали замкнутого контура. Первоначальный опорный план Х1 находим по методу минимального элемента (табл. 8). Ограничения по пропускной способности в таблице записаны в рамке нижнего правого угла клеток

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

(1,4)-(1,2)-(4,2) и (3,4)-(3,2)-(4,2).

Выберем первый. Записываем недостающие 20 единиц в клетку (1,4), вычитаем 20 из поставки в (1,2) и прибавляем к поставке (4,2).

Замечание. Если с столбце, спрос по которому не удовлетворен полностью, или в строке, мощность которой использована частично, нет клеток без поставок и кружков, то для получения допустимого распределения строятся замкнутые контуры с четным числом вершин. Получаем допустимый план Х2 (табл. 9). Число кружков в нем (m n 1) = 7, а

занятых клеток с поставками 9, т.е. больше чем m n 1.

59

строим контур по кружкам, помечаем ее знаком (-) и перемещаем по контуру поставку

min( 90;180;180 110 ) 70 .

Целевая функция уменьшится на величину z 70 2 120 . Получаем новый план Х3. Проделав еще две итерации, получаем оптимальный план Хопт (табл. 10)

60

Вопросы для самопроверки

1.Каков смысл задачи с ограничениями по пропускной способности?

2.Каково условие оптимальности в задаче?

3.Зачем вводятся кружки для занятых клеток?

4.Тарифы каких занятых клеток обводятся кружками?

5.Как определяется величина поставки, перемещаемой по контуру, построенному по кружкам?

6.Почему в оптимальном плане допускается отрицательная

характеристика для клетки, у которой xij dij и каков экономический смысл этой характеристики?

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

9 5 3 10