Решение задачи оптимизации Лабораторный практикум №1
Задачи оптимизации - это задачи, в которых требуется выбрать лучший вариант решения из нескольких возможных.
Теория оптимизации формализует совокупность действий, связанных с достижением определенных целей, например: определение ассортимента продукции, составление эффективного графика работы сотрудников, разработка схемы перевозок. Операция характеризуется количественными факторами двух видов: неконтролируемыми (значение известны, но не зависят от воли принимающего решение) и контролируемыми (управляемыми, значения зависят от лица, принимающего решения, но в определенных приделах, выражаемых математическими ограничениями).
Решение – это любой допустимый (удовлетворяющий ограничениям) набор значений факторов. Критерий качества решения, выраженный с помощью функции, называют критерием оптимальности, а функцию позволяющую оценить качество решения, - целевой функцией.
Оптимальное решение – решение, на котором достигается экстремум целевой функции. Если ограничения задаются системой линейных неравенств и целевая функция является линейной, то задача называется задачей линейного программирования.
Отличие экономико-математической постановки задачи оптимизации в табличном процессоре от традиционной экономико-математической постановки состоит в том, что в формулах задаются не символьные обозначения переменных и параметров, а координаты ячеек таблицы, в которых хранятся эти переменные.
Задачей данной работы является определение, на основании данных представленных в таблице №1, оптимального объема реализации товаров (№1-№4) организации ООО «Х» с целью получения максимальной прибыли, при этом также следует учесть:
- месячное ограничение по финансированию закупки товара – 19 500 тыс. руб.;
- месячное ограничение по количеству рейсов автотранспорта – 26.
Таблица №1
Ассортимент товаров ооо «х» в 2010 году.
Список товаров |
1 |
2 |
3 |
4 |
Предполагаемый объем реализации в месяц (шт.) |
630 |
649 |
710 |
864 |
Предполагаемый максимальный объем реализации в месяц (шт.) |
630 |
649 |
710 |
864 |
Вместимость склада (шт.) |
550 |
900 |
700 |
1000 |
Вместимость машины (шт.) |
25 |
55 |
35 |
65 |
Цена реализации 1 ед. (тыс. руб.) |
18,47 |
18,24 |
18,39 |
18,53 |
Цена приобретения 1 ед. (тыс. руб.) |
15,72 |
15,53 |
16,43 |
17,31 |
Алгоритм выполнения:
a. Для нахождения решения оптимизационной задачи – определения оптимального объема реализации товаров с целью получения максимальной прибыли применим надстройку Поиск решения. Надстройка - вспомогательная программа, служащая для добавления в Microsoft Office специальных команд или возможностей. Надстройка Поиск решения находится в группе Сервис.
b. В модели оптимизации участвуют три элемента: целевая ячейка, изменяемые ячейки и ограничения.
Целевая ячейка представляет задание или цель. Цель задачи получить максимальную прибыль, исходя из имеющихся возможностей. Таким образом, целевой ячейкой будет являться прибыль по всем товарам №1-№4. Для ее определения необходимо создать электронную таблицу 1.1 на основе данных представленных в таблице №1 и ниже добавить одну строку «Прибыль на 1 ед. (тыс.руб.)» = Цена реализации 1 ед. (тыс.руб.) – Цена приобретения 1 ед. (тыс.руб.) (рис.3).
Рис. 3.
Для расчета общей прибыли и ограничений по всем товарам необходимо создать электронную таблицу 1.2 (см. рис. 4 и рис. 5), где в столбце «Ограничение» данные (26 и 19 500) взяты из условия задачи. Ограничение по общей прибыли не заполняется.
Рис. 4.
Для расчета общей прибыли в столбце «Факт» электронной таблицы 1.2 (рис.4) воспользуйтесь формулой СУММПРОИЗВ, она перемножает соответствующие значения в диапазонах ячеек и возвращает сумму этих значений. Прибыль общая вычисляется следующим образом: =СУММПРОИЗВ (диапазон ячеек по показателю «предполагаемый объем реализации» из таблицы 1.1; диапазон ячеек по показателю «прибыль на 1 ед.» из таблица 1.1). Для указанного ниже примера (рис. 5) формула в ячейке В11 («прибыль общая факт») будет выглядеть так: =СУММПРОИЗВ(B2:E2;B8:E8).
Рис. 5. Демонстрация решения указанного практикума
Для расчета количества рейсов в столбце «Факт» необходимо разделить показатель «предполагаемый объем реализации» из таблицы 1.1. на показатель «вместимость машины» и суммировать их по каждому товару №1-№4. Например, в ячейке В12 («кол-во рейсов», рис.5) можно написать:=B2/B5+C2/C5+D2/D5+E2/E5.
Для расчета третьего показателя – общих затрат на приобретение товаров №1-№4 можно воспользоваться указанной выше формулой: =СУММПРОИЗВ (диапазон ячеек по показателю «предполагаемый объем реализации» из таблицы 1.1; диапазон ячеек по показателю «цена приобретения 1 ед.» из таблицы 1.1). Для примера, указанного на рис. 5, формула в ячейке В13 будет выглядеть так: =СУММПРОИЗВ(B2:E2;B7:E7).
Выполнив вышеуказанные действия столбец «Факт» будет полностью заполнен.
c. Откройте диалоговое окно Поиск решения (рис. 5).
Рис. 5.
Целевая ячейка – цель максимизировать прибыль, таким образом, ей соответствует показатель «прибыль общая» из таблицы 1.2. Для указания целевой ячейки щелкните в поле Установить целевую ячейку и затем выберите ячейку с общей прибылью из таблицы 1.2 (ячейка В11).
Изменяемые ячейки – диапазон ячеек показателя «предполагаемый объем реализации» (диапазон B2:E2). Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
Исходя из условий задачи, определены следующие четыре ограничения, которые необходимо внести в диалоговое окно Добавление ограничений нажав кнопку Добавить (рис. 6):
- количество рейсов «факт» <= количество рейсов «ограничение»;
- общие затраты «факт» <= общие затраты «ограничение;
- диапазон «предполагаемый объем реализации» <= диапазон «вместимость склада»;
- диапазон «предполагаемый объем реализации» <= диапазон «предполагаемый максимальный объем реализации». Указанное ограничение присутствует в связи с тем, что предполагаемый объем реализации является возможно максимальным на существующем рынке и не может превысить своего значения, в связи с этим в таблице 1.1 присутствуют две строки с одинаковыми показателями.
Рис. 6.
Так же необходимо ввести ограничение, которое определяет, что все изменяемые ячейки не должны принимать отрицательное значение. Оно задается в диалоговом окне Параметры поиска решения. Щелкните кнопку параметры в диалоговом окне Поиск решения и отметьте опции Линейная модель и Неотрицательные значения (рис. 7).
Модель поиска решения является линейной при соблюдении следующих условий:
- целевая ячейка вычисляется как сумма выражения вида (изменяемая ячейка)*(константа);
- каждое ограничение удовлетворяет требованию линейной модели – каждое ограничение вычисляется как сумма выражения вида (изменяемая ячейка)*(константа) и сравнивается с константой.
Рис. 7.
Если установлен параметр линейная, Поиск решения использует алгоритм симплекс-метода для поиска оптимального решения. Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом в 1947 году.
Если же модель поиска решения линейная, но не установлен параметр линейная, применяется очень неэффективный алгоритм (метод GRG2) и поиск оптимального решения может быть затруднен.
Щелкнув OK в диалоговом окне Параметры поиска решения, активируется диалоговое окно Поиск решения, далее необходимо нажать кнопку Выполнить. Откроется диалоговое окно Результаты поиска решения (рис. 8).
Рис. 8.
Кроме вставки оптимальных значений в изменяемые ячейки, Поиск решения позволяет представлять результаты в виде трех отчетов: Результаты, Устойчивость и Пределы. Для генерации одного или нескольких отчетов необходимо выделить их название в окне диалога Результаты поиска решения.
Выделите отчет Результаты и нажмите кнопку ОК. Отчет будет сформирован в новом листе.
Проанализируйте полученные результаты и сделайте выводы.
Лабораторный практикум №2
«Задача о рюкзаке»: оптимизация загрузки транспортных средств грузами с различными весовыми, объемными, стоимостными и прочими характеристиками
Постановка задачи
В самолет требуется погрузить такой комплект предметов (который может состоять из 4 видов предметов), чтобы эффект от этих предметов был максимальным. Для каждого предмета известны его вес и эффективность. Целевая функция – эффективность (сумма эффективностей каждого вида предметов), которую нужно максимизировать. Единственное ограничение – вес, который может поднять самолет (83 тонны).
Примечание
Данная задача относится к классу «задач о рюкзаке». Такое название возникло из «классической» постановки задачи: турист собирается в поход и планирует взять с собой некоторое количество предметов (грузов) с различной степенью «полезности». Под «полезностью» конкретного предмета понимается совокупность его характеристик, определяющих эффективность использования этого предмета в походе. Для каждого предмета известны его вес и объем (который предмет займет в рюкзаке). Конечно, имеются и ограничения: выносливость туриста (какой вес он может нести) и размер (объем) рюкзака.
Естественно, что общий вес всех предметов, которые целесообразно взять в поход, превышает «грузоподъемность» туриста, а общий объем предметов превышает объем рюкзака.
Поэтому требуется подобрать такую комбинацию предметов, чтобы их суммарная «полезность» была максимальной при выполнении ограничений по весу и объему.
Обобщенная постановка задачи подразумевает самые различные транспортные средства, могут рассматриваться самые различные характеристики грузов – вес, объем и стоимость наиболее очевидны.