Пример решения задачи о назначениях на минимум.

Условие задачи.

Автотранспортное предприятие получило право на эксплуатацию 4-х автобусов на городских маршрутах А, В, С, Д. Маршруты отличаются различной протяженностью, дорожными условиями, интенсивностью движения автотранспорта. Автобусы также имеют различные характеристики по вместимости, маневренности, скорости, себестоимости перевозок. Тем не менее, любой из автобусов по своим характеристикам может работать на любом из предложенных маршрутов.

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

Задача выполняется на минимум и на максимум решения.

Решение.

Составим исходную таблицу 1.1, в которой по горизонтали буквами А, В, С, Д обозначены маршруты, а по вертикали – номера автобусов.

Путем пробных испытаний можно установить, какая себестоимость перевозок характерна в среднем для каждого автобуса на определенных маршрутах. Для этого в первый день изыскательской работы следует расставить автобусы по маршрутам произвольным образом и к концу дня произвести расчеты себестоимости перевозок. На следующий день автобусы расставляют по маршрутам иным образом и опять производят замеры и соответствующие расчеты. И так продолжают до тех пор, пока не переберут все возможные варианты расстановки автобусов. Этот этап решения задачи называется изыскательской работой.

Студенты этап изысканий в решении задачи могут не производить, а данные для табл. 1.1 выбрать произвольно, по своему усмотрению, или по опыту работы одного из известных предприятий.

Результаты изысканий записываются в клетки табл. 1.1.

Далее рассмотрим алгоритм поиска оптимального решения на поиск минимума выбранного критерия.

1. В каждой строке табл. 1.1 найдем наименьший элемент и запишем его в соответствующей строке табл. 1.2.

Табл. 1.1 Табл. 1.2

А В С Д

2. Вычтем элементы табл. 1.2 из строк табл. 1.1 и получим табл. 1.3.

Табл. 1.3

				Табл. 1.4

3. В табл. 1.3 находим минимальные числа по столбцам и запишем их в табл. 1.4. Вычтем из элементов табл. 1.3 числа из табл. 1.4.

Получим табл. 1.5. Теперь в каждой строке и в каждом столбце табл.5 есть, по крайней мере, один нулевой элемент.

Табл. 1.5

0

4. Далее проведем минимальное число прямых линий, проходящих через все нулевые клетки строк и столбцов табл. 1.5.

5. Найдем наименьший среди элементов, через которые не проходит ни одна из проведенных прямых (число 2).

6. Вычтем число 2 из всех элементов, через которые не проходят прямые.

7. Прибавим число 2 (минимальное число) в клетки, где прямые пересекаются.

8. Остальные клетки, через которые проходит только одна прямая, оставим без изменений. Таким образом, получим табл. 1.6.

Табл. 1.6

	А	В	С	Д

9. Теперь необходимо проанализировать данные, полученные в табл. 1.6.

Оптимальное решение задачи определяют клетки с нулевой себестоимостью. Выберем альтернативные решения (возможные решения по нулевым клеткам):

¨ на маршрут А нужно поставить автобусы № 3 или № 4,

¨ на маршрут В можно поставить автобус № 3,

¨ на маршрут С следует поставить автобус № 1,

¨ на маршрут Д можно поставить автобусы № 2 или № 4.

Таким образом:

- на маршрут В следует однозначно поставить автобус № 3, а на маршрут С – автобус № 1;

- на маршрут А надо направить автобус № 4, так как автобус № 3 уже использован,

- на маршруте Д остается автобус № 2.

Окончательное решение задачи: А 4; В 3; С 1; Д 2

10. Проверка:

Находим сумму общей себестоимости по данным исходной табл. 1.1 по оптимальному варианту. Она составляет 201.

Любые другие варианты дают сумму большую, чем в оптимальном варианте, например, равную 202, 208 и т.д.

Эту же задачу следует решить для поиска максимума прибыли или доходов. Для этого необходимо:

1. В исходной табл. 1.1 найти максимальное число (В2 - 61).

2. Вычесть максимальное число из всех клеток табл. 1.1.

3. Получим табл. 1.2.

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

Дата добавления: 2015-10-28