Дипломная (вкр): Решение задач оптимизации с применением пакетов прикладных программ

Алгоритмы такого рода лежат в основе инструмента Поиск решения (Solver) в табличном процессоре MS Excel. Следовательно, решение многих экономических оптимизационных (линейных и нелинейных) задач можно существенно облегчить с помощью данного инструмента.

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

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

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

Обычными задачами, решаемыми с помощью надстройки Поиск решения, являются [24]:

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

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

- Планирование перевозок. Минимизация затрат на транспортировку.

- Составление смеси. Получение заданного качества смеси при наименьших расходах.

- Оптимальный раскрой материалов (ограничения - количество деталей различной формы и размеров).

- Оптимизация финансовых показателей (например максимизация доходов за счет оптимизации средств на разные инвестиционные проекты).

Задачи, которые лучше всего решаются данным средством, имеют три свойства:

- имеется единственная максимизируемая или минимизируемая цель (доход, ресурсы и т.д.);

- имеются ограничения, выражающиеся, как правило, в виде неравенств (например, объем используемого сырья не может превышать объем имеющегося сырья на складе, или время работы станка за сутки не должно быть больше 24 часов минус время на обслуживание);

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

Размер задачи, которую можно решить с помощью базовой версии этой программы, ограничивается такими предельными показателями:

- количество неизвестных - 200;

- количество формульных ограничений на неизвестные - 100;

- количество предельных условий ) на неизвестные - 400.

Ограничения в задачах. Под ограничениями понимаются соотношения типа А1>=В1, А1=А2, А3>=0, А1= целое.

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

Часто ограничения записываются сразу для групп ячеек, например: А1:А10<=В1:В10 или А1:Е1>0.

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

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

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

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

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

Рассмотрим применение инструмента Поиск решения на примере следующей экономической задачи.

Задача 1. Составление производственного плана.

Фабрика выпускает сумки: женские, мужские, дорожные. Данные о материалах, используемых для производства сумок и месячный запас сырья на складе приведены в таблице 2.

Таблица 2. Данные о материалах

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

·  сумка женская - 150 шт. при оптовой цене 3000 руб.;

·  сумка мужская - 70 шт. при оптовой цене 700 руб.;

·  сумка дорожная - 50 шт. при оптовой цене 2000 руб.;

·  сумка спортивная - 30 шт. при оптовой цене 1200 руб.

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

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

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

Ментальная карта - это инструмент визуального представления и записи информации, метод, альтернативный привычному линейному способу.

Ментальная карта должна проиллюстрировать основную формулу математической модели (рисунок  <#"869912.files/image035.gif">

Рисунок 15. Основная формула математической модели

Ментальную карту выполним в виде столбцов со списками данных (рисунок  <#"869912.files/image036.gif">

Рисунок 16. Представление исходных данных

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

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

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

Целевая функция формируется скалярным произведением вектора цены  на вектор искомых значений переменных . Критерий оптимальности плана - получение максимального значения выручки - целевой функции .

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

Оптимальному решению задачи отвечает максимальное значение целевой функции при следующих условиях и ограничениях (таблица 3):

Таблица 3. Тестовая таблица

Лишь после того, как мы разобрались в условиях задачи, можно приступить к формированию таблицы в MS Excel (рисунок 17). Заполним ячейки исходными данными. Искомые переменные (количество сумок каждого вида) поместим в ячейки строки 12. В ячейку F3 вставим формулу и протянем ее до ячейки F10. Целевая функция помещается в ячейке F10. Это выручка, т.е. стоимость всех произведенных сумок.

Рисунок 17. Вставка формул в таблицу MS Excel

Отформатированная таблица представлена на рисунке 18. В ячейки для искомых переменных В12:Е12 можно вставлять, вообще говоря, любые числа. Программа выполнит подбор их числовых значений в соответствии с условиями задачи. Однако чаще всего в качестве начальных значений вводят 0 (как на рисунке 18) или 1 (как на рисунке 19).

Рисунок 18. Сформированная таблица MS Excel

После вставки формул по команде Данные - Поиск решения вызовем диалог и заполним поля, как показано на рисунке 2.5. Адреса ячеек нужно не набирать вручную, а показывать мышью. Вызывать поля ограничений для записи нужно кнопкой "Добавить". На рисунке показано, что введены ограничения на целостность искомых переменных, на превышение выпуска продукции над обязательными поставками и на не превышение расхода материалов над запасами их на складе. Не отрицательность переменных учитывается в диалоге автоматически.

Рисунок 19. Заполнение диалога "Параметры поиска решения"

После выполнения команды "Найти решение" будет выдан результат расчета: значения искомых переменных и соответствующий расход материалов (рисунок 20):

Рисунок 20. Результаты поиска решения

Таким образом, мы нашли, что максимально возможная выручка может составить 677500 руб. Для этого сверх договорных поставок мы должны изготовить 35 мужских сумок и 9 дорожных сумок. При этом на складе останется около 10% запаса материалов, кроме кожи и кожзаменителя, которые будут израсходованы полностью. Для сохранения результата нужно нажать кнопку "Сохранить сценарий", в диалоге дать имя сценарию "Сумки_1".

Оптимизация математической модели фактически закончена. Но теперь нужно перейти обратно от модели к реальной ситуации, т.е. принять управленческое решение. А что будет, если не удастся реализовать сумки, изготовленные сверх потребности? Ясно, что выручка будет равна только сумме, перечисленной от покупателей по договорным обязательствам. Тогда, может быть, и не изготавливать излишнюю продукцию? А сколько при этом останется материалов на складе? Руководитель предприятия на основе данного анализа должен иметь возможность принять решение о создании запасов, как буферных (запас материалов для компенсации задержек в поставках), так и гарантийных (запас продукции для удовлетворения ожидаемого спроса).