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

Задание.
Пассажирскому предприятию необходимо перевезти пассажиров по трём направлениям, имея в наличие два вида автотранспорта. Требуется составить план расстановки автотранспорта с перевозной способностью а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);
Составляем опорный план методом северо-западного угла по доходам и расходам.
Вычисляем детерминанты для свободных клеток по формуле:
где ΔFR - алгебраические суммы коэффициентов С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

Перейти к онлайн решению своей задачи


doc:xml:
загрузка...