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

Лабораторная робота № 5

Тема: Оптимизационные задачи. Традиционные экономические задачи.

Краткие теоретические сведения

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

Решением транспортной задачи является минимизация суммарных издержек, связанных с перевозками. Транспортные издержки рассчитываются как произведение стоимости перевозки (с) на количество перевозок (x). Суммарные транспортные издержки представляют собой суммарную стоимость всех перевозок. Поскольку комбинация перевозок может быть самая разнообразная, то необходимо выбрать оптимальный вариант:

Задача выполняется в Excel заданием команды «Поиск решения».

 

Несбалансированность в транспортной задаче возникает в случае, когда сумма запасов превышает (излишек) или меньше (дефицит), чем сумма заказов. В такой ситуации сначала необходимо сбалансировать транспортную задачу.

Если , т.е. присутствуют излишки запасов, то для сбалансирования задачи необходимо добавить «фиктивного потребителя», чтобы объем его заказа был равен размеру излишков. В этом случае в таблицы издержек и перевозок добавляется по одному столбцу для такого потребителя. В результате оптимизации в этом столбце окажется количество грузов (запасов), которое должно остаться у каждого из поставщиков.

Если , т.е. наблюдается дефицит, то для сбалансированности задачи необходимо добавить «фиктивного поставщика». В этом случае в таблицы издержек и перевозок добавляется по одной строке для такого поставщика. В результате оптимизации в этой строке окажется количество грузов (запасов), которое не получит каждый потребитель.

 

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

Задача о назначениях является частным видом линейной оптимизационной задачи. Наиболее часто задача о назначениях представляется следующим образом:

Имеются n рабочих и m видов работ. Стоимость c_ij выполнения i-м рабочим j-той работы приведена в таблице, где под строкой понимается рабочий, а под столбцом - работа. Необходимо составить план работ так чтобы все работы были выполнены, каждый рабочий был занят только на одной работе, а суммарная стоимость выполнения всех работ была бы минимальной.

Решение задачи о назначениях очень похоже на решение транспортной задачи. Особенность лишь в том, что плановые переменные могут принимать только значения 0 или 1 и в каждом столбце и строке может быть только одно ненулевое значение. Для решения задачи о назначениях в Excel с использованием настройки Поиск решения следует выделить ячейки назначений и подсчитать для них суммы по столбцам и по строкам. В ячейку целевой функции следует ввести формулу вычисляющую сумму произведений стоимости работы на план назначений.

После чего следует выбрать в Excel пункт меню Сервис/Поиск решения, в окне Поиск решения выбрать целевую ячейку, изменяемые ячейки и добавить ограничения. Как правила используются ограничения следующего вида:

1. Неотрицательность значений изменяемых ячеек;
2. Суммы значений изменяемых ячеек для каждой строки и столбца должны быть равны 1;
3. Иногда бывает необходимо задать целочисленные ограничения на изменяемые ячейки.

Далее следует нажать кнопку Выполнить, после чего будет получено решение задачи о назначениях.

Довольно часто задача о назначениях бывает представлена в так называемом несбалансированном виде (количество работ не равно количеству работников). В этом случае для приведения задачи о назначениях к сбалансированному виду следует добавить в таблицу одну или несколько фиктивных работ или работников.

 

Ход работы

Таблица 1. Стоимость перевозки единице продукции

Пункт производства	Центры потребления	Объем производства
b1	b2	b3	b4
a1
a2
a3
Объем потребления

 

Данная модель не сбалансированная, объем производства меньше объема потребления, то есть наблюдается дефицит продукции. В этом случае необходимо ввести фиктивную фабрику, стоимость перевозок единице продукции которой равна стоимости штрафов за недопоставку продукции, объемы перевозок – объемам недопоставки продукции в пункты распределения.

 

Таблица 2. Стоимость перевозки единице продукции после сбалансирования

 

Пункт производства	Центры потребления	Объем производства
b1	b2	b3	b4
a1
a2
a3
a4	2,5	2,5	2,5	2,5
Объем потребления

 

Результат решения транспортной задачи с помощью «Поиск решения» указан в Табл.3

 

Таблица 3. Оптимальное решение транспортной задачи

	Обьем перевозок

 

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

Таблица 4. Стоимость выполнения работ

 

рaботники	виды работ

 

Данная модель не сбалансированная так как число работ совпадает с числом работников. Необходимо сбалансировать модель.

 

Таблица 5. Стоимость выполнения работ после сбалансирования

 

рaботники		виды работ

 

Результат решения задачи о назначении показан в табл. 5

 

Таблица 6. Оптимальный план работ в задаче о назначении

стоимость работ

 

 

Вывод:

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