Решение одноиндексных оптимизационных задач. ЛР № 2. Решение одноиндексных оптимизационных задач Цель работы научиться решать одноиндексные оптимизационные задачи производства
 Скачать 4.38 Mb.
|
|
Пример 4 Решить графическим способом следующую двумерную задачу линейного программирования:  Решение Построение области допустимых решений целевой функции F. Построим прямоугольную систему координат. Так как, x1 и x2 неотрицательны, то можно ограничится рассмотрением первого квадранта (рис 2.5).  Рис.. 2.5. Пример 4 Рассмотрим первое ограничение:  Рассмотрим второе ограничение:  Отложим полученные точки на числовых осях и найдем полуплоскости, которые соответствуют первым трем ограничениям (на рисунке они указаны стрелками). Заштрихованная область ОАВС - область допустимых решений функции F. Построение прямой уровня. Возьмем произвольную точку, принадлежащую области допустимых решений - ОАВС, например, точку М с координатами (1; 1). Подставим координаты точки М в функцию F. F(1; 1)=-31 - 1=- 4 Прямая уровня будет иметь следующий вид: -3x1 - x2=- 4 Найдем две точки этой прямой - (1; 1) и (0; 4) (если x1=0, то x2=4). Построим прямую уровня. Вектор a{-3; - 1}, отложенный от точки М указывает направления возрастания функции F. Минимизируем данную функцию F. Минимизация целевой функции F. Так как построенный вектор a - является вектором, указывающем направление возрастания функции F, то передвижение прямой уровня в направлении, обратном вектору a позволит нам найти точку минимума. Но так как прямая уровня параллельна прямой (2), то любая точка на отрезке ВС является оптимальным решением. В частности в вершинах В(1,5 ; 1,5) и С(2; 0). F(1,5; 1,5)= F(2; 0) = - 6 Ответ: Минимум функции F равен - 6, и он достигается в любой точке, принадлежащей отрезку ВС. Пример 5 Решить графическим способом следующую двумерную задачу линейного программирования:  Решение: Построение области допустимых решений целевой функции F. Построим прямоугольную систему координат. Так как, x1 и x2 неотрицательны, то можно ограничится рассмотрением первого квадранта (рис 2.6). Рассмотрим первое ограничение:  Рассмотрим второе ограничение:  x2 =2 - прямая, проходящая через точку (0; 2) параллельно оси X1. Отложим полученные точки на числовых осях и найдем полуплоскости, которые соответствуют первым двум ограничениям (на рисунке они указаны стрелками). Заштрихованная область АВСD - область допустимых решений функции F.  Рис. 2.6. Пример 5 Построение прямой уровня. Возьмем произвольную точку, принадлежащую области допустимых решений - АВСD, например, точку М с координатами (2,5; 1). F(3; 1)=2,5+1=3,5 Прямая уровня будет иметь следующий вид: x1+x2=3,5 Найдем две точки этой прямой - (2,5; 1) и (0; 3,5) (если x1=0, то x2=3,5). Построим прямую уровня. Вектор а {1; 1}, отложенный от точки М указывает направления возрастания функции F. Максимизируем данную функцию F. Максимизация целевой функции F. Так как область допустимых решений неограниченна в направлении, в котором функция F возрастает, то не существует конечной точки, в которой функция F достигала бы максимума. Таким образом, данная задача не имеет решений. Ответ: Задача не имеет решений. Примечание - Если бы в рассмотренной выше задачи требовалось минимизировать функцию, при тех же ограничениях, то минимум достигался бы в единственной точке С(1; 0) и был бы равен 1. Таким образом, если область допустимых решений неограниченное множество, то задача может иметь решение, а может и не иметь. Это зависит от того, в каком направлении возрастает (убывает) функция F, и совпадает ли это направлению с направлением неограниченности области допустимых решений. Вывод: При решении двумерных задач линейного программирования возможны следующие ситуации (ОДР - область допустимых решений) (рис. 2.7):  Рис. 2.7. Ситуации ОДР Пример 6 Построить математическую модель формирования плана производства. Решить ее графическим методом. Имеется производство по изготовлению двух видов продукции А и В при ограниченном объеме материалов трех сортов, из которых производится продукция. Исходные данные приведены в таблице.  Определить объем производства продукции, обеспечивающий получение максимальной прибыли. Построение математической модели. Пусть x1 - количество продукции вида А, а x2 - количество продукции В. Тогда x1+4x2 - количество материала сорта 1, требуемое на изготовление продукции, а по условию задачи это число не превышает 320 x1+4x2<=320 (1) 3x1+2x2 - количество материала сорта 2, требуемое на изготовление продукции, а по условию задачи это число не превышает 360 3x1+2x2<=360 (2) x1+2x2 - количество материала сорта 2, требуемое на изготовление продукции, а по условию задачи это число не превышает 180 x1+2x2<=180 (3) Кроме того, поскольку x1 и x2 выражают объем выпускаемых продукции, то они не могут быть отрицательными, то есть x1>=0, x2>=0 (4) F=x1+2x2 - прибыль, которая должна быть максимальной. Таким образом, имеем следующую математическую модель для данной задачи.  Решение: Построение области допустимых решений целевой функции F. Построим прямоугольную систему координат. Так как, x1 и x2 неотрицательны, то можно ограничится рассмотрением первого квадранта. Рассмотрим первое ограничение:  Рассмотрим второе ограничение:  Рассмотрим третье ограничение:  Отложим полученные точки на числовых осях и найдем полуплоскости, которые соответствуют данным ограничениям (на рисунке они указаны стрелками). Заштрихованная область ОАВСD - область допустимых решений функции F. Построение прямой уровня. Возьмем произвольную точку, принадлежащую области допустимых решений - ОАВСD, например, точку М с координатами (20; 20). F(20; 20)=20+2*20=60 Прямая уровня будет иметь следующий вид: x1+2x2=60 Найдем две точки этой прямой - (20; 20) и (60; 0) (если x2=0, то x1=60). Построим прямую уровня. Вектор а {1; 2}, отложенный от точки М указывает направления возрастания функции F. Максимизируем данную функцию F (Рис. 2.8).  Рис. 2.8. Пример 6 Максимизация целевой функции F. Так как построенный вектор a - является вектором, указывающем направление возрастания функции F, то передвижение прямой уровня в направлении вектора a позволит нам найти точку максимума. В нашем случае - это точка В. Данная точка расположена на пересечении двух прямых (1) и (3), поэтому, чтобы найти ее координаты необходимо решить следующую систему уравнений:  Вычтем из второго уравнения первое. Получается 2x2=140 или x2 =70 . Подставим найденное значение x2 в первое уравнение: x1=180 - 140=40 (40; 70) - точка, соответствующая оптимальному решению задачи, следовательно, максимальная прибыль составляет 40+2*70=180. Значит, чтобы получить максимальную прибыль, фирме необходимо выпускать сорок единиц продукции вида А и семьдесят единиц продукции вида В. Ответ: Для получения максимальной прибыли необходимо выпускать 40 единиц продукции вида А и 70 единиц продукции вида В. Решение задач линейного программирования симплексным методом Графический метод позволяет наглядно представить процедуру поиска оптимального решения задачи линейного программирования, но, в силу ограниченности размерности задачи, играет лишь иллюстративную роль. Симплексный метод – универсальный метод, позволяющий найти решение любой задачи линейного программирования (ЗЛП), если, разумеется, задача разрешима. Этот метод осуществляет направленный перебор вершин допустимого множества (опорных планов ЗЛП), то есть позволяет из начальной вершины за кратчайшее число шагов перейти в точку оптимума. Применяют симплекс-метод к задаче канонического (стандартного) вида, в которой все ограничения – равенства с неотрицательной правой частью и на все переменные накладывается условие неотрицательности. Для перехода от ограничений задачи, представленных в виде неравенств, к ограничениям-равенствам в левую часть неравенства вводятся неотрицательные дополнительные переменные с коэффициентами (+1), если неравенство имеет вид « ≤ », и с коэффициентами (-1) в случае неравенства вида « ≥ ». В целевую функцию дополнительные переменные входят с коэффициентом 0. Алгоритм симплекс-метода Алгоритм симплекс-метода находит оптимальное решение, рассматривая ограниченное количество допустимых базисных решений. Алгоритм симплекс-метода всегда начинается с некоторого допустимого базисного решения и затем пытается найти другое допустимое базисное решение, "улучшающее" значение целевой функции. Это возможно только в том случае, если возрастание какой-либо нулевой (небазисной) переменной ведет к улучшению значения целевой функции. Но для того, чтобы небазисная переменная стала положительной, надо одну из текущих базисных переменных сделать нулевой, т.е. перевести в небазисные. Это необходимо, чтобы новое решение содержало в точности m базисных переменных. В соответствии с терминологией симплекс-метода выбранная нулевая переменная называется вводимой (в базис), а удаляемая базисная переменная — исключаемой (из базиса). Два правила выбора вводимых и исключающих переменных в симплекс-методе назовем условием оптимальности и условием допустимости. Сформулируем эти правила, а также рассмотрим последовательность действий, выполняемых при реализации симплекс-метода. Условие оптимальности. Вводимой переменной в задаче максимизации (минимизации) является небазисная переменная, имеющая наибольший отрицательный (положительный) коэффициент в F-строке. Если в F-строке есть несколько таких коэффициентов, то выбор вводимой переменной делается произвольно. Оптимальное решение достигнуто тогда, когда в F-строке все коэффициенты при небазисных переменных будут неотрицательными (неположительными). Условие допустимости. Как в задаче максимизации, так и в задаче минимизации в качестве исключаемой выбирается базисная переменная, для которой отношение значения правой части ограничения к положительному коэффициенту ведущего столбца минимально. Если базисных переменных с таким свойством несколько, то выбор исключаемой переменной выполняется произвольно. Последовательность действий, выполняемых в симплекс-методе. Шаг 1. Находится начальное допустимое базисное решение. Шаг 2. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, вычисления заканчиваются. Шаг 3. На основе условия допустимости выбирается исключаемая переменная. Шаг 4. Методом Гаусса-Жордана вычисляется новое базисное решение. Переход к шагу 2. Вычисления в симплекс-методе выполняются итерационно в том смысле, что условия оптимальности и допустимости, а также вычисления применяются к текущей симплекс-таблице, в результате чего получается следующая таблица. Мы будем называть последовательные симплекс-таблицы итерациями. (Симплекс-метод с ограничениями «≥» рассмотрен в приложении 1). Пример 7. Предприятие выпускает два вида краски (х1 и х2) для полиграфических изданий из двух материалов (М1 и М2). Для выпуска краски х1 нормы расхода материалов составляют 1 ед. для М1 и 3 ед. для М2, для краски х2, соответственно: М1 – 2 ед., М2 – 1 ед. Запасы сырья составляют: М1 – 18 ед. и М2 – 16 ед. Краску х1 использует одна группа полиграфических изданий в пределах не более 5 ед., а краску х2 – три издания в пределах не более 21 ед.. Отпускная цена краски составляет: х1 – 2 у.е., х2 – 3 у.е. Определить оптимальный план производства для достижения максимальной прибыли при условии использования сырья в пределах запасов. Решить задачу с помощью симплексных таблиц: Математическая модель задачи следующая:  При ограничениях:  Таким образом, для получения начального опорного решения, во-первых, приведем задачу к каноническому виду путем введения в левую часть ограничений дополнительных переменных. при этом все переменные распадаются на две группы: m дополнительных и (n – m) – основных. во-вторых, основные переменные приравняем нулю, тогда m дополнительных переменных (являющихся базисными) примут значения, равные правым частям ограничений. Расширенная система имеет вид:  Здесь х3, х4, х5, х6 — дополнительные (остаточные) переменные, добавленные в неравенства для преобразования их в равенства (если неравенство типа «≥», то дополнительная переменная добавляется со знаком «-». При х1 и х2 равными 0, получаем: х3=18, х4=16, х5=5, х6=21. Заполним первую симплексную таблицу 2.1: Таблица 2.1 – Опорный план
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||