Математические модели в экономике

Задача 1. Тарифы перегонки одного вагона

На трех железнодорожных станциях А₁, А₂ и А₃ скопилось 120, 110 и 130 незагруженных вагонов. Эти вагоны необходимо перегнать на железнодорожные станции В₁, В₂, В₃, В₄ и В₅. На каждой из этих станций потребность в вагонах соответственно равна 80, 60, 70, 100 и 50. Тарифы перегонки одного вагона определяются матрицей:

.

Составьте такой план перегонок вагонов, чтобы общая стоимость была минимальной.

Решение Занесем исходные данные в распределительную таблицу.

Проверим закрытость системы.

• ?А=120+110+130=360
• ?В=80+60+70+100+50=360

Условие баланса соблюдается. Запасы равны потребностям.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

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

• 2. Подсчитаем число занятых клеток, их 7, а должно быть m+n-1=7. Следовательно, опорный план является невырожденным.
• 3. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i по занятым клеткам таблицы, в которых u_i+v_i=c_ij, полагая, что u_i=0.

u₁+v₁=2; 0+v₁=2; v₁=2.

u₁+v₃=1; 0+v₃=1; v₃=1.

u₂+v₁=3; u₂+2=3; u₂=1.

u₂+v₂=3; 1+v₂=3; v₂=2.

u₃+v₂=9; u₃+2=9; u₃=7.

u₃+v₄=3; 7+v₄=3; v₄=-4.

u₂+v₅=2; 1+v₅=2; v₅=1.

Опорный план не является оптимальным, т.к. существуют оценки свободных клеток, для которых u_i+v_i>c_ij:

• (3;1): 7+2>8; ?31=7+2−8=1.
• (3;3): 7+1>6; ?33=7+1−6=2.
• (3;5): 7+1>4; ?35=7+1−4=4.

Выбираем максимальную оценку свободной клетки (3;5): 4.

Для этого в перспективную клетку (3;5) ставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

Из грузов x_ij стоящих в минусовых клетках, выбираем наименьшее, т. е. min (30,50)=30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из объемов грузов стоящих в минусовых клетках. В результате мы получим новый опорный план.

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi по занятым клеткам таблицы, в которых ui+vi=cij, полагая, что ui=0.

u₁+v₁=2; 0+v₁=2; v₁=2.

u₁+v₃=1; 0+v₃=1; v₃=1.

u₂+v₁=3; u₂+2=3; u₂=1.

u₂+v₂=3; 1+v₂=3; v₂=2.

u₂+v₅=2; 1+v₅=2; v₅=1.

u₃+v₅=4; u₃+1=4; u₃=3.

u₃+v₄=3; 3+v₄=3; v₄=-0.

Опорный план является оптимальным, т.к. для всех ui+vi?cij.

Затраты составят: F (x)=2*50+1*70+3*30+3*60+2*20+3*100+4*30=900.