Министерство образования и науки Украины

Севастопольский национальный технический

университет

РЕШЕНИЕ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

И АНАЛИЗ ОПТИМАЛЬНОГО РЕШЕНИЯ

НА ЭВМ Методические указания к индивидуальным занятиям и подготовке к курсовой работе по дисциплине «Прикладная математика»

для студентов специальности 7.091501 «Компьютерные системы и сети»

дневной формы обучения Севастополь Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) УДК 519.688 (07) Методические указания к индивидуальным занятиям и подготовке к курсовой работе по разделу «Решение задач линейного программирования и анализ оптимального решения на ЭВМ» дисциплины «Прикладная математика» для студентов специальности 7.091501 «Компьютерные системы и сети» дневной формы обучения /Сост. Л.П. Луговская, Н.А. Скаткова. – Севастополь: Изд-во СевНТУ, 2009. – 15 с.

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

Методические указания рассмотрены и утверждены на заседании кафедры кибернетики и вычислительной техники (протокол № 5 от 19.01.2009 г.).

Допущено учебно-методическим центром СевНТУ в качестве методических указаний.

Рецензент – старший преподаватель кафедры высшей математики Ларионова Е.Н.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

СОДЕРЖАНИЕ

1. Решение задач линейного программирования на ЭВМ………... 1.1. Постановка задачи………………………………………………... 1.2. Ввод исходных данных…………………………………………... 1.3. Поиск решения…………………………………………………… 2. Анализ оптимального решения на ЭВМ……………………….. 2.1. Двойственная задача……………………………………………... 2.2. Анализ оптимального решения…………………. 2.3. Анализ устойчивости оптимального решения…………………. 2.4. Анализ допустимых пределов изменения параметров задачи… Библиографический список Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

1. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ЭВМ

1.1. Постановка задачи Рассмотрим пример задачи линейного программирования.

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

Таблица 1 – Нормы расхода ресурсов при производстве продукции Ресурс Изделие 1 Изделие 2 Изделие 3 Изделие 4 Наличие Трудовые ресурсы 1 1 1 1 Сырье 6 5 4 3 Финансы 4 6 10 13 Стоимость изделия 60 70 120 130 -Математическая модель задачи имеет вид:

F 60 x1 70 x 2 120 x 3 130 x 4 max x1 x 2 x 3 x 4 16, (1) 6 x1 5 x 2 4 x 3 3x 4 x1 6 x 2 10 x 3 13 x где xj – количество выпускаемой продукции j-го типа; F – функция цели; в левых частях выражений ограничений указаны величины потребного ресурса, а правые части показывают количество имеющегося ресурса.

Для решения задачи с помощью Excel следует создать форму для ввода исходных данных и ввести их. Форма ввода показана на рисунке 1.

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

В ячейки F8:F10 введены левые части ограничений для ресурсов каждого Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) Рисунок 1- Форма ввода условий задачи линейного программирования Рисунок 2 - Форма ввода исходных данных в режиме вывода формул Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) Для решения задач линейного программирования в Excel используется мощный инструмент, называемый Поиск решения. Обращение к Поиску решения осуществляется из меню Сервис, на экран выводится диалоговое окно Поиска решения (рисунок 3).

Ввод условий задачи для поиска ее решения состоит из следующих шагов:

1) Назначить целевую функцию, для чего установить курсор в поле Установить целевую ячейку окна Поиск решения и щелкнуть в ячейке F6 в форме ввода;

2) Включить переключатель значения целевой функции, т.е. указать ее Равной Максимальному значению;

3) Ввести адреса изменяемых переменных (xj): для этого установить курсор в поле Изменяя ячейки окна Поиск решения, а затем выделить диапазон ячеек B3:E3 в форме ввода;

4) Нажать кнопку Добавить окна Поиск решения для ввода ограничений задачи линейного программирования; на экран выводится окно Добавление ограничения (рисунок 4) :

этого в поле Ссылка на ячейку указать ячейку В3, соответствующую х1, выбрать из списка нужный знак (), в поле Ограничение указать ячейку формы ввода, в которой хранится соответствующее значение граничного условия, (ячейка В4), нажать кнопку Добавить; повторить поле Ссылка на ячейку окна Добавление ограничения указать ячейку Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) F9 формы ввода, в которой содержится выражение левой части ограничения, наложенного на трудовые ресурсы, в полях Ограничение указать знак и адрес Н9 правой части ограничения, нажать кнопку Добавить; аналогично ввести ограничения на остальные виды ресурсов;

Рисунок 4 – Окно добавления ограничений Решение задачи линейного программирования начинается с установки параметров поиска:

выводится окно Параметры поиска решения (рисунок 5);

что подходит для решения большинства задач);

если необходимо просмотреть все этапы поиска оптимального решения;

Рисунок 5 – Окно задания параметров поиска решения Для решения задачи нажать кнопку Выполнить в окне Поиск решения, на экране – окно Результаты поиска решения (рисунок 6), в котором содержится сообщение Решение найдено. Все ограничения и условия оптимальности Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) выполнены. Если условия задачи несовместны, то выводится сообщение Поиск не может найти подходящего решения. Если целевая функция не ограничена, то появляется сообщение Значения целевой ячейки не сходятся.

Рисунок 6 – Окно результатов поиска решения Для рассматриваемого примера решение найдено и результат оптимального решения задачи выводится в форме ввода: значение целевой функции, соответствующее максимальной прибыли и равное 1320, указывается в ячейке F формы ввода, оптимальный план выпуска продукции х1=10, х2=0, х3=6, х4= указывается в ячейках В3:С3 формы ввода (рисунок 7).

Количество использованных для выпуска продукции ресурсов выводится в ячейки F9:F11: трудовых – 16, сырья – 84, финансов – 100.

Рисунок 7 – Результаты решения задачи линейного программирования Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) Если при установке параметров в окне Параметры поиска решения (рисунок 5) был установлен флажок Показывать результаты итераций, то будут показаны последовательно все шаги поиска. На экран будет выводиться окно Текущее состояние поиска решения (рисунок 8). При этом текущие значения переменных и функции цели будут показаны в форме ввода. Так, результаты первой итерации поиска решения исходной задачи представлены в форме ввода на рисунке Рисунок 8 – Окно текущего состояния поиска решения Рисунок 9 – Отображение результатов первой итерации поиска решения Чтобы продолжить поиск решения, следует нажимать кнопку Продолжить в окне Текущее состояние поиска решения.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

2. АНАЛИЗ ОПТИМАЛЬНОГО РЕШЕНИЯ

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

Составим для исходной задачи двойственную задачу и введем дополнительные двойственные переменные vi.

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

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

Для вызова отчета в поле Тип отчета выделить название нужного типа и нажать ОК.

Отчет по результатам (рисунок 10) состоит из трех таблиц:

Исходно указывается значение целевой функции до начала вычислений;

полученных в результате решения задачи (оптимальный план выпуска Для ограничений в графе Формула приведены зависимости, которые были введены при задании ограничений в окне Поиск решения; в графе Значение указаны величины использованного ресурса; в графе Разница показано количество неиспользованного ресурса. Если ресурс используется полностью, то в графе Состояние выводится сообщение связанное; при неполном использовании ресурса в этой графе указывается не связан. Для граничных условий приводятся Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) аналогичные величины с той лишь разницей, что вместо неиспользованного ресурса показана разность между значением переменной xj в найденном оптимальном решении и заданным для нее граничным условием (xj0).

Именно в графе Разница можно увидеть значения дополнительных переменных yi исходной задачи в формулировке (2). Здесь у1=у3=0, т.е. величины неиспользованных трудовых и финансовых ресурсов равны нулю. Эти ресурсы используются полностью. Вместе с тем, величина неиспользованных ресурсов для сырья у2=26, значит, имеются излишки сырья.

Рисунок 10 – Отчет по результатам поиска решения Отчет по устойчивости (рисунок 11) состоит из двух таблиц.

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

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) сколько изменится целевая функция при принудительном включении единицы продукции соответствующего типа в оптимальный план;

функции, при которых сохраняется оптимальный план выпуска.

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

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

Рисунок 11 – Отчет по устойчивости оптимального решения Отчет по устойчивости позволяет получить двойственные оценки.

Как известно, двойственные переменные zi показывают, как изменится целевая функция при изменении ресурса i-го типа на единицу. В отчете по устойчивости двойственная оценка называется Теневой ценой.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) В нашем примере сырье не используется полностью и его ресурс у2=26.

Очевидно, что увеличение количества сырья, например, до 111 не повлечет за собой увеличения целевой функции. Следовательно, для второго ограничения двойственная переменная z2=0. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет больше нуля, а двойственная оценка этого ограничения равна нулю.

В рассматриваемом примере трудовые ресурсы и финансы использовались полностью, поэтому их дополнительные переменные равны нулю (у1=у3=0). Если ресурс используется полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции, и, следовательно, на величину целевой функции.

Двойственные оценки ограничений на трудовые и финансовые ресурсы отличны от нуля, т.е. z1=20, z3=10.

Значения двойственных оценок находим в отчете по устойчивости, в таблице 2, в графе Теневая цена.

При увеличении (уменьшении) трудовых ресурсов на единицу целевая функция увеличится (уменьшится) на 20 единиц и будет равна F=1320+201=1340 ( при увеличении).

Аналогично, при увеличении объема финансов на единицу целевая функция Здесь же, в графах Допустимое увеличение и Допустимое уменьшение таблицы 2, показаны допустимые пределы изменения количества ресурсов j-го вида.

Например, для при изменении приращения величины трудовых ресурсов в пределах от –6 до 3,55, как показано в таблице, структура оптимального решения сохраняется, т.е. наибольшую прибыль обеспечивает выпуск Прод1 и Прод3, но в других количествах.

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

Если основные переменные не вошли в оптимальное решение, т.е. равны нулю ( в примере х2=х4=0), то соответствующие им дополнительные переменные имеют положительные значения (v2=10, v4=20). Если же основные переменные вошли в оптимальное решение (х1=10, х3=6), то их дополнительные двойственные переменные равны нулю (v1=0, v3=0).

Эти величины показывают, насколько уменьшится (поэтому знак минус в значениях переменных v2 и v4) целевая функция при принудительном выпуске единицы данной продукции. Следовательно, если мы захотим принудительно выпустить единицу продукции вида Прод3, то целевая функция уменьшится на единиц и будет равна 1320 -101 =1310.

Обозначим через сj изменение коэффициентов целевой функции в исходной модели (1). Эти коэффициенты определяют прибыль, получаемую при реализации единицы продукции j-го вида.

В графах Допустимое увеличение и Допустимое Уменьшение таблицы отчета по устойчивости показаны пределы изменения сj, при которых сохраняется структура оптимального плана, т.е. будет выгодно по-прежнему выпускать продукцию вида j. Например, при изменении с1 в пределах -12 с1 40, как Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) показано в отчете, по-прежнему будет выгодно выпускать продукцию первого вида. При этом значение целевой функции будет F=1320+x1сj =1320+10сj.

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

Например, если при оптимальном решении х1=10, х2=0, х3=6, х4=0 положить х1= (нижний предел) при неизменных х2, х3 и х4, то значение целевой функции будет равно 600+700+1206+1300=720.

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

Поэтому везде F=1320.

Рисунок 12 – Отчет по пределам изменений параметров задачи Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Степанов А. Г. Разработка управленческого решения средствами пакета Excel: учеб. пособие/ А.Г. Степанов. – СПб.:Изд-во СПбГУАП, 2001. - 172 с.

2. Волков И.К., Загоруйко Е.А. Исследование операций: учеб. для вузов / И.К.

Волков, Е.А. Загоруйко; под ред. В.С. Зарубина, А.П. Крищенко. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. - 436 с.

3. Таха Х. А. Введение в исследование операций, 6-е издание. [пер. с англ.]/ А.Х. Таха. - М.: Издательский дом «Вильямс», 2001. - 912 с.

4. Конюховский П. В. Математические методы исследования операций в экономике/ П.В. Конюховский. – СПб.: Изд-во «Питер», 2001. - 192 с.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)