Лабораторная работа - Решение задач линейного программирования - файл n1.doc

Лабораторная работа - Решение задач линейного программирования
Скачать все файлы (13461.5 kb.)

Доступные файлы (1):
n1.doc13462kb.29.03.2014 21:44скачать

n1.doc



Федеральное агентство по образованию

Государственное образовательное учреждение

Высшего профессионального образования

«Уфимский государственный нефтяной технический университет»


Кафедра «Математические методы в экономике и финансы»

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ

По дисциплине «Математические методы и модели исследования операций»

Выполнил


Проверил _______________ Т.И. Григорчук



Уфа 2008



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

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

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

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

F = 3x1 + x2 + 2x3 ? max

2x1 + 2x2 + x3 ? 70

x1 + 3 x3 ? 200

4x1 + x2 +2x3 ? 40

xj ? 0; j = 1,2,3
Введем исходные данные задачи, зависимости, ограничения и граничные условия в окно программы Exel:




Откроем диалоговое окно Поиск решения (Сервис Поиск решения)

Назначим целевую функцию, введем адреса искомых переменных, добавим ограничения ( ВЗ >= В4, СЗ >= С4, DЗ >= D4 и F9<= Н9, F10 <= Н10, F11 <= H11 )

Настроим параметры поиска решения:



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


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

Построим диаграммы использованных ресурсов и количества продукции, произведенного при оптимальном решении:



Лабораторная работа №2.

Преодоление несовместности задач линейного программирования с помощью Excel.

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

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

В диалоговом окне Поиск решения изменим граничные условия для Прод1: $В$3=0; Прод3: D3=20; введем дополнительное условие для Прод2: С3=5. Решим задачу. На экране появляется диалоговое окно:



Т.е. решение не совместимо.

Для выяснения причин несовместимости введем дополнительные необходимые ресурсы ti (i =1,3). Такая постановка задачи дает возможность определить минимальное значение дополнительных необходимых ресурсов t1,t2, t3.

F = t1 + t2 + t3? min

2x1 + 2x2 + x3 + t1 =70

x1 + 3 x3 + t2=200

4x1 + x2 +2x3 + t3=40

t1 ?0; t2 ? 0; t3 ? 0

Чтобы ввести эту систему, откорректируем таблицу для ввода данных:



В Поиске решения установим целевую ячейку I4 равной минимальному значению. В окно Изменяя ячейки введем В3:Н3. В окно Ограничения введем ограничения и граничные условия: (B3 = 0; I9 <= K9; C3 = 5; F3 >= 0; I10 <= K10; D3 = 20; G3 >= 0; I11 <= K11; H3 >= 0)



Итак, получаем: искомый дополнительный потребный ресурс равен t1 = 0, t2 = 0, t3 = 5. Это значит, что для заданного выпуска продукций необходимо иметь всего следующее количество ресурсов: трудовые - 30; сырье - 60; финансы – 45, при этом будет получена прибыль, равная 45.

Лабораторная работа №3.

Устранение неограниченности целевой функции с помощью Excel.

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

Рассматриваем систему:

х1 + х2 ? 1

х1 ? 0; х2 ? 0

Добавим к системе целевую функцию, тогда получим:

F = x1 ? mах

х12 ? 1

x1 ? 0; х2 ? 0

Задача имеет неограниченную целевую функцию. Посмотрим, как будет решаться такая задача в Ехсеl.



В ходе решения этой задачи на экране появляется диалоговое окно, которое является призна­ком неограниченности целевой функции. Для преодоления этой неограниченности необходимо при максимизации целе­вой функции область допустимых решений ограничить сверху. С этой целью добавим ограничение: х1 + х2 2,

После чего система будет иметь вид:

F = x1 ? mах

х12 ? 1

х1 + х2 2,

x1 ? 0; х2 ? 0
Тогда получим:

Оптимальное решение получено.


Лабораторная работа №4.

Анализ задач линейного программирования с помощью Excel.
Цель: Научиться находить и анализировать решение задачи линейного программирования с помощью Excel.

Ход работы:

Анализ оптимального решения выполняется на основании применения положений симплекс-метода, и начинается после успешного решения задачи, когда на экране появляется диа­логовое окно Результат поиска решения. Решение найдено. С помощью этого диалогового окна можно вы­звать отчеты трех типов (результаты, устойчивость, пределы).

Выполним каждый из этих отчетов в пакете Exel:


Отчет состоит из трех таблиц:

Для Ограничений в графе Формула приведены зависимости, ко­торые были введены в диалоговое окно Поиск решения; в графе Значение приведены величины использованного ресурса; в графе Разница показано количество неиспользованного ресур­са. Если ресурс используется полностью, то в графе Состояние указывается связанное; при неполном использовании ресурса в этой графе указывается не связан.

Отчет по устойчивости состоит из двух таблиц.



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

- результат решения задачи;

- нормированная стоимость, т. е. дополнительные двойственные пе­ременные vj, которые, пока­зывают, насколько изменяется целевая функция при при­нудительном включении единицы этой продукции в опти­мальное решение;

- коэффициенты целевой функции;

- предельные значения приращения коэффициентов ∆сj; це­левой функции, при которых сохраняется набор перемен­ных, входящих в оптимальное решение.

В таблице 2 приводятся аналогичные значения для ограничений:

- величина использованных ресурсов;

- теневая цена, т. е. двойственные оценки а, которые пока­зывают, как изменится целевая функция при изменении ресурсов на единицу;

- значения приращения ресурсов ∆bj;, при которых сохраня­ется оптимальный набор переменных, входящих в опти­мальное решение.
В отчете по пределам показано, в каких пределах может изменяться выпуск продукции, вошедшей в оптимальное решение, при сохранении структуры оптималь­ного решения:

- приводятся значения хj в оптимальном решении;

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


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

Далее приводятся верхние пределы изменения хj и значения целевой функции при выпуске продукции, вошедшей в опти­мальное решение на верхних пределах.

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

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

Составим таблицу вариантов:



Введем в ячейку Н11 = 50.

Выполним Поиск решения, сохранив при этом сценарий.



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



На экране отчет Итоговый сценарий:



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

Для удобства дальнейшей работы выполним редактирование Итогового сценария.



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



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

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

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

Ход работы:

В задаче распределения ресурсов возможны две постановки:

- максимизация результата при заданных ресурсах;

- минимизация используемых ресурсов при заданном ре­зультате.

Добавим к задаче рассмотренной в лабораторной работе № 2 следующие условия:

  1. Назначим граничные условия на все виды выпускаемой продукции 1 ? Прод* ? 5, которые введем в ячейки В6:В7



2. Сформулируем целевые функции для решения задачи в двух постановках.

Для решения задачи при минимизации используемых ресурсов в нашу математическую модель введем дополнительные переменные и запишем задачу в следующем виде:

F = y1 + y1 +y1 ? max

2x1 +2 x2 +1 x3 + у1= 70

x1 + 3 x3 + у2 = 200

4x1 + x2 -2x3 + у3= 40

1 ? xj ? 3; j = 1, 3

В системе величины у1, у2, у3 — это дополнительные пе­ременные, которые определяют величину неиспользованного ресурса. Следователь­но, если мы хотим минимизировать используемые ресурсы, то должны максимизировать неиспользуемые ресурсы.



Решим задачу последовательно по всем целевым функциям и сделаем отчет:



Выполним редактирование Итогового сценария.


Представим полученные результаты в виде трехмерной гистограммы.


Найдем оптимальное решение при заданном значении функции. Введем в целевую ячейку I6 назначаемую величину 100. Получаем:


Лабораторная работа №6.

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

Введем дополнительные ограничения для переменных:



Получаем, что условия задачи несовместны.
Назначим число трудовых ресурсов Н9 = 10 и выполним поиск решения.



На экране: результат решения из которого вид­но, что при данных условиях следует выпускать только Прод3=10.

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

Решение этих задач начнем с оптимизации условной целевой функции. Основной логической функцией, применяемой при такой оптимизации, является логическая функция ЕСЛИ, имеющая формат записи: =ЕСЛИ (А;С3;С4),



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


Вывод


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


Учебный текст
© perviydoc.ru
При копировании укажите ссылку.
обратиться к администрации