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

Составим исходную таблицу 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.

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