Решение одноиндексных оптимизационных задач. ЛР № 2. Решение одноиндексных оптимизационных задач Цель работы научиться решать одноиндексные оптимизационные задачи производства

• Название: Решение одноиндексных оптимизационных задач Цель работы научиться решать одноиндексные оптимизационные задачи производства
• Анкор: Решение одноиндексных оптимизационных задач
• Дата: 22.05.2023
• Размер: 4.38 Mb.
• Имя файла: ЛР № 2.docx
• Тип: Решение; #1151185
• страница: 1 из 8

Работа № 2. Решение одноиндексных оптимизационных задач

Цель работы – научиться решать одноиндексные оптимизационные задачи производства.

Теоретические основы

Оптимизационные модели

Отличительными признаками оптимизационных моделей являются:

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

Оптимизационная задача в общем виде:

Найти значения переменных , которые удовлетворяют системе неравенств (уравнений):

а_i ( ) ≤ b_i, i = 1,2,…,m (2.1)

и обращают в максимум (или минимум) целевую функцию

F = f( ) → max (min) (2.2)

(Условия неотрицательности переменных, если они есть, входят в ограничения (2.1)).

для решения задачи (2.1) – (2.2) применяются методы математического программирования.

Если целевая функция (1.2) и ограничения (2.1) представлены линейными функциями, то такая задача является задачей линейного программирования.

Если, исходя из содержательного смысла, ее решение должно быть выражено целыми числами, то это задача целочисленного линейного программирования.

Если целевая функция (2.2) и (или) ограничения (2.1) задаются нелинейными функциями, то имеем задачу нелинейного программирования. В частности, если указанные функции обладают свойствами выпуклости, то полученная задача является задачей выпуклого программирования.

Если функции f и (или) а_i в выражениях (2.2) и (2.1) зависят от параметров, то получаем задачу параметрического программирования, если эти функции носят случайный характер, – задачу стохастического программирования.

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

В задаче математического программирования функцию

F= f( ) (2.2) называют целевой функцией; систему неравенств (2.1) – ограничениями задачи.

Из перечисленных методов математического программирования наиболее распространенным и разработанным является линейное программирование.

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

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

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

Цель изучения темы: научиться решать двумерные задачи линейного программирования графическим методом

• 
  двумерная задача линейного программирования
  
• 
  методы решения
  

Двумерная задача линейного программирования задача линейного программирования, количество переменных которой равно 2. Переменные принято обозначать x₁ и x₂.

В общем виде двумерную задачу линейного программирования можно представить в следующем образом.

Определить значение переменных x₁ и x₂, при которых линейная целевая функция F достигает максимум (минимум)

F=с1x₁+с2x₂ -> max (min) при ограничениях на переменные:

(2.3)

Среди ограничений могут одновременно встречаться знаки >= , <= и =. Коэффициенты aij, bi, cj, i=1..m, j =1,2 любые действительные числа (возможно и 0).

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

Пример 1

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





Решение

Построение области допустимых решений целевой функции F

Построим прямоугольную систему кооординат, где ось ОX обозначим за x₁, а OY - за x₂. Так как, согласно условию (2.3) x₁ и x₂ неотрицательны, то можно ограничится расмотрением первого квадранта.

Рассмотрим первое ограничение: 3x₁+4x₂<=1700 (2.1)

Заменим в данном ограничении знак неравенства знаком равентства и постоим прямую.

3x₁+4x₂=1700 (1')

Для этого найдем две точки, принадлежащие данной прямой. Пусть, например, x₁=0, тогда подставив 0 в (1') получим 4x₂=1700 или x₂=425. (0: 425) - координаты первой точки, принадлежащей прямой.

Пусть x₂=0, то 3x₁=1700, следовательно, x₁=567. (567: 0) - координаты второй точки, принадлежащей прямой. Отметим эти точки на числовых осях.

Аналогично, для второго ограничения:

2x₁+5x₂<=1600 (2)

2x₁+5x₂=1600 (2')

При x₁=0, x₂=320 (0; 320)

При x₂=0, x₁=800 (800; 0)

Построим данные прямые (на рисунке они соответственно обозначены (1') и (2')).

Теперь найдем на чертеже такие полуплоскости, которые соответствуют неравенствам (1) и (2).

Прямая (1') 3x₁+4x₂=1700 делит координатную плоскость на две полуплоскости. Одна полуплоскость расположена выше прямой, вторая ниже. Чтобы найти ту полуплоскость, которая соответствует неравенству (1), необходимо взять какую либо точку, принадлежащую одной из полуплоскостей и подставить ее координаты в неравенство. Если неравенство будет верным, то данная полуплоскость является искомой .

Например, возьмем точку с координатами (0; 0) и подставим ее координаты в неравенство (1) 3x₁+4x₂<=1700 или 0+0<=1700. Получается 0<=1700 - данное неравенство является верным, следовательно, неравенству (1) удовлетворяет полуплоскость, лежащая ниже прямой (1') (рис. 2.1).



Рис. 2.1. Графический метод решения примера 1

Аналогично, поступим для неравенства (2) 2x₁+5x₂<=1600. Возьмем точку с координатами (0; 0). Получается 0<=1600 - данное неравенство верно. Неравенству (2) удовлетворяет полуплоскость, расположенная ниже прямой (2').

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

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

Построение прямой уровня.

Возьмем произвольную точку, принадлежащую области допустимых решений - четырехугольнику ОАВС, например, точку М с координатами (100; 100). Подставим координаты точки М в функцию F.

F(100; 100)=2*100+4*100=600.

Прямая уровня будет иметь следующий вид: 2x₁+4x₂=600

Построим полученную прямую. Для этого необходимо найти координаты двух произвольных точек этой прямой. Одна точка у нас уже есть - это точка М(100; 100). Найдем еще одну точку. Пусть x₂=0, тогда x₁=300. Следовательно, координаты дополнительной точки (300; 0). Отметим полученные точки и построит прямую уровня (на рисунке 1 она обозначена (3')).

Значения функции F будут возрастать по мере того, как прямая уровня удаляется от начала координат в положительном квадранте. Направление возрастания функции F будет совпадать с вектором, координаты которого являются коэффициентами при переменных x₁ и x₂ функции F. На рисунке - это вектор a{2; 4}, отложенный от точки М.

Примечание. Обратите внимание, что вектор a, определяющий направление возрастания функции F, всегдa будет перпендикулярен прямой уровня.

Максимизация целевой функции F.

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

Найдем координаты точки B. Данная точка расположена на пересечении двух прямых (1') и (2'), поэтому, чтобы найти ее координаты необходимо решить следующую систему уравнений:



Из второго уравнения выразим x₁



И подставим полученное значение в первое уравнение.



(300; 200) - точка, соответствующая оптимальному решению задачи, следовательно, максимальная прибыль составляет 2*300+4*200=1400 дол. в неделю. Значит, чтобы получить максимальную прибыль, фирме необходимо выпускать в неделю триста полок модели А и двести полок модели В.

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

1. 
   Строим область допустимых решений функции F.
   

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

2. 
   Строим прямую уровня.
   

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

3. 
   Максимизируем (минимизируем) целевую функцию F.
   

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

Пример 2

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



Решение:

Построение области допустимых решений целевой функции F.

Построим прямоугольную систему координат. Так как, x₁ и x₂ неотрицательны, то можно ограничится рассмотрением первого квадранта.

Рассмотрим первое ограничение:

2x₁+4x₂<=8

Заменим в данном ограничении знак неравенства знаком равенства и постоим прямую.

2x₁+4x₂=8 (1)

Найдем две точки, принадлежащие данной прямой.

x₁=0, следовательно, x₂=2: координаты (0; 2).

x₂=0, следовательно, x₁=4: координаты (4; 0)

Рассмотрим второе ограничение:

3x₁+2x₂<=6

3x₁+2x₂ =6 (2)

x₁=0,следовательно, x₂=3: координаты (0; 3).

x₂=0, следовательно, x₁=2: координаты (3; 0)

Рассмотрим третье ограничение:

x₁+x₂<=1

x₁+x₂ =1 (3)

x₁=0, следовательно, x₂=1: координаты (0; 1)

Если x₂=0, то x₁=-1, но мы рассматриваем только первый квадрант, поэтому возьмем другую точку, например, x₁=1, тогда x₂=2: координаты (1; 2)

Отложим полученные точки на числовых осях и найдем полуплоскости, которые соответствуют первым трем ограничениям (на рисунке они указаны стрелками). Заштрихованная область ОАВСD - область допустимых решений функции F (рис. 2.2).



Рис. 2.2. Графический метод решения примера 2

Построение прямой уровня.

Возьмем произвольную точку, принадлежащую области допустимых решений - ОАВСD, например, точку М с координатами (1; 1). Подставим координаты точки М в функцию F.

Получается F(1; 1)=-3*1 - 1=- 4.

Прямая уровня будет иметь следующий вид: -3x₁ - x₂=- 4

Найдем две точки этой прямой - (1; 1) и (0; 4) (если x₁=0, то x₂=4). Построим прямую уровня. Вектор а{-3; - 1}, отложенный от точки М указывает направления возрастания функции F. Минимизируем данную функцию F.

Минимизация целевой функции F.

Так как построенный вектор - является вектором а, указывающем направление возрастания функции F, то передвижение прямой уровня в направлении, обратном вектору а позволит нам найти точку минимума. В нашем случае - это точка D. Координаты точки D равны (2; 0)

Подставляя кординаты точки минимума в функцию F, получим

F(2; 0)= -3*2 - 0= - 6

Ответ: Минимум функция F равен - 6, и он достигается в точке с координатами (2;0)

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

Пример 3

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



Решение:

Построение области допустимых решений целевой функции F (рис. 2.3).



Рис. 2.3. Пример 3

Первое ограничение:

x₁+x₂>=10

x₁+x₂ = 10 (1)

При x₁=0 x₂=10 (0; 10)

При x₂=0 x₁=10 (10; 0)

Второе ограничение:

3x₁+5x₂>=15

3x₁+5x₂ = 15 (2)

При x₁=0 x₂=5 (0; 5)

При x₂=0 x₁=3 (3; 0)

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

Рассмотрим случай, когда область допустимых решений существует. Здесь возможны два варианта:

1. 
   Область допустимых решений ограниченна со всех сторон (примеры №1,2);
   
2. 
   Область допустимых решений неограниченна с какой-либо стороны.
   

Примечание - Область допустимых решений всегда является выпуклым множеством. Множество S называется выпуклым, если для любых двух точек M и N этого множества весь отрезок MN содержится в множестве S. На рисунке 2.4 изображены примеры выпуклых (а) и невыпуклых (б) множеств.

а)

б)

Рис. 2.4. Примеры множеств

Если область допустимых решений ограничена (она представляет собой замкнутый выпуклый N - угольник), то задача разрешима и экстремальное значение достигается в какой - либо вершине области допустимых решений. Исключение составляет тот случай, когда прямая уровня параллельна одной из сторон области допустимых решений, и по условию задачи ее надо перемещать именно в направлении этой стороны. Тогда оптимальное решение будет достигаться в любой точке, принадлежащей данной стороне.

Рассмотрим этот случай на примере.