Материал: Математические методы и модели в экономике. Амелин С.В

пустых ячеек, зарезервированных под размещение искомых переменных задачи (плана перевозок).

Рис. 67. Ввод целевой функции транспортной задачи

Условия транспортной задачи вводятся в диалоговую форму надстройки Поиск решения, вызываемой из меню Сер-

вис (рис. 68). В окно Установить целевую ячейку вводится ад-

рес функции цели щелчком левой кнопки мышки по ячейке, содержащей математическое выражение для подсчёта общих затрат на перевозки. Направление поиска экстремума целевой функции устанавливается соответствующим минимальному значению. В окно Изменяя ячейки вводятся адреса искомых значений переменных (B9:Е12).

135

Рис. 68. Заполнение диалоговой формы Поиск решения

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

Рис. 69. Заполнение диалоговой формы Добавление ограничения

В левом окне формы Добавление ограничения (рис. 69)

вводятся адреса левой части ограничений – суммы объёмов перевозок от поставщиков и суммы объёмов перевозок к потребителям. Знак ограничения устанавливается в виде знака равенства “ = “. В правом окне формы Добавление ограничения вводятся адреса правой части ограничений – числовые значения предложения и спроса.

136

Нажав кнопку Параметры, следует поставить «галки»,

выделив пункты: Линейная модель, Неотрицательные значения и Автоматическое масштабирование (рис. 70).

Рис. 70. Заполнение диалоговой формы Параметры

Оптимальный план перевозок представлен на рис. 71. Так, от первого поставщика третьему потребителю перевозится 30 единиц груза, от второго поставщика второму потребителю – 70 единиц груза. Третий поставщик обеспечивает поставки первому потребителю в объёме 20 единиц груза и третьему потребителю – 30 единиц груза. Поставки из четвёртого пункта отправления осуществляются по трём маршрутам: второму потребителю – 20 единиц груза, третьему потребителю – 10 единиц груза, третьему – 70 единиц груза. Общие затраты на перевозки составят 350 ден.ед.

137

Рис. 71. Результаты решения транспортной задачи

Метод потенциалов

Для решения транспортной задачи можно использовать метод потенциалов. Пусть задан опорный план задачи, тогда каждому пункту отправления Аi приписывается некоторое число Ui, а каждому пункту назначения Вj – число Vj. Эти числа называют потенциалами, они подбираются так, чтобы для каждой базисной клетки (i, j) выполнялось равенство

Ui + Vj = Cij.

Таким образом, получаем m + n – 1 простых уравнений с m + n неизвестными Ui и Vj. В таком случае, когда система состоит из числа уравнений, меньшего, чем число неизвестных, появляется свободная неизвестная величина, которой мы можем придать любое значение. Все остальные неизвестные можно найти из системы уравнений.

138

После того, как будут найдены все потенциалы Ui и Vj, для каждой свободной клетки (i, j) определяют числа ij = Cij–

– (Ui + Vj). Далее поступаем так же, как и в распределительном методе: находим наибольшее по модулю отрицательное

число i0 j0 (т.е. самое малое из отрицательных) и делаем

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

отрицательному i0 j0 .

Пример решения задачи методом потенциалов:

Положим U1 = 0, тогда учитывая занятые клетки