Максимизация удельного показателя перевозок

Автотранспортному предприятию необходимо организовать перевозку пассажиров по трём направлениям в количестве В1, В2, В3 человек, используя два вида транспорта с провозочной способностью А1, А20 человек. Требуется составить план перевозки пассажиров, обеспечивающий максимизацию удельного показателя, если валютные доходы и эксплуатационные расходы заданы таблицами. См. пример решения.
Инструкция. Выберите размерность матрицы доходов и затрат (число транспортных средств и число направлений), нажмите Далее. Полученное решение сохраняется в файле MS Word.
Количество направлений
Количество транспорта

В случаях, когда требуется оптимизировать удельный показатель (например себестоимость перевозки) при ограничениях, то составляется дробно- линейная математическая модель, обеспечивающая оптимальное планирование удельного показателя себестоимости перевозок.
E - удельный показатель; R-эксплуатационные расходы; F- валютные доходы
Е= F/R
Математическая модель: Е= F/R => max
при ограничениях:
∑xij = Ai
∑xij = Bj
X>=0
при условии баланса ∑Ai = ∑Bj
Пусть задана матрица валютных доходов.

1 2 3 4
1 5 6 3 8
2 7 3 9 7
3 1 1 2 8

Эксплуатационные расходы

1 2 3 4 Запасы
1 1 5 4 3 10
2 7 8 5 4 20
3 3 2 11 9 10
Потребности 10 20 10 10

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 10 + 20 + 10 = 40
∑b = 10 + 20 + 10 + 10 = 50
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равным 10 (50—40). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.

1 2 3 4 Запасы
1 1 5 4 3 10
2 7 8 5 4 20
3 3 2 11 9 10
4 0 0 0 0 10
Потребности 10 20 10 10

Первая итерация заключается в определении исходного опорного плана и проверке его на оптимальность.
Определение исходного опорного плана. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(cij), способу Фогеля и по способу Лебедева-Тихомирова.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

1 2 3 4 Запасы
1 1[10] 5 4 3 10
2 7 8 5[10] 4[10] 20
3 3 2[10] 11 9 10
4 0 0[10] 0 0 10
Потребности 10 20 10 10

2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.
F(x) = 1*10 + 5*10 + 4*10 + 2*10 + 0*10 = 120

Составляем опорный план методом северо-западного угла по доходам и расходам.
Вычисляем детерминанты для свободных клеток по формуле:
где ΔFR - алгебраические суммы коэффициентов СFij, СRij, взятых со знаками соответствующих клеток цикла.
Если Dij<=0, то план оптимален, в случае max.
Если Dij>=0, то необходимо произвести перераспределение в свободную клетку для которой Dij>0.
Эксплуатационные расходы составят:
R(x) = 1*10 + 5*10 + 4*10 + 2*10 + 0*10 = 120
По валютным доходам.
Валютные доходы составляют:
F(x) = 5*10 + 9*10 + 7*10 + 1*10 + *10 = 220
Удельный показатель равен: E = F / R = 220 / 120 = 1.83.
Проверим план на оптимальность.
Рассчитаем алгебраические суммы Δij коэффициентов СFij, СRij для свободных клеток, взятых со знаками соответствующих циклов.
Вычисляем Δij для каждой свободной клетки.
В свободную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

1 2 3 4 Запасы
1 1[10][+] 5[0][-] 4[0] 3[0] 10
2 7[0] 8[0][+] 5[10] 4[10][-] 20
3 3[0][-] 2[10] 11[0] 9[+] 10
4 0 0[10] 0 0 10
Потребности 10 20 10 10

Цикл приведен в таблице (3,4 → 3,1 → 1,1 → 1,2 → 2,2 → 2,4).
Оценка свободной клетки равна Δ34 = (9) - (3) + (1) - (5) + (8) - (4) = 6
Для этой же клетки СF34 = 6.
D =
2220
6120

D34 = 2 • 120 - (6 • 220) = -1080
В свободную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

1 2 3 4 Запасы
1 1[10][-] 5[0][+] 4[0] 3[0] 10
2 7[0] 8[0] 5[10] 4[10] 20
3 3[0] 2[10] 11[0] 9 10
4 0[+] 0[10][-] 0 0 10
Потребности 10 20 10 10

Цикл приведен в таблице (4,1 → 4,2 → 1,2 → 1,1).
Оценка свободной клетки равна Δ41 = (0) - (0) + (5) - (1) = 4
Для этой же клетки СF41 = 4.
D =
1220
4120

D41 = 1 • 120 - (4 • 220) = -760
В свободную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

1 2 3 4 Запасы
1 1[10][-] 5[0][+] 4[0] 3[0] 10
2 7[0][+] 8[0] 5[10][-] 4[10] 20
3 3[0] 2[10] 11[0] 9 10
4 0 0[10][-] 0[+] 0 10
Потребности 10 20 10 10

Цикл приведен в таблице (4,3 → 4,2 → 1,2 → 1,1 → 2,1 → 2,3).
Оценка свободной клетки равна Δ43 = (0) - (0) + (5) - (1) + (7) - (5) = 6
Для этой же клетки СF43 = 6.
D =
-1220
6120

D43 = -1 • 120 - (6 • 220) = -1440
В свободную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

1 2 3 4 Запасы
1 1[10][-] 5[0][+] 4[0] 3[0] 10
2 7[0][+] 8[0] 5[10] 4[10][-] 20
3 3[0] 2[10] 11[0] 9 10
4 0 0[10][-] 0 0[+] 10
Потребности 10 20 10 10

Цикл приведен в таблице (4,4 → 4,2 → 1,2 → 1,1 → 2,1 → 2,4).
Оценка свободной клетки равна Δ44 = (0) - (0) + (5) - (1) + (7) - (4) = 7
Для этой же клетки СF44 = 7.
D =
1220
7120

D44 = 1 • 120 - (7 • 220) = -1420
Из приведенного расчета видно, что ни одна свободная клетка не имеет положительного детерминанта D оценки, следовательно, дальнейшее увеличение целевой функции Fx невозможно, поскольку она достигла максимального значения.
Таким образом, последний опорный план является оптимальным.

Минимальные затраты составят: R(x) = 1*10 + 5*10 + 4*10 + 2*10 + 0*10 = 120
Максимальный доход составит: F(x) = 5*10 + 9*10 + 7*10 + 1*10 + *10 = 220

загрузка...