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

 

Рис. 1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 3  изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений, а на рис. 4  - случай, когда система ограничений задачи несовместна.

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

     

     можно представить в виде системы двух неравенств:

       

Целевая функция при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

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

Вектор  с координатами из коэффициентов целевой функции (ЦФ) при и перпендикулярен к каждой из линий уровня (рис.2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .

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

При поиске оптимального решения задач линейного  программирования возможны следующие  ситуации:

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

Рис. 5. Геометрическая интерпретация ограничений и ЦФ задачи.

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

 

1. В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.
2. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки и проверить истинность полученного неравенства. Если  неравенство истинное, то    надо заштриховать полуплоскость, содержащую данную точку. Если ложное – надо заштриховать полуплоскость, не содержащую данную точку. Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте. Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.
3. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
4. Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня    (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
5. Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.
6. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
7. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

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

Постановка  задачи 

Авиакомпания  осуществляет перевозку пассажиров по трем маршрутам: Крым, Турция, Египет. Для этого можно использовать 3 типа самолетов: ТУ-154 вместимостью 150 человек, ТУ-134 вместимостью 200 человек и ИЛ-86 вместимостью 500 человек. Потребность перевозки составляет: Крым – 5600 чел., Турция – 7000 чел., Египет – 6500 чел. Стоимость перевозки по указанным маршрутам на  ТУ-154 50 ед., 45 ед., 70 ед.; на ТУ-134 60 ед., 53 ед., 65 ед.;  на ИЛ-86 40 ед., 60 ед., 50 ед. Авиакомпания имеет в своем парке 35 самолетов ТУ-154, 38 самолетов ТУ-134 и 25 самолетов ИЛ-86.

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

                                                                                   

Решение задачи 

Решение данной задачи производится на ЭВМ с помощью  Microsoft Excel 11 одним из самых распространенных методов решения задачи линейного программирования симплекс-методом.

Для решения  поставленной задачи необходимо ввести обозначения:

x1 – количество самолетов ТУ-154 на рейс Крым;

x2 - количество самолетов ТУ-154 на рейс Турция;

x3 - количество самолетов ТУ-154 на рейс Египет;

x4 - количество самолетов ТУ-134 на рейс Крым;

x5 - количество самолетов ТУ-134 на рейс Турция;

x6 - количество самолетов ТУ-134 на рейс Египет;

x7 - количество самолетов ИЛ-86 на рейс Крым;

x8 - количество самолетов ИЛ-86 на рейс Турция;

x9 - количество самолетов ИЛ-86 на рейс Египет; 

Целевая функция  будет иметь вид:

F(x) = 150 (50x1 + 45x2 + 70x3) +

     + 200 (60x4 + 53x5 + 65x6) +

     + 500 (40x7 + 60x8 + 50x9)  →  min 

Ограничения:

x1 + x2 + x3 ≤ 35

x4 + x5 + x6 ≤ 38

x7 + x8 + x9 ≤ 25

150x1 + 200x4 + 500x7 = 5600

150x2 + 200x5 + 500x8 = 7000

150x3 + 200x6 + 500x9 = 6500

xi ≥ 0, i =  1; 9. 

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

 

В Microsoft Excel задача будет иметь вид: 

 
 

 

Воспользовавшись  функцией «Поиск решения» водим ограничения: 

 

В результате выяснилось, что для минимизации затрат на перевозку необходимо использовать на маршруте Крым: 3 самолета ТУ-134, 10 самолетов ИЛ-86; на маршруте Турция: 32 самолета ТУ-154, 11 самолетов ТУ-134; на маршруте Египет:  13 самолетов ИЛ-86. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Заключение 

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

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

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

Список  использованной литературы: 

1. Гельман В.Я. Решение математических задач средствами Excel:  Практикум. – СПб., Питер, 2003.
2. Моисеев, Н.Н., Иванов, Ю.П., Столяров, Е.М. Методы оптимизации.