Решение транспортной задачи с помощью средства Excel Поиск решения

Исходные данные транспортной задачи приведены схематически: внутри прямоугольника заданы удельные транс­портные затраты на перевозку единицы груза c_ij, слева указаны мощности поставщиков a_i, а сверху - мощности потребителей b_j. Найти оптимальный план закрепления поставщиков за потре­бителями x_ij.

Мощности поставщиков	Мощности потребителей

В данной задаче суммарные запасы равны суммарным потреб­ностям, т.е. .

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

Ввод условий задачи состоит из следующих шагов.

1. Создание формы для решения задачи.

Этот шаг предполагает создание матрицы перевозок. Для этого необходимо выполнить резервирование изменяемых ячеек, поэтому в блок ячеек В3:Е6 вводятся «1» - так резервируется место, где после решения задачи будет находиться распределение поставок, обеспечивающее минимальные затраты на перевозку груза.

2. Ввод исходных данных.

В конкретном примере осуществляется ввод мощностей четырех поставщиков (ячейки А10:А13), потребности регионов в их продук­ции (В9:Е9), а также удельные затраты по доставке нефтепродуктов от конкретного поставщика потребителю (блок В10:Е13) (рис. 1.26).

3. Ввод граничных условий.

3.1. Вводим условия реализации мощностей поставщиков.

, где а_i - мощность поставщика i; x_ij - объем поставки груза от поставщика i к потребителю j; n - количество потребителей.

Для этого необходимо выполнить следующие операции:

§ поместить курсор в ячейку АЗ;

§ выбрать знак ∑;

§ выделить необходимые для суммирования ячейки В3:Е3;

§ нажать ENTER для подтверждения ввода формулы для сум­мирования.

Рис. 1.26. Создание формы для ввода условий задачи. Ввод исходных данных и граничных условий. Изменяемые ячейки - B3:Е6. В эти ячейки будет записан оптимальный план перевозок - x_ij

Аналогичные действия выполнить для ячеек А4, А5, А6, т.е. ввести условия реализации мощностей всех поставщиков (для всех строк). Эти действия можно реализовать иначе:

§ поместить курсор в ячейку АЗ;

§ выбрать команду Копировать, т.е. скопировать в буфер фор­мулу, введенную для ячейки АЗ;

§ выделить ячейки А4:А6;

§ выбрать команду Вставить, тем самым из буфера будет встав­лена формула для суммирования в А4:А6.

3.2. Вводим условия удовлетворения запросов потребителей, т.е.

, где b_j - мощность потребителя j; m - количество поставщиков.

Для этого необходимо выполнить следующие операции:

§ поместить курсор в ячейку В7;

§ выбрать знак ∑, при этом автоматически выделяется весь столбец В3:В6;

§ нажать ENTER для подтверждения суммирования показате­лей выделенного столбца.

Эту же последовательность действий выполнить для ячеек С7 и Е7 или же проделать следующие действия:

§ поместить курсор в ячейку С7;

§ выбрать команду Копировать;

§ выделить ячейки С7:Е7;

§ выбрать команду Вставить.

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

4. Назначение целевой функции.

Для вычисления значения целевой функции, соответствующей минимальным суммарным затратам на доставку груза, необходи­мо зарезервировать ячейку и ввести формулу для ее вычисления , где c_ij - стоимость доставки единицы груза от поставщика i к потребителю j; x_ij - объем поставки груза от поставщика i к потребителю j.

Для этого необходимо произвести следующие действия:

§ поместить курсор в ячейку В15 (после решения задачи в дан­ной ячейке будет находиться значение целевой функции);

§ запустить Мастер функций (значок f _x);

§ в окне Категория выбрать Математические;

§ в окне Функция при помощи спинера выбрать СУММПРОИЗВ;

§ нажать кнопку ОК;

§ в окне СУММПРОИЗВ указать адреса массивов, элементы которых

обрабатываются этой функцией.

В задаче целевая функция представляет собой произведение удельных затрат на доставку груза (расположенных в блоке ячеек В10+Е13) и объемов поставок для каждого потребителя (содер­жимое ячеек В3+Е6). Для этого надо:

§ в поле Массив 1 указать адреса В10:Е13;

§ в поле Массив 2 указать адреса В3:Е6;

§ нажать кнопку ОК - подтверждение окончания ввода адресов массивов.

В поле ячейки В15 появится некоторое числовое значение, рав­ное произведению единичных поставок на удельные коэффициен­ты затрат по доставке грузов (в данной задаче - это число 144) (рис. 1.27).

Рис. 1.27. Введены зависимости из математической модели. Выражение для вычисления значения целевой функции получено с помощью функции СУММПРОИЗВ (B3:Е6, B10:Е13).

5. Ввод зависимостей из математической модели.

Для этого необходимо выполнить следующие действия:

§ выбрать Сервис => Поиск решения;

§ поместить курсор в поле Установить целевую (ячейку);

§ ввести адрес $В$15 (тем самым мы резервируем ячейку, куда после решения задачи помещается значение целевой функции) или поместить курсор в В15, а затем выбрать Поиск решения. При этом в поле адреса целевой ячейки будет автоматически введен адрес $В$15;

§ установить направление изменения целевой функции, равное Минимальному значению;

§ ввести адреса изменяемых ячеек В3+Е6. Для этого необходимо:

· выбрать Изменяя ячейки;

· Ввести адреса $В$3:$Е$6 или щелкнуть на красной стрелке рядом с этим полем, выйти в таблицу с матрицей перевозок, выделить блок ячеек В3+Е6, щёлкнуть на красной стрелке и вернуться в блок Поиск решения. Такая последовательность действий приводит к тому, что будут введены нужные адреса.

6. Ввод ограничений задачи.

В матрицу перевозок, содержащую исходные данные по зада­че, необходимо ввести условие реализации мощностей всех по­ставщиков (рис. 28). Для этого необходимо:

§ выбрать Добавить ограничения;

§ в поле Ссылка на ячейку ввести адреса $А$3:$А$6;

§ в среднем поле установить знак «=». Для этого щелкнуть спинер и выбрать необходимый знак «=» (для открытой модели знак «=» следует заменить знаком «≤»);

§ в поле Ограничение установить адреса $А$10:$А$13;

§ для подтверждения введенного условия нажать кнопку ОК.

Рис. 28. Все грузы должны быть перевезены: , i = 1, …, m, т.е. А3:А6 = А10:А13

Далее вводится ограничение, которое реализует условие удов­летворения мощностей всех потребителей (рис. 29). Для этого необходимо:

§ выбрать Добавить ограничения;

§ в поле Ссылка на ячейку ввести адреса $В$7:$Е$7;

§ в поле знака выбрать при помощи спинера знак «=»;

§ в поле Ограничение установить адреса $В$9:$Е$9;

§ нажать кнопку ОК;

§ после этого надо вернуться в поле Поиск решения;

§ после ввода всех ограничений ввести ОК. На экране появится

окно Поиск решения с введенными ограничениями (рис. 30).

Рис. 29. Диалоговое окно «Добавление ограничений». Все потребности должны быть удовлетворены: , j =1,..., n, т.е. В7:Е7 = В9:Е9

Рис. 30. Ввод зависимостей из математической модели

7. Ввод параметров.

С помощью окна Параметры можно вводить условия для реше­ния оптимизационных задач. В нашей задаче следует установить флажок Неотрицательные значения и флажок Линейная модель. Нажать кнопку ОК. Опять появится диалоговое окно Поиск решения. Далее необходимо:

§ щелкнуть по кнопке Параметры;

§ выбрать переключатель Линейная модель;

§ выбрать переключатель Неотрицательные значения (так как объе­мы поставок груза не могут быть отрицательными);

§ нажать кнопку ОК. После этого произойдет переход в поле Поиск решения;

§ нажать кнопку Выполнить.

Решение

Решение задачи выполняется сразу же после ввода данных, когда на экране находится диалоговое окно Поиск решения. Нажать кноп­ку Выполнить. На экране появится диалоговое окно Результаты поиска решения (рис. 31).

В результате нами был получен оптимальный план перевозок:

Матрица перевозок (изменяемые ячейки)

31. диалоговое окно Результаты поиска решения

План перевозок означает что:

Х₁₃ = 80 ед. груза следует перевезти от поставщика 1 потре­бителю 3;

Х₂₁ = 200 ед. груза следует перевезти от поставщика 2 потре­бителю 1;

Х_2З = 70 ед. груза следует перевезти от поставщика 2 потреби­телю 3;

Х₂₄ = 50 ед. груза следует перевезти от поставщика 2 потребителю 4;

Х_З2 = 100 ед. груза следует пере везти от поставщика 3 потреби­телю 2;

X₄₁ = 50 ед. груза следует перевезти от поставщика 4 потребите­лю 1;

Х₄₂ = 0 ед. груза следует перевезти от поставщи­ка 4 потребителю 2.

Общая стоимость перевозок = 3200.

Задача о назначениях

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

Исходные параметры задачи о назначениях (табл. 1):

n - количество ресурсов;

m - количество работ;

а_i = 1 - единичное количество ресурса A_i, i = 1,..., n (напри­мер: один работник, одно транспортное средство, одна научная тема и т.д.);

b_j = 1 - единичное количество работы B_j, j = 1,..., m (напри­мер: одна должность, один маршрут, одна лаборатория);

c_ij - характеристика качества выполнения работы B_j с помо­щью ресурса А_i (например: компетентность работника i при работе на должности j; время, за которое транспортное средство i пере­везет груз по маршруту j; степень квалификации лаборатории i при работе над научной темой j.

Искомые параметры:

x_ij - факт назначения или не назначения ресурса A_i на ра­боту B_j:

L(X) - общая (суммарная) характеристика качества распреде­ления ресурсов по работам.

Таблица 1. Общий вид транспортной матрицы задачи о назначениях

Ресурсы	Работы	Количество ресурсов
В1	В2	...	Вm
А1	c11	c12	...	c1m
А2	c21	c22	...	c2m
...	...	...	...	…	…
Аn	cn1	cn2	...	cnm
Количество работ			...