Работа № 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)

---

Смотрите также файлы

• 3 Социальнопсихологический тренинг общения.doc

• Приоритетные направления начального общего образования в рамках реализации Федерального государственного образовательного стандарта второго поколения.doc

• Едеральное агентство по техническому регулированию и метрологии н ациональный.doc

• Практическая работа Использование библиотеки цифрового образовательного контента в учебной деятельности.docx

• Минобрнауки россии санктПетербургский государственный.docx