Курсовой проект Вариант 20. "Решение оптимизационных задач линейного программирования"

• Название: "Решение оптимизационных задач линейного программирования"
• Дата: 19.09.2022
• Размер: 0.59 Mb.
• Имя файла: Курсовой проект Вариант 20.doc
• Тип: Пояснительная записка; #684806
• страница: 1 из 3

Белорусский государственный университет

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

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

Кафедра информационных технологий автоматизированных систем

РАСЧЕТНО-ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

по курсовой работе

по курсу “Системный анализ и исследование операций”

на тему “Решение оптимизационных задач линейного программирования”

Выполнил студент гр. ****** _____________ ************

(подпись)

Руководитель _____________ Т.В. Тиханович

(подпись)


Минск ****
Содержание
Введение………………………………………………………………….…….3

1 Постановка задачи…………………………………………………….……..7

2 Построение базовой аналитической модели…………………………….....8

3 Обоснование вычислительной процедуры………………………………..10

4 Решение задачи оптимизации на основе симплекс-метода………………11

5 Анализ базовой аналитической модели на чувствительность…………...15

5.1 Статус и ценность ресурсов……………………………………………15

5.2 Анализ на чувствительность к изменению использования

ресурсов………………………………………………………………….16

5.3 Анализ на чувствительность к изменению коэффициента

целевой функции………………………………………………………..16

6 Построение модифицированной аналитической модели и анализ

результатов модификации……………………………………………………18

7 Примеры постановок и решение оптимизационных задач………….…...19

Заключение……………………………………………………………………22

Литература…………………………………………………………………….23

Приложение А ………………………………………………….…….............24

Приложение Б ………………………………………………………………...26

Приложение В…………………………………………………………………27

Приложение Г ………………………………………………………………...29

Приложение Д ……………….………………………………………………..32


Введение

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

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

В последнее время разработан и успешно применяется для решения определенного класса задач метод геометрического программирования.

Как правило, нельзя рекомендовать какой-либо один метод, который можно использовать для решения всех без исключения задач, возникающих на практике. Одни методы в этом отношении являются более общими, другие - менее общими. Наконец, целую группу методов (методы исследования функций классического анализа, метод множителей Лагранжа, методы нелинейного программирования) на определенных этапах решения оптимальной задачи можно применять в сочетании с другими методами, например динамическим программированием или принципом максимума.
Отметим также, что некоторые методы специально разработаны или наилучшим образом подходят для решения оптимальных задач с математическими моделями определенного вида. Так, математический аппарат линейного программирования, специально создан для решения задач с линейными критериями оптимальности и линейными ограничениями на переменные и позволяет решать большинство задач, сформулированных в такой постановке. Так же и геометрическое программирование предназначено для решения оптимальных задач, в которых критерий оптимальности и ограничения представляются специального вида функциями позиномами.
Динамическое программирование хорошо приспособлено для решения задач оптимизации многостадийных процессов, особенно тех, в которых состояние каждой стадии характеризуется относительно небольшим числом переменных состояния. Однако при наличии значительного числа этих переменных, т. е. при высокой размерности каждой стадии, применение метода динамического программирования затруднительно вследствие ограниченных быстродействия и объема памяти вычислительных машин.
Пожалуй, наилучшим путем при выборе метода оптимизации, наиболее пригодного для решения соответствующей задачи, следует признать исследование возможностей и опыта применения различных методов оптимизации. Ниже приводится краткий обзор математических методов решения оптимальных задач и примеры их использования.
Методы исследования функций классического анализа представляют собой наиболее известные методы решения несложных оптимальных задач, с которыми известны из курса математического анализа. Обычной областью использования данных методов являются задачи с известным аналитическим выражением критерия оптимальности, что позволяет найти не очень сложное, также аналитическое выражение для производных. Полученные приравниванием нулю производных уравнения, определяющие экстремальные решения оптимальной задачи, крайне редко удается решить аналитическим путем, поэтому, как, правило, применяют вычислительные машины. При этом надо решить систему конечных уравнений, чаще всего нелинейных, для чего приходится использовать численные методы, аналогичные методам нелинейного программирования.

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

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

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

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

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

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

Команды, которые позволяют решить оптимизационную задачу в Excel:

Подбор параметров для нахождения значения, приводящего к требуемому результату.

Надстройку Поиск решения для расчета оптимальной величины по нескольким переменным и ограничениям;

Диспетчер сценариев для создания и оценки наборов сценариев «что – если» с несколькими вариантами исходных данных.

1 Постановка задачи
Кондитерская фабрика выпускает карамель трёх видов: «Мечта», «Заря», «Полёт». Для производства карамели используется три основных вида сырья: сахарный песок, патока и фруктовое пюре. Фабрика может закупать не более 800 т сахарного песка, не более 600 т потоки и не более 120 т фруктового пюре.

Сырьё закупается по следующим ценам ( за одну тонну): сахарный песок – 1220 ден.ед., потока – 1500 ден.ед., фруктовое пюре – 2100 ден.ед. Нормы расхода сырья (в тоннах) на выпуск одной тонны карамели каждого вида приведены в таблице.

Вид сырья	Расходы на 1 т карамели, т
	«Мечта»	«Заря»	«Полёт»
Сахарный песок	0,8	0,5	0,6
Патока	0,2	0,4	0,3
Фруктовое пюре	-	0,1	0,1

Прочие расходы на выпуск одной тонны карамели составляют 450 ден.ед.

По заказу фабрика должна выпустить не менее 40 т карамели «Мечта».

Карамель продаётся по следующим ценам: «Мечта» - 2040 ден.ед., «Заря» -1990, «Полёт» - 1970 ден.ед./т.

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

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

Введём переменные:

X1 – количество т. выпущенной карамели «Мечта»;

X2 – количество т. выпущенной карамели «Заря»;

X3 – количество т. выпущенной карамели «Полёт»;
На основе условия задачи составим ограничение на использование сырья для производства карамели. Так как сказано, что нельзя закупать более 800 сахарного песка, не более 600 т потока и не более 120 т фруктового пюре, тогда используя таблицу, можем составить ограничения, ограничения примут следующий вид:

0,8Х₁+0,5Х₂+0,6Х₃ 800 – это ограничение на закупку сахарного песка с учётом его потребности для изготовления каждого вида карамели;

0,2Х₁+0,4Х₂+0,3Х₃ 600 – это ограничение на закупку потоки с учётом его потребности для изготовления каждого вида карамели;

0Х₁+0,1Х₂+0,1Х₃ 120 – это ограничение на закупку фруктового пюре с учётом его потребности для изготовления каждого вида карамели;
_{Теперь составим ограничение на основе того, сколько карамели необходимо выпустить фабрике. Так как известно, что нужно поставить не менее 40 т карамели «Мечта», то можно составить следующее ограничение:}

Х₁≥40.
Кроме того, переменные Х₁, Х₂, Х₃, по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество болванок и количество деталей. Поэтому необходимо указать ограничения не отрицательности:

Х_i≥0 i = 1,…,3.
В данной задаче требуется составить план работы предприятия, позволяющий обеспечить максимальную прибыль. Для вычисления прибыли необходимо определить выручку от продажи и затраны на производство карамели.
Посчитаем затраты на производство карамели.

Известно, что затраты на производство одной тонны любой карамети 450 ден.ед., плюс ко всему сырьё, из которого изготавливают карамель, так же имеют свою стоимость, то есть на его закупку также необходимы средства. Так как одна тонна сахарного песка составляет 1220 ден.ед., а нам буден необходимо 0,8Х₁+0,5Х₂+0,6Х₃ тонн этого сырья, то затраты на его закупку составят 1220(0,8Х₁+0,5Х₂+0,6Х₃) ден.ед. Затраты на закупку потока составят 1500(0,2Х₁+0,4Х₂+0,3Х₃) ден.ед., а затраты на закупку фруктового песка 2100(0Х₁+0,1Х₂+0,1Х₃ 120) ден.ед. Таким образом, все затраты, с учетом затрат на производство одной тонны карамели будут иметь вид:

1726Х₁+1870Х₂+1842Х₃.

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

2040Х₁+1990Х₂+1970Х₃.

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

Е=314Х₁+120Х₂+128Х₃ –>max.
Приведем полную математическую модель рассматриваемой задачи:

0,8Х₁+0,5Х₂+0,6Х₃ 800

0,2Х₁+0,4Х₂+0,3Х₃ 600 (2.1)

0Х₁+0,1Х₂+0,1Х₃ 120

Х₁≥40

Х_i≥0 целые, i = 1,…3

Е=314Х₁+120Х₂+128Х₃ –>max (2.2)

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

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