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

1. Теоретическая часть

Для решения задач линейного программирования в программе Microsoft Excel имеется надстройка Поиск решения , обращение к которой производится из меню Сервис .

Если команда Поиск решения отсутствует в меню Сервис , то требуется установить надстройку «Поиск решения». Для этого в меню Сервис выбирается команда Надстройки , которая открывает диалоговое окно, показанное на рис. 1.

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

Постановка задачи

Предприятие изготавливает и реализует три вида продукции – P 1 , Р 2 и Р 3 . Для производства продукции используются три вида ресурсов – комплектующие изделия, сырье и материалы. Запасы ресурсов и их расход на изготовление единицы продукции каждого вида приведены в табл. 1.

Таблица 1

Прибыль от реализации единицы продукции каждого вида составляет 240, 210 и 180 денежных единиц для P 1 , Р 2 и Р 3 соответственно.

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

Математическая модель задачи

Обозначим переменными x 1 , x 2 и x 3 искомые объемы производства продукции видов P 1 , Р 2 и Р 2 , а через F – прибыль предприятия. Тогда математическая постановка представленной задачи принимает следующий вид.

Определить значения переменных x 1 , x 2 и x 3 , для которых достигается максимум целевой функции

F = 240 x 1 + 210 х 2 + 180 x 3

при ограничениях:

Целевая функция описывает суммарную прибыль от реализации произведенной продукции всех трех видов. Ограничения (1), (2) и (3) учитывают расход и запасы комплектующих изделий, сырья и материалов соответственно. Поскольку объемы производства продукции не могут быть отрицательными, добавляются условия

x 1 ≥ 0; x 2 ≥ 0; x 3 ≥ 0.

Порядок оптимального решения задачи

Примерные действия, необходимые для решения задачи линейного программирования средствами программы Excel, представим в виде последовательности шагов.

Шаг 1. Исходные данные задачи записываются на рабочем листе электронной таблицы. Один из вариантов показан на рис. 2.

Замечание. Если известно исходное допустимое базисное решение, то можно несколько ускорить процесс поиска оптимального решения. Для этого начальные значения некоторых или всех переменных могут быть заданы вручную. В данном примере для их хранения используются ячейки $B$2, $C$2 и $D$2. Если допустимое базисное решение не задано, то программа Excel автоматически определяет начальные значения переменных задачи.

Шаг 2. В ячейку E3 вводится формула

СУММПРОИЗВ(В3:D3; $B$2:$D$2)

для вычисления текущего значения целевой функции, которая находит сумму попарных произведений ячеек (В3:D3) с коэффициентами при переменных в выражении целевой функции на ячейки ($B$2:$D$2) с текущими значениями переменных.

Шаг 3. Чтобы задать ограничения решаемой задачи, в ячейки E5, E6 и E7 копируется формула из ячейки E3. После этого в указанных ячейках должны быть получены формулы, представленные в табл. 2.

Таблица 2

	СУММПРОИЗВ(В5:D5; $B$2:$D$2)
	СУММПРОИЗВ(В6:D6; $B$2:$D$2)
	СУММПРОИЗВ(В7:D7; $B$2:$D$2)

Шаг 4. После создания таблицы с исходными данными курсор устанавливается в ячейку E3, содержащую формулу для вычисления целевой функции. Далее в меню Сервис выбирается команда Поиск решения , которая открывает диалоговое окно, приведенное на рис. 3.

В поле Установить целевую ячейку окна «Поиск решения», показанного на рис. 3, должен появиться адрес ячейки с формулой целевой функции (в данном примере это ячейка $E$3).

Затем в этом окне (рис. 3) заполняются следующие поля этого окна:

В поле Равной переключатель вида экстремума целевой функции устанавливается в положение максимальное значение (или минимальное значение при соответствующей постановке задачи);

В поле Изменяя ячейки указывается диапазон ячеек со значениями переменных задачи, выделяемый на рабочем листе электронной таблицы (в примере это ячейки $B$2:$D$2);

В поле Ограничения задаются ограничения исходной задачи. Для этого курсор устанавливается в поле ввода ограничений и нажимается кнопка Добавить . В результате выводится диалоговое окно «Добавление ограничения», показанное на рис. 4.

В этом окне в поле Ссылка на ячейку вводится адрес ячейки с формулой соответствующего ограничения (например, для ограничения (1) это будет ячейка E5), а в поле Ограничение указывается предельное значение, которое может принимать выбранное ограничение (в данном примере правая часть ограничения (1) находится в ячейке G5).

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

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

После нажатия кнопки Добавить в окне «Добавление ограничения» (или кнопки ОК для ввода последнего ограничения) данное ограничение попадает в список ограничений решаемой задачи. С помощью кнопок Удалить и Изменить можно удалять выделенные в списке ограничения или вносить в них исправления.

Замечание . В окне «Добавление ограничения» можно указать, что все или некоторые переменные должны принимать только целые значения (рис. 5). Это позволяет получать решения задач целочисленного линейного программирования (полностью или частично целочисленных).

Шаг 5. После заполнения всех полей окна «Поиск решения» нажимается кнопка Параметры (рис. 3), которая открывает диалоговое окно «Параметры поиска решения», показанное на рис. 6.

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

Здесь (рис. 6) также можно определить параметры процесса решения: предельное время поиска решения, максимальное количество итераций, точность и т.п. Флажок Показывать результаты итераций позволяет по шагам следить за поиском решения. Флажок Автоматическое масштабирование включается в том случае, когда разброс значений переменных очень велик.

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

Полученные результаты отображаются на рабочем листе электронной таблицы, как это показано на рис. 8. В частности, значения переменных - в ячейках $B$2:$D$2, значение целевой функции – в ячейке E3.

Таким образом, получено оптимальное решение исходной задачи в виде вектора
, где
,
и
, для которого значение целевой функцииF максимально и составляет F * = 129825.

Результаты решения задачи линейного программирования также можно сохранить в виде отдельных рабочих листов с именами Отчет по результатам , Отчет по устойчивости и Отчет по пределам . Для сохранения результатов в виде отчетов необходимо предварительно в поле Тип отчета выделить требуемые типы отчетов (рис. 7). В этом же окне можно отказаться от полученных решений и восстановить исходные значения переменных.

Отчет по результатам для рассмотренной задачи показан на рис. 9.

В данном отчете представлены оптимальное решение задачи линейного программирования и его расположение в области допустимых решений. В графах Результат выводятся оптимальные значения целевой функции F * и переменных задачи
, а также их значения для исходного базисного решения, с которого начинался поиск оптимального решения (графаИсходное значение ). Состояние ограничений (графа Статус ) характеризует расположение точки
в области допустимых решений. ГрафаРазница показывает разности между значениями левых и правых частей ограничений (невязки). Для связанного ограничения невязка равна нулю, что свидетельствует о расположение точки
на границе области допустимых решений, которая задается этим ограничением. Если ограничение являются не связанным, то оно не влияет на оптимальное решение.

Замечание . В экономической интерпретации связанные ограничения соответствуют дефицитным ресурсам. Для не связанных ограничений графа Разница показывает оставшиеся объемы неиспользованных не дефицитных ресурсов. В рассмотренной задаче ограничения (1) и (3) соответствуют комплектующим изделиям и материалам, которые являются дефицитными ресурсами. Ограничение (2) является не связанным, т.е. не влияет на оптимальный план производства продукции по критерию максимальной прибыли. Это означает, что второй ресурс (сырье) не использован в объеме 292,5 ед.

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

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

В отчете по пределам (рис. 11) показаны нижние и верхние пределы возможного изменения переменных (в пределах области допустимых решений) и соответствующие значения целевой функции (графа Целевой результат ) при этих изменениях. В частности, если x 1 = 0, а x 2 и x 3 остаются без изменений, то F = 2400 + 2100 + 180191,25 = 34425; при x 3 = 0 и неизменных x 1 и x 2 получим F = 240397,5 + 2100 + 1800 = 95400.

Решение задач линейного программирования в MS Excel

Инструментом для решений задач оптимизации в MS Excel служит надстройка «Поиск решения». Процедура поис­ка решения позволяет найти оптимальное значение фор­мулы, содержащейся в ячейке, которая называется целе­вой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во вли­яющих ячейках.

Если данная надстройка установлена, то «Поиск реше­ния»запускается из меню «Сервис». Если такого пункта нет, следует выполнить команду «Сервис - Надстройки...» и вы­ставить флажок против надстройки «Поиск решения».

Решение задачи оптимизации состоит из трёх этапов.

A. Создание модели задачи оптимизации.

B. Поиск решения задачи оптимизации.

C. Анализ найденного решения задачи оптимизации.

Рассмотрим подробнее эти этапы.

Этап А.

На этапе создания модели вводятся обозначения неиз­вестных, на рабочем листе заполняются диапазоны исход­ными данными задачи, вводится формула целевой функ­ции.

Этап В.

Команда «Сервис - Поиск решения» открывает диалоговое окно «Поиск решения», в котором, в свою очередь, имеются следующие поля:

«Установить целевую ячейку» - служит для указания целе­вой ячейки, значение которой необходимо максими­зировать, минимизировать или установить равным за­данному числу. Эта ячейка должна содержать форму­лу.

«Равной» - служит для выбора варианта оптимизации зна­чения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить чис­ло, введите его в поле.

«Изменяя ячейки» - служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные огра­ничения и условие оптимизации значения ячейки, указанной в поле «Установить целевую ячейку».

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

«Ограничения» - служит для отображения списка гранич­ных условий поставленной задачи.

«Добавить» - служит для отображения диалогового окна «Добавить ограничение».

«Изменить» - служит для отображения диалоговое окна «Изменить ограничение».

«Удалить» – служит для снятия указанного ограничения.

«Выполнить» – служит для запуска поиска решения по­ставленной задачи.

«Закрыть» - служит для выхода из окна диалога без запус­ка поиска решения поставленной задачи. При этом сохраняются установки сделанные в окнах диалога, появлявшихся после нажатий на кнопки «Парамет­ры, Добавить, Изменить или Удалить».

«Параметры» - служит для отображения диалогового окна «Параметры поиска решения», в котором можно загрузить или сохранить оптимизируемую модель и ука­зать предусмотренные варианты поиска решения.

«Восстановить» - служит для очистки полей окна диалога и восстановления значений параметров поиска ре­шения, используемых по умолчанию.

Для решения задачи оптимизации выполните следую­щие действия.

1. В меню «Сервис» выберите команду «Поиск решения».

2. В поле «Установить целевую ячейку» введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.

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

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

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

4. В поле «Изменяя ячейки» введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку «Предположить».

5. В поле «Ограничения» введите все ограничения, накладываемые на поиск решения.

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

Чтобы восстановить исходные данные, установите пере­ключатель в положение «Восстановить исходные значения».

Этап С.

Для вывода итогового сообщения о результате решения используется диалоговое окно «Результаты поиска реше­ния».

Диалоговое окно «Результаты поиска решения» содер­жит следующие поля:

«Восстановить исходные значения» - служит для восста­новления исходных значений влияющих ячеек моде­ли.

«Отчеты» - служит для указания типа отчета, размещаемо­го на отдельном листе книги.

«Результаты» - используется для создания отчета, состоя­щего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.

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

«Ограничения» - используется для создания отчета, состоя­щего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, зна­чения в которых ограничены множеством целых чи­сел. Нижним пределом является наименьшее значе­ние, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограни­чениям. Соответственно, верхним пределом называ­ется наибольшее значение.

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

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

Предприятие должно производить изделия видов: , причем количество каждого выпускаемого изделия не должно превысить спрос и одновременно не должно быть меньше за­планированных величин соответственно. На изготовление изделий идет m видов сырья , за­пасы которых ограничены соответственно величинами Известно, что на изготовление i -ro изделия идет единиц j -го сырья. Прибыль, получаемая от реализации изделий равна соответственно . Требуется так спланировать производство из­делий, чтобы прибыль была максимальной и при этом выполнялся план на производство каждого изделия, но не превышался спрос на него.

Использование Microsoft Excel для решения задач линейного программирования .

В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel , нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel » внизу окна:

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

Для того чтобы решить задачу ЛП в табличном процессоре Microsoft Excel , необходимо выполнить следующие действия:

1. Ввести условие задачи:

a) создать экранную форму для ввода условия задачи :

· переменных,

· целевой функции (ЦФ),

· ограничений,

· граничных условий;

b) ввести исходные данные в экранную форму :

· коэффициенты ЦФ,

· коэффициенты при переменных в ограничениях,

· правые части ограничений;

c) ввести зависимости из математической модели в экранную форму :

· формулу для расчета ЦФ,

· формулы для расчета значений левых частей ограничений;

d) задать ЦФ (в окне "Поиск решения" ):

· целевую ячейку,

· направление оптимизации ЦФ;

e) ввести ограничения и граничные условия (в окне "Поиск решения" ):

· ячейки со значениями переменных,

· граничные условия для допустимых значений переменных,

· соотношения между правыми и левыми частями ограничений.

2. Решить задачу:

a) установить параметры решения задачи (в окне "Поиск решения" );

b) запустить задачу на решение (в окне "Поиск решения" ) ;

c) выбрать формат вывода решения (в окне "Результаты поиска решения" ).

Рассмотрим подробно использование MS Excel на примере решения следующей задачи.

Задача.

Фабрика "GRM pic" выпускает два вида каш для завтрака - "Crunchy" и "Chewy". Используемые для производства обоих продуктов ингредиенты в основ-ном одинаковы и, как правило, не являются дефицитными. Основным ограничением, накладываемым на объем выпуска, является наличие фонда рабочего времени в каждом из трех цехов фабрики.

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

Цех	Необходимый фонд рабочего времени чел.-ч/т		Общий фонд рабочего времени чел.-ч. в месяц
	"Crunchy"	"Chewy"
А. Производство	10	4	1000
В. Добавка приправ	3	2	360
С. Упаковка	2	5	600

Доход от производства 1 т "Crunchy" составляет 150 ф. ст., а от производства "Chewy" - 75 ф, ст. На настоящий момент нет никаких ограничений на возможные объемы продаж. Имеется возможность продать всю произведенную продукцию.

Требуется:

а) Сформулировать модель линейного программирования, максимизи-рующую общий доход фабрики за месяц.

б) Решить ее c помощью MS Excel.

Формальная постановка данной задачи имеет вид:

(1)
Ввод исходных данных
Создание экранной формы и ввод исходных данных

Экранная форма для решения в MS Excel представлена на рисунке 1.


Рисунок 1.

В экранной форме на рисунке 1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка на листе Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным задачи 1 соответствуют ячейки B4 (), C4 (), коэффициентам ЦФ соответствуют ячейки B6 (150), C6 (75), правым частям ограничений соответствуют ячейки D 18 (1000), D 19 (360), D 20 (600) и т.д.
Ввод зависимостей из формальной постановки задачи в экранную форму

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

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

Рисунок 2

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

· курсор в поле D 6;

· нажав кнопку "

· в окне "Функция" выберитефункцию СУММПРОИЗВ (рис. 3);


Рисунок 3

· в появившемся окне "СУММПРОИЗВ" в строку "Массив 1" введите выражение B $4: C $4 , а в строку "Массив 2" - выражение B 6: C 6 (рис. 4);

Рисунок 4

Левые части ограничений задачи (1) представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B 3, C 3 ), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (B 13, C 13 - 1-е ограничение; B 14, С14 - 2-е ограничение и B 15, С15 - 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл.1.

Таблица 1.
Формулы, описывающие ограничения модели (1)

Левая часть ограничения	Формула Excel
	=СУММПРОИЗВ(B 4: C 4; B 13: C 13))
	=СУММПРОИЗВ(B 4: C 4; B 14: C 14))
	=СУММПРОИЗВ(B 4: C 4; B 15: C 15)

Задание ЦФ

Дальнейшие действия производятся в окне "Поиск решения" , которое вызывается из меню "Сервис" (рис.5):

· поставьте курсор в поле "Установить целевую ячейку" ;

· введите адрес целевой ячейки $ D $6 или сделайте одно нажатие левой клавиши мыши на целевую ячейку в экранной форме ¾ это будет равносильно вводу адреса с клавиатуры;

· введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке "максимальному значению".

Рисунок 5
Ввод ограничений и граничных условий
Задание ячеек переменных

В окно "Поиск решения" в поле "Изменяя ячейки" впишите адреса $ B $4:$С$4 . Необходимые адреса можно вносить в поле "Изменяя ячейки" и автоматически путем выделения мышью соответствующих ячеек переменных непосредственно в экранной форме.
Задание граничных условий для допустимых значений переменных

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

· Нажмите кнопку "Добавить" , после чего появится окно "Добавление ограничения" (рис.6).

· В поле "Ссылка на ячейку" введите адреса ячеек переменных $ B $4:$С$4 . Это можно сделать как с клавиатуры, так и путем выделения мышью всех ячеек переменных непосредственно в экранной форме.

· В поле знака откройте список предлагаемых знаков и выберите .

· В поле "Ограничение" введите 0.

Рис.6 - Добавление условия неотрицательности переменных задачи (1)
Задание знаков ограничений , , =

· Нажмите кнопку "Добавить" в окне "Добавление ограничения" .

· В поле "Ссылка на ячейку" введите адрес ячейки левой части конкретного ограничения, например $ B $18 . Это можно сделать как с клавиатуры, так и путем выделения мышью нужной ячейки непосредственно в экранной форме.

· В соответствии с условием задачи (1) выбрать в поле знака необходимый знак, например, .

· В поле "Ограничение" введите адрес ячейки правой части рассматриваемого ограничения, например $ D $18 .

· Аналогично введите ограничения: $ B $19<=$ D $19 , $ B $20<=$ D $20 .

· Подтвердите ввод всех перечисленных выше условий нажатием кнопки OK .

Окно "Поиск решения" после ввода всех необходимых данных задачи (1) представлено на рис. 5.

Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делают, нажав кнопки "Изменить" или "Удалить" (см. рис. 5).
Решение задачи
Установка параметров решения задачи

Задача запускается на решение в окне "Поиск решения". Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку "Параметры" и заполнить некоторые поля окна "Параметры поиска решения" (рис. 7).

Рис. 7 - Параметры поиска решения, подходящие для большинства задач ЛП

Параметр "Максимальное время" служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).

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

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

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

Параметр "Сходимость" применяется только при решении нелинейных задач.Установка флажка "Линейная модель" обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.

Подтвердите установленные параметры нажатием кнопки " OK " .
Запуск задачи на решение

Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить".

После запуска на решение задачи ЛП на экране появляется окно "Результаты поиска решения" с сообщением об успешном решении задачи, представленном на рис. 8.


Рис. 8 -. Сообщение об успешном решении задачи

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

Если при заполнении полей окна "Поиск решения" были допущены ошибки, не позволяющие Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра "Относительная погрешность" не позволяет найти оптимальное решение. Для исправления этой ситуации увеличивайте погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.

В окне "Результаты поиска решения" представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы" . Они необходимы при анализе полученного решения на чувствительность. Для получения же ответа (значений переменных, ЦФ и левых частей ограничений) прямо в экранной форме просто нажмите кнопку " OK ". После этого в экранной форме появляется оптимальное решение задачи (рис. 9).


Рис.9 - Экранная форма задачи (1) после получения решения

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Частное образовательное учреждение высшего образования «Санкт-Петербургский университет технологий управления и экономики»

Кафедра экономики и менеджмента

КОНТРОЛЬНАЯ РАБОТА

По дисциплине: МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Выполнил:

Студент (ка) 3 курса, группа № 19731Д/3-2

Крюк Альбина Владимировна

Руководитель:

к.э.н., доцент Ж.М. Козлова.

Барнаул 2016

• Введение
• Заключение
• ВВЕДЕНИЕ
• Решение широкого круга задач электроэнергетики и других отраслей народного хозяйства основывается на оптимизации сложной совокупности зависимостей, описанных математически с помощью некоторой «целевой функции» (ЦФ). Подобные функции можно записать для определения затрат на топливо для электростанций, на потери электроэнергии при транспорте ее от электростанции к потребителям и многие другие проблемные задачи. В таких случаях требуется найти ЦФ при определенных ограничениях, накладываемых на ее переменные. Если ЦФ линейно зависит от входящих в ее состав переменных и все ограничения образуют линейную систему уравнений и неравенств, то такая частная форма оптимизационной задачи получила название «задачи линейного программирования».
• Темы контрольной работы «Решение задач линейного программирования в MS Excel», получить практические навыки в использовании электронных таблиц Microsoft Excel и решения оптимизационных задач линейного программирования.

1. Типовые задачи оптимизации и их экономико-математические модели

Экономико-математическое моделирование представляет собой процесс выражения экономических явлений математическими мо­делями. Экономическая модель -- это схематичное представление экономического явления или процесса с использованием научной абстракции, отражение их характерных черт. Математические мо­дели -- основное средство решения задач оптимизации любой дея­тельности. По своей сути эти модели -- средство плановых расче­тов. Ценность их для экономического анализа и оптимизации реше­ний состоит в том, что они позволяют оценить напряженность плановых заданий, определить лимитирующую группу оборудова­ния, видов ресурсов, получать оценки их дефицитности и т.п. Мате­матическое моделирование экономических явлений и процессов дает возможность получить четкое представление об исследуемом объекте, охарактеризовать и количественно описать его внутреннюю струк­туру и внешние связи. Модель -- условный образ объекта управле­ния /1/.

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

1) ана­лиз теоретических закономерностей, свойственных изучаемому яв­лению или процессу и эмпирических данных о его структуре и особенностях; на основе такого анализа формируются модели;

2) определение методов, с помощью которых можно решить задачу;

3) анализ полученных результатов.

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

а) максимизация полезного эффекта товара при ограни­чении совокупности затрат;

б) максимизация прибыли фирмы при условии, что качество товара не снизится; в) снижение себестоимо­сти товара при условии, что его качество не снизится, затраты у потребителя не увеличатся;

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

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

Например, уравнение целевой функции (L) и система ограниче­ний по оптимизации прибыли фирмы (правда, у авторов нет огра­ничений по качеству товара) будет иметь следующий вид:

где хj -- количество производимой продукции j-го вида в нату­ральных измерениях;

Пj -- прибыль, получаемая от производства единицы про­дукции j-го вида;

аij -- норма расхода i-го производственного ресурса на про­изводство единицы j-го вида продукции;

щj -- запасы i-го вида производственного ресурса на рас­сматриваемый период времени.

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

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

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

Решим графическим методом типовую задачу оптимизации

Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный - 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Известно, что для некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 ден. Ед., а улучшенный - 4 ден. Ед. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум, и почему?

Сформулируем прямую оптимизационную задачу.

Пусть х1 - количество обычных наборов удобрений;

х2 - количество улучшенных наборов удобрений.

А для некоторого газона требуется по крайней мере 10 кг азотных удобрений, следовательно:

3х1 + 2х2 ? 10

4х1 + 6х2 ? 20

Стоимость необходимых наборов удобрений составит:

Таким образом, получим следующую экономико-математическую модель задачи:

min (х) = 3х1 + 4х2

3х1 + 2х2 ? 10

4х1 + 6х2 ? 20

Построим область решений системы ограничений. Для этого рассмотрим равенства и построим их графики - прямые.

1) 3х1 + 2х2 ? 10

3х1 + 2х2 = 10

3) х1 + 3х2 ? 7

Неравенство не выполняется, значит, исходному неравенству соответствует полуплоскость, не содержащая точку О(0;0).

х1 = 0 - ось ОХ2.

х2 = 0 - ось ОХ1.

Следовательно, область решений системы ограничений находится только в первой четверти декартовой системы координат.

Рис.1. Графическое решение ЗЛП

Находим общую часть всех построенных полуплоскостей. Это выпуклая заштрихованная область.

Для нахождения оптимального решения задачи изобразим графически функцию цели:

(х) = d1x1 + d2x2

(х) = 3х1 + 4х2

Для этого строим вектор d, начало которого в точке (0;0), а конец в точке (d1;d2).

И строим одну из линий уровня функции цели (это линия, на которой функция цели принимает постоянное значение).

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

Определим координаты точки В:

3х1 + 2х2 = 10 *(-3)

4х1 + 6х2 = 20

9х1 - 6х2 = -30

4х1 + 6х2 = 20

Складываем почленно уравнения и получаем:

(х) = 3*2 + 4*2 = 14 (ден. ед.)

Таким образом, чтобы минимизировать стоимость удобрений, нужно купить 2 обычных набора удобрений и 2 улучшенных набора удобрений. При этом минимальные затраты на покупку удобрений составят 14 денежных единиц. microsoft excel программирование математический

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

2. Задачи линейного программирования, решение средствами MS Excel

Линейное программирование является разделом, с которого начала развиваться дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Задачи линейного программирования является удобной математической моделью для большого числа экономических задач (планирование производства, расходование материалов, транспортные перевозки и т.д.). Использование метода линейного программирования представляет собой важность и ценность - оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями.
В электронных таблицах Excel с помощью функции поиска решения можно вести поиск значения в целевой ячейке, изменения значения переменных. При этом для каждой переменной можно задать ограничения, например верхнюю границу. Перед тем как запустить поиск решения, необходимо четко сформулировать в модели решаемую проблему, т.е. определить условия, выполняемые при оптимизации. Отправленной точкой при поиске оптимального решения является модель вычисления, созданная в рабочем листе. Программе поиска решения при этом необходимы следующие данные. 1. Целевая ячейка - это ячейка в модели вычисления, значения в которой должно быть максимизировано, минимизировано или же равняться определенному указанному значению. Она должна содержать формулу, которая прямо или косвенно ссылается на изменяемые ячейки, или же самой быть изменяемой. 2. Значения в изменяемых ячейках будут последовательно (методом итераций) изменяться до тех пор, пока не будет получено нужное значение в целевой ячейке. Эти ячейки, следовательно, прямо или косвенно должны влиять на значение целевой ячейки. 3. Вы можете задать как для целевой, так и для изменяемых ячеек, ограничения и граничные условия. Можно задать также ограничения для других ячеек. Прямо или косвенно присутствующих в модели. Программа предоставляет возможность задать специальные параметры, определяющие процесс поиска решения. После задания всех необходимых параметров можно запустить поиск решения. Функция поиска решения создаст по итогам своей работы три отчета, которые можно пометить в рабочую книгу.Ограничения - это условия, которые должны быть выполнены аппаратом поиска решения при оптимизации модели.

Изучение литературы показало, что:

1. Линейное программирование - это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

· рационального использования сырья и материалов; задачи оптимизации раскроя;

· оптимизации производственной программы предприятий;

· оптимального размещения и концентрации производства;

· составления оптимального плана перевозок, работы транспорта;

· управления производственными запасами;

· и многие другие, принадлежащие сфере оптимального планирования.

2. Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

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

ЗАКЛЮЧЕНИЕ

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

Благодаря программному продукту Excel, который входит в пакет MS Office, решение наших задач ускоряется в несколько десятков раз. А благодаря точным математическим расчетам данного ПО, мы можем без сомнения найти самые точные результаты исследований.

Размещено на Allbest.ru

...

Подобные документы

Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.

курсовая работа , добавлен 27.08.2012


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

курсовая работа , добавлен 28.04.2014


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

лабораторная работа , добавлен 26.10.2013


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

курсовая работа , добавлен 21.03.2012


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

курсовая работа , добавлен 10.06.2014


Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.

дипломная работа , добавлен 20.11.2010


Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".

курсовая работа , добавлен 29.05.2015


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

курсовая работа , добавлен 07.06.2010


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

курсовая работа , добавлен 13.03.2015


Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.