Пример выполнения задания «Оптимизационные задачи в MS Excel»

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

¾ Ассортимент продукции (максимизация выпуска товаров при ограничениях на сырье для производства этих товаров).

¾ Составление штатного расписания для достижения наилучших результатов при наименьших расходах.

¾ Планирование перевозок (минимизация затрат на транспортировку товаров при условии удовлетворения потребностей потребителей).

¾ Составление смеси (получение заданного качества смеси при наименьших расходах)

Все эти задачи обладают следующими свойствами:

1. Наличие единственной цели.

2. Наличие ограничений, выражающихся, как правило, в виде неравенств.

3. Наличие набора входных значений-переменных, непосредственно или косвенно влияющих на ограничения и на оптимизируемые величины.

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

1. Если в модели в наличии несколько периодов времени, величина материального ресурса на начало следующего периода должна равняться величине этого ресурса на конец предыдущего периода.

2. В модели поставок величина запаса на начало периода плюс количество полученного должна равняться величине запаса на конец периода плюс количество отправленного.

3. Некоторые величины в модели по своему физическому смыслу не могут быть отрицательными либо дробными.

Ограничения имеют тот же синтаксис, что и логические формулы. Но, если в найденном решении логические формулы будут выполнены точно, то ограничения – с некоторой возможной погрешностью. Величина этой погрешности задается параметром Относительная погрешность и по умолчанию равна 0,000001.

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

Составление математической модели.

Сначала необходимо проделать подготовительную работу, а именно - определить тарифы на каждом участке будущего оптимального плана перевозок. Поскольку компания заинтересована в том, чтобы делать свою работу максимально быстро, то в качестве тарифов в данной задаче выступает время, потраченное на перевозку единицы товара из n-го склада в m-ую контору. При помощи карты Минска, с учетом времени на заправку автомобиля, компания оценила среднее время перевозки товара из каждого склада в каждый магазин. В результате была составлена таблица с исходными данными (табл.2.5).

Таблица 2.5

Время на перевозку

Данная транспортная задача относится к типу задач с неправильным балансом (47<>50). Далее задачу необходимо формализировать, т.е. записать в виде уравнений (формул). Пусть X – количество единиц товара, перевозимых из каждого склада в каждый магазин. Тогда X₁₁ - количество единиц товара, перевозимых из первого склада в первый магазин, X₁₂ - количество единиц товара, перевозимых из первого склада во второй магазин, и т.д. Поскольку задача с неправильным балансом, то необходимо ввести также фиктивный магазин. Все переменные представлены ниже (табл. 2.6).

Таблица 2.6

Количество перевозимых товаров

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

X₁₁+ X₂₁=15

X₁₂+ X₂₂=12

X₁₃+ X₂₃=20

X₁₄+ X₂₄=3

Аналогично получаем следующие условия:

X₁₁+X₁₂+X₁₃+X₁₄=20

X₂₁+X₂₂+X₂₃+X₂₄=30

Целевая функция определяет время выполнения намеченного плана транспортировки товара. Поэтому:

E=5* X₁₁ + 20* X₁₂ + 8* X₁₃ + 10* X₂₁ + 15* X₂₂ + 12* X₂₃ → min

Тарифы на доставку товара в виртуальный магазин принимаются равными нулю, поэтому слагаемое (0*X₁₄+0*X₂₄) в записи формулы для целевой функции можно опустить.

Выбор метода решения.

Итак, в ячейки строки с целевой функцией запишем коэффициенты перед переменными, входящими в целевую функцию. Так же поступим и cо всеми ограничениями в виде равенств (в столбце "L" записывается правая часть уравнений). В столбце с решением "J" в каждую ячейку введем формулу вида: =СУММПРОИЗВ(Bn:Gn;B2:G2), где n изменяется от 3 до 9. Затем открываем окно диалога «Поиск решения» и записываем все ограничения (рис. 2.6).

Рис. 2.6. Окно диалога «Поиск решения»

Нажимаем на кнопку "Выполнить".

Оптимальный план перевозок груза выглядит следующим образом: с первого склада нужно переправить 15 ед. груза в первый магазин и 5 ед. груза в третий магазин, а со второго - 12 ед. груза во второй и 15 ед. груза в третий магазин. На все это компания будет тратить 475 минут (7 часов и 55 минут). Это оптимальный вариант.