Линейное программирование

Содержание

Слайд 2

Линейное про­граммирование – раздел математического программирования, применяемый при разработке методов отыскания

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

Слайд 4

Наиболее часто используются оптимизационные модели принятия решений. Их общий вид таков:
F(X) →

Наиболее часто используются оптимизационные модели принятия решений. Их общий вид таков: F(X)
max;
X ϵ A,
где Х - параметр, который менеджер может выбирать (управляющий параметр). Он может иметь различную природу - число, вектор, множество и т.п.

Слайд 5

Цель менеджера - максимизировать целевую функцию F(X), вы­брав соответствующий Х. При этом

Цель менеджера - максимизировать целевую функцию F(X), вы­брав соответствующий Х. При этом
он должен учитывать ограничения X ϵ A на возможные значения управляющего параметра Х - он должен лежать в множестве А. Рассмотрим примеры оптимизационных задач менеджмента.
Среди оптимизационных задач менеджмента наиболее известны задачи линейного программирования, в которых максимизируемая функция F(X) линейная, а ограничения А задаются линейными не­равенствами.

Слайд 6

Производственная задача. Цех может производить стулья и сто­лы. На производство стула идет

Производственная задача. Цех может производить стулья и сто­лы. На производство стула идет
5 единиц материала, на производство стола — 20 единиц (футов красного дерева). Стул требует 10 человеко- часов, стол — 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула — 45 дол. США, при производстве стола — 80 дол. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

Слайд 7

Обозначим Х1 число изготовленных стульев, Х2 — число столов. Задача оптимизации имеет

Обозначим Х1 число изготовленных стульев, Х2 — число столов. Задача оптимизации имеет
вид:
45Х1 + 80Х2 → max;
5Х1 + 20Х2 < 400;
10Х1 + 15Х2 < 450;
Х1 > 0; Х2 > 0.

Слайд 8

В первой строке выписана целевая функция — прибыль при выпуске Х1 стульев

В первой строке выписана целевая функция — прибыль при выпуске Х1 стульев
и Х2 столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х1 и Х2. При этом должны быть выполнены ограничения по материалу (вторая строчка) — истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) — затрачено не более 450 ч.

Слайд 9

Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если

Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если
Х1 = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то Х1 положительно. Но невозможно представить себе отрицательный выпуск — Х1 не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.

Слайд 10

Условия производственной задачи можно изобразить на координатной плоскости. Будем по оси абсцисс

Условия производственной задачи можно изобразить на координатной плоскости. Будем по оси абсцисс
откладывать значения Х1, а по оси ординат — значения Х2. Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х1, Х2) объемов выпуска в виде треугольника (рис. 1).

Слайд 11

Рис. 1. Ограничения по материалу

Рис. 1. Ограничения по материалу

Слайд 12

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

Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, в данном
случае — треугольника. Этот треугольник получается путем отсечения от первого квадранта примы­кающей к началу координат зоны. Отсечение проводится прямой, соот­ветствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х1, соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев.

Слайд 13

Та же прямая пересекает ось Х2, соответствующую столам, в точке (0,20). Это

Та же прямая пересекает ось Х2, соответствующую столам, в точке (0,20). Это
означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 сто­лов. Для всех точек внутри треугольника выполнено неравенство, что означает — материал останется. Аналогичным образом можно изобразить и ограничения по труду (рис. 2).

Слайд 14


Рис. 2. Ограничения по труду

Рис. 2. Ограничения по труду

Слайд 15

Ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника,

Ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника,
который получается аналогично — путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х1, соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х2, соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, что означает — часть рабочих будет простаивать.

Слайд 16

Мы видим, что очевидного решения нет — для изготовления 80 стульев есть

Мы видим, что очевидного решения нет — для изготовления 80 стульев есть
материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то и другое. Но в каком соотношении?
Чтобы ответить на этот вопрос, надо «совместить» рис. 1 и рис. 2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис. 3).

Слайд 18

Таким образом, множество возможных значений объемов вы­пуска стульев и столов (Х1, Х2),

Таким образом, множество возможных значений объемов вы­пуска стульев и столов (Х1, Х2),
или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизаци­онной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис. 3. Три его вершины очевидны — это (0,0), (45,0) и (0,20). Четвертая — это пересечение двух прямых — границ треугольников на рис. 1 и рис. 2, т.е. решение сис­темы уравнений
5Х1 + 20Х2 = 400;
10Х1 + 15Х2 = 450.

Слайд 19

Из первого уравнения: 5Х1 = 400 - 20 Х2, Х1 = 80

Из первого уравнения: 5Х1 = 400 - 20 Х2, Х1 = 80
- 4Х2. Подставляем значение X1, выраженное через X2, во второе уравнение:
10(80 - 4Х2) + 15Х2 = 800 - 40Х2 + 15Х2 = 800 - 25Х2 = 450,
следовательно, 25Х2 = 350, Х2 = 14, откуда Х1 = 80 - 4 х 14 = 80 - 56 = 24. Итак, четвертая вершина четырехугольника — это (24, 14).

Слайд 20

Надо найти максимум линейной функции на выпуклом многоу­гольнике. (В общем случае линейного

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