Алгоритм решения задачи

Особенности решения транспортных задач

Пример. Три поставщика А ₁, А ₂, А ₃ имеют запасы однородного груза а ₁ = 18т., а ₂ = 22т., а ₃ = 34т. Весь груз требуется с наименьшими затратами доставить потребителям В ₁, В ₂, В ₃, В ₄ , потребности которых составляют: b ₁ = 12т., b ₂ = 18т., b ₃ = 20т, b ₄ = 24т. Тарифы перевозок (стоимость перевозки 1т. груза) представлены матрицей

Требуется определить оптимальный план поставки грузов.

Экономико-математическая модель задачи

Переменные: – количество груза, доставляемое i -м поставщиком j -му потребителю.

Целевая функция – это суммарные транспортные издержки.

min (3)

Ограничения по поставщикам:

(4)

Ограничения по потребителям:

(5)

Из ограничений видно, что это задача закрытого вида.

1. Ввести исходную информацию. Введите исходную информацию, как показано на рис.16 (ячейки А1:F6). В ячейках В3:Е5 находятся значения тарифов перевозок .

Рис.16

2. Создать форму для решения и результатов задачи. Форма имеет вид показанный на рис.16 (ячейки А9:F14). В ячейках В11:Е13 будет размещен результат решения задачи (оптимальные значения ). В ячейках F11:F13 реализованы формулы для вычисления левых частей ограничений (4), например в ячейке F11 записывается формула =СУММ(B11:E11), что соответствует левой части первого ограничения (4): . Аналогичным образом реализуются левые части ограничения по потребителям (5) (В14:Е14) с помощью функции =СУММ соответствующих столбцов таблицы результатов. В ячейке F14 будет вписано итоговое значение целевой функции (3), поэтому в ней реализована формула

с помощью функции =СУММПРОИЗВ(B3:E5;B11:E13).

3. Запустить команду Поиск решений. В результате чего появляется окно рис.17.

Рис.17

Заполнить это окно как показано на рисунке, т.е. ввести адреса целевой ячейки, результата задачи (Изменяя ячейки), активизировать цель задачи – минимальное значение и ввести ограничения по технологии, описанной при реализации предыдущей задачи (задача оптимального использования ресурсов). Для данной задачи результаты выше перечисленных операций представлены на рис.17.

4. Ввести параметры для решения задачи. Для чего необходимо активировать кнопку «Параметры» и в всплывающем окне (рис.18) установить опции, как показано на рисунке, после чего нажать кнопку «ОК». При этом происходит возврат к окну Поиск решения, где необходимо нажать кнопку «Выполнить». В результате на экране появляется окно Результаты поиска решения (Рис.19). Необходимо нажать кнопку «ОК». Результаты появятся в, заготовленной для результатов, таблице (рис.20).

Рис.18

Рис.19

Рис.20

Из таблицы видно, что при таком распределении перевозок общие затраты на перевозку составляют 294 денежных единиц.

В случае транспортной задачи открытого типа ее алгоритм решения на компьютере практически ничем не отличается от решения задач закрытого типа. Отличие состоит только в ограничениях.

Пусть в предыдущем примере запасы грузов у поставщиков А ₁, А ₂, А ₃ составляют соответственно: 20т., 25т., 35т. Видно, что в этом случае , т.е. задача открытого типа. Ограничения по поставщикам будут следующими

Ограничения и результаты решения задачи представлены на рис.21, рис.22.

Рис.21

Рис.22

Из рис.22 следует, что первый и второй поставщики свои грузы перевезли полностью, а у третьего поставщика осталось не реализованным 6т. груза. При этом стоимость перевозок по сравнению с задачей закрытого типа (294 д.е.) стала меньшей (280 д.е.). Этот результат является закономерным, т.к. возможности варьирования перевозимыми грузами увеличились.

Дата добавления: 2014-12-25