Максимизация удельного показателя перевозок
Данный калькулятор предназначен для решения транспортных задач универсальным методом.В случаях, когда требуется оптимизировать удельный показатель (например себестоимость перевозки) при ограничениях, то составляется дробно-линейная математическая модель, обеспечивающая оптимальное планирование удельного показателя себестоимости перевозок.
E - удельный показатель; R-эксплуатационные расходы; F- валютные доходы
Е= F/R
Математическая модель: Е= F/R => max
при ограничениях:
∑xij = Ai
∑xij = Bj
X>=0
при условии баланса ∑Ai = ∑Bj
Автотранспортному предприятию необходимо организовать перевозку пассажиров по трём направлениям в количестве В1, В2, В3 человек, используя два вида транспорта с провозочной способностью А1, А20 человек.
Требуется составить план перевозки пассажиров, обеспечивающий максимизацию удельного показателя, если валютные доходы и эксплуатационные расходы заданы таблицами.
Пусть задана матрица валютных доходов.
| 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
Составляем опорный план методом северо-западного угла по доходам и расходам.
Вычисляем детерминанты для свободных клеток по формуле:
где ΔF,ΔR - алгебраические суммы коэффициентов С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 = |
|
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 = |
|
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 = |
|
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 = |
|
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
Пример. Пассажирскому предприятию необходимо перевезти пассажиров по трём направлениям, имея в наличие два вида автотранспорта. Требуется составить план расстановки автотранспорта с перевозной способностью а1 =400;
а2 =200 пассажиров при котором достигается максимальное значение удельного показателя: Е=F/R;
F-валютные доходы;
R-эксплуатационные расходы.
| Валютные доходы | Эксплуатационные расходы | ||||
| 1 | 3 | 5 | 3 | 5 | 9 |
| 8 | 4 | 7 | 7 | 6 | 2 |
Решение находим с помощью калькулятора.
В случаях, когда требуется оптимизировать удельный показатель (например себестоимость перевозки) при ограничениях, то составляется дробно- линейная математическая модель, обеспечивающая оптимальное планирование удельного показателя себестоимости перевозок.
E - удельный показатель; R-эксплуатационные расходы; F- валютные доходы
Е= F/R
Математическая модель: Е= F/R => max
при ограничениях:
∑xij = Ai
∑xij = Bj
X>=0
при условии баланса ∑Ai = ∑Bj
Валютные доходы
| 1 | 2 | 3 |
1 | 1 | 3 | 5 |
2 | 8 | 4 | 7 |
Эксплуатационные расходы
| 1 | 2 | 3 | Запасы |
1 | 3 | 5 | 9 | 400 |
2 | 7 | 6 | 2 | 200 |
Потребности | 200 | 200 | 200 |
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 400 + 200 = 600
∑b = 200 + 200 + 200 = 600
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
| 1 | 2 | 3 | Запасы |
1 | 3 | 5 | 9 | 400 |
2 | 7 | 6 | 2 | 200 |
Потребности | 200 | 200 | 200 |
|
Первая итерация заключается в определении исходного опорного плана и проверке его на оптимальность.
Определение исходного опорного плана. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(cij), способу Фогеля и по способу Лебедева-Тихомирова.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
| 1 | 2 | 3 | Запасы |
1 | 3[200] | 5[200] | 9 | 400 |
2 | 7 | 6 | 2[200] | 200 |
Потребности | 200 | 200 | 200 |
|
2. Подсчитаем число занятых клеток таблицы, их 3, а должно быть m + n - 1 = 4. Следовательно, опорный план является вырожденным.
F(x) = 3*200 + 5*200 + 2*200 = 2000
Строим новый план.
| 1 | 2 | 3 | Запасы |
1 | 3[200] | 5[200] | 9 | 400 |
2 | 7 | 6 | 2[200] | 200 |
Потребности | 200 | 200 | 200 |
|
2. Подсчитаем число занятых клеток таблицы, их 3, а должно быть m + n - 1 = 4. Следовательно, опорный план является вырожденным.
F(x) = 3*200 + 5*200 + 2*200 = 2000
Строим новый план.
| 1 | 2 | 3 | Запасы |
1 | 3[200] | 5[200] | 9 | 400 |
2 | 7 | 6 | 2[200] | 200 |
Потребности | 200 | 200 | 200 |
|
2. Подсчитаем число занятых клеток таблицы, их 3, а должно быть m + n - 1 = 4. Следовательно, опорный план является вырожденным.
F(x) = 3*200 + 5*200 + 2*200 = 2000
Строим новый план.
| 1 | 2 | 3 | Запасы |
1 | 3[200] | 5 | 9[200] | 400 |
2 | 7 | 6[200] | 2 | 200 |
Потребности | 200 | 200 | 200 |
|
2. Подсчитаем число занятых клеток таблицы, их 3, а должно быть m + n - 1 = 4. Следовательно, опорный план является вырожденным.
F(x) = 3*200 + 9*200 + 6*200 = 3600
Строим новый план.
| 1 | 2 | 3 | Запасы |
1 | 3 | 5[200] | 9[200] | 400 |
2 | 7[200] | 6 | 2 | 200 |
Потребности | 200 | 200 | 200 |
|
2. Подсчитаем число занятых клеток таблицы, их 3, а должно быть m + n - 1 = 4. Следовательно, опорный план является вырожденным.
F(x) = 5*200 + 9*200 + 7*200 = 4200
Строим новый план.
| 1 | 2 | 3 | Запасы |
1 | 3 | 5[200] | 9[200] | 400 |
2 | 7[200] | 6 | 2 | 200 |
Потребности | 200 | 200 | 200 |
|
Подсчитаем число занятых клеток таблицы, их 3, а должно быть m + n - 1 = 4. Следовательно, опорный план является вырожденным.
Значение целевой функции для этого опорного плана равно:
На протяжении многих итераций так и не удалось получить невырожденный план, поэтому для получения невырожденного плана принудительно добавляем в распределительную таблицу 1 нулей [0].
Для получения невырожденного плана принудительно добавляем нуль [0] в клетку (1;3);
Составляем опорный план методом северо-западного угла по доходам и расходам.
Вычисляем детерминанты для свободных клеток по формуле:
где ΔF,ΔR - алгебраические суммы коэффициентов СFij, СRij, взятых со знаками соответствующих клеток цикла.
Если Dij<=0, то план оптимален, в случае max.
Если Dij>=0, то необходимо произвести перераспределение в свободную клетку для которой Dij>0.
Эксплуатационные расходы составят:
R(x) = 3*200 + 5*200 + 2*200 = 2000
По валютным доходам.
Валютные доходы составляют:
F(x) = 1*200 + 3*200 + 7*200 = 2200
Удельный показатель равен: E = F / R = 2200 / 2000 = 1.1.
Проверим план на оптимальность.
Рассчитаем алгебраические суммы Δij коэффициентов СFij, СRij для свободных клеток, взятых со знаками соответствующих циклов.
Вычисляем Δij для каждой свободной клетки.
В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1 | 2 | 3 | Запасы |
1 | 3[200][-] | 5[200] | 9[0][+] | 400 |
2 | 7[+] | 6 | 2[200][-] | 200 |
Потребности | 200 | 200 | 200 |
|
Цикл приведен в таблице (2,1; 2,3; 1,3; 1,1; ).
Оценка свободной клетки равна Δ21 = (7) - (2) + (9) - (3) = 11
Для этой же клетки СF21 = 11.
D21 = 5 • 2000 - (11 • 2200) = -14200
В свободную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1 | 2 | 3 | Запасы |
1 | 3[200] | 5[200][-] | 9[0][+] | 400 |
2 | 7 | 6[+] | 2[200][-] | 200 |
Потребности | 200 | 200 | 200 |
|
Цикл приведен в таблице (2,2; 2,3; 1,3; 1,2; ).
Оценка свободной клетки равна Δ22 = (6) - (2) + (9) - (5) = 8
Для этой же клетки СF22 = 8.
D22 = -1 • 2000 - (8 • 2200) = -19600
Из приведенного расчета видно, что ни одна свободная клетка не имеет положительного детерминанта D оценки, следовательно, дальнейшее увеличение целевой функции Fx невозможно, поскольку она достигла максимального значения.
Таким образом, последний опорный план является оптимальным.
Минимальные затраты составят: R(x) = 3*200 + 5*200 + 2*200 = 2000
Максимальный доход составит: F(x) = 1*200 + 3*200 + 7*200 = 2200
