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

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

Имеется  предприятие, производящее 2 продукта: А и В. Продукты отличаются по цене: продукт А имеет цену 3 у.е. за тонну, продукт В – 5 у.е. за тонну. Кроме того, производство одной тонны продукта А требует 3, а продукта В -9 единиц сырья. Запас сырья на предприятии ограничен и составляет 75 единиц. Общее количество продуктов А и В не должно превышать 10 тонн, что обеспечит стабильность цен при их продаже.  Производство более дешевого продукта А не может превышать производство более дорогого продукта В более чем на 3 тонны. Расход сырья на производство не может превышать имеющегося запаса в 75 единиц.

С учетом этого сформулируем математически условия задачи. Обозначим как х₁ массу продукта А, а х₂ – массу продукта В соответственно. Тогда целевая функция L будет определяться следующим выражением:

L = 3x₁ + 5x₂ → max.

Требуется определить такие х₁ и х₂, при которых эта функция максимальна.

Из условий задачи вытекает ряд ограничений:

x₁ ≥ 0

x₂ ≥ 0

3x₁ + 9x₂ ≤ 75

x₁ + x₂ ≤ 10

x₁ – x₂ ≤3

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

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

Первое ограничение задачи x₁ ≥ 0 делит пространство переменных на две половины, одна из которых является разрешенным, а другая – запрещенным полупространством. Второе ограничение x₂ ≥ 0 также отсекает от пространства переменных разрешенное полупространство. Оба первых ограничения совместны в первом квадранте декартовой плоскости. Заметим, что и на осях переменных ограничения не нарушаются, поскольку ограничения являются нестрогими неравенствами. Разрешенное полупространство покажем штриховкой.

Третье ограничение задачи 3x₁ + 9x₂ ≤ 75 в предельном виде можно рассматривать как уравнение прямой в выбранной системе координат: 3x₁ + 9x₂ =75, или х₂= -1/3х₁+25. Положение этой прямой показано ниже на рисунке. Разрешенное полупространство расположено ниже прямой.

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

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

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

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

L = 3x₁ + 5x₂. Зададим L произвольное значение, пусть например L=15. Последнее означает, что мы определили в трехмерном пространстве, имеющем ось для отображения целевой функции, некую плоскость, для любой точки которой значение целевой функции неизменно и равно 15, независимо от значений x₁ и х₂. С другой стороны, выражение L = 3x₁ + 5x₂ определяет положение плоскости целевой функции в выбранной системе координат. Плоскость целевой функции проходит через начало координат и наклонена к по отношению к осям переменных. Этот наклон тем больше, чем больше коэффициент при соответствующей переменной.

Выражение 3x₁ + 5x₂=15 означает, что плоскости в пространстве пересекаются. Линия пересечения плоскости постоянного уровня и плоскости целевой функции есть прямая, проекция ее на пространство переменных также является прямой, которая называется прямой опорного решения (ПОР).

В нашей задаче положение ПОР соответствует уравнению прямой х₂=-3/5х₁+3.

Она отсекает на оси х₁ отрезок, равный 5, а на оси х₂ – 3 единицам. Возрастание целевой функции происходит при увеличении х₁ и х₂, что показано стрелками на ПОР на рисунке.

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

Нетрудно заметить, что наиболее далеко отстоящей точкой от ПОР является вершина области допустимых решений С, в которой и будет наибольшее значение целевой функции L. Эта вершина области и будет оптимальным решением нашей задачи.

Положение вершины С определяется решением системы уравнений:

х₁+х₂=10

3х₁+9х₂=75,

что дает координаты С(2,5;7,5). Значение целевой функции при этом равно 45.

ПОР –прямая опорного решения.

3x₁ + 9x₂ = 75

x₁ + x₂ = 10

x₁ = 2,5, x₂ = 7,5

L = 45

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

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

Заключение

Ограниченное время, отпущенное для изучения курса «Моделирование процессов и объектов в металлургии», разумеется, недостаточно для того, чтобы дать студентам знания и навыки, необходимые для решения практических задач моделирования и оптимизации металлургических процессов и аппаратов. Тем более, что металлургические технологии весьма разнообразны, как и оборудование, в котором они реализуются.

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

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

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

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

СОДЕРЖАНИЕ

Введение

1. СИСТЕМНЫЙ АНАЛИЗ

1.1. Основные понятия и определения системного анализа

1.2. Внешние связи системы

1.3. Классификация систем по их свойствам

2. Моделирование технологических процессов

и объектов

2.1. Основные понятия и определения

2.2. Алгоритм создания модели

2.3. Структурный подход для построения математических моделей

2.4. Использование структурного подхода для составления моделей на молекулярном уровне

2.5. Описание стехиометрии системы химических реакций

2.6. Метод направленных графов

2.7. Матричный метод

2.8. Моделирование равновесия в системах химических реакций

2.9. Моделирование кинетики химических реакций

2.10. Скорость сложной химической реакции

2.11. Интегрирование уравнений кинетики

2.12. Численные методы интегрирования

2.13. Химические реакции в потоке вещества

2.14. Моделирование явлений тепло- и массопереноса

2.15. Моделирование тепловых явлений

2.16. Тепловая работа аппарата с частичным теплообменом

3. Математические методы оптимизации технологических систем

3.1. Методы построения обобщённых критериев оптимальности

3.2. Классификация оптимизационных задач

3.3. Аналитические методы решения оптимизационных задач

3.4. Поисковые (численные) методы решения однофакторных

оптимизационных задач

3.5. Поисковые методы решения многофакторных оптимизационных

задач

3.6. Метод координатного спуска

3.7. Градиентные методы

3.8. Симплексные методы

3.9. Экспериментальные методы оптимизации

3.10. Методы линейного программирования

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

Заключение

ЛИТЕРАТУРА

1. Советов Б.Я., Яковлев С.А. Моделирование систем: Учебник для вузов.- 3-е изд., перераб. и доп. М.: Высшая школа, 2007.

2. Советов Б.Я., Яковлев С.А. Моделирование систем: Практикум. М.: Высшая школа, 1999.

3. Кафаров В.В. Методы кибернетики в химии и химической технологии. М.: Химия, 1985.

4. Цымбал В.П. Математическое моделирование металлургических процессов. М.: Металлургия, 1987.

5. Закгейм А.Ю. Введение в моделирование химико – технологических процессов. М.: Химия, 1982.

6. Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988.

7. Банди Б. Основы линейного программирования. М.: Радио и связь, 1989.

8. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986.

9. Введение в системный анализ теплофизических процессов: Учебное пособие для вузов/

Н.А.Спирин, В.С.Швыдкий, В.И.Лобанов, В.В.Лавров. Екатеринбург: УГТУ-УПИ, 1999, 205 с.

10. Оптимизация и идентификация технологических процессов в металлургии: Учебное пособие/ Н.А.Спирин, В.В.Лавров, С.И.Паршаков, С.Г.Денисенко. Екатеринбург, ГОУ ВПО УГТУ-УПИ, 2006. 307 с.

11. Цымбал В.П. Математическое моделирование сложных систем в металлургии: Учебник для вузов/ В.П.Цымбал.-Кемерово; М.: Изд. Объед. «Российские университеты»: Кузбассвузиздат – АСТШ, 2006. 431 с.

12. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ: Учебное пособие для вузов.- М.: Высшая школа, 1989.-367 с.