Учебная работа № 1602. План чтения лекции по учебной дисциплине «Математические методы»
Юридический техникум Рассмотрено и одобрено ПЦК
г. Кропоткин программирования
Председатель ПЦК
Покалицына О.В.
План
чтения лекции по учебной дисциплине
«Математические методы»
Раздел № 2.Линейное программирование.
Тема № 2.2. Основная задача линейного программирования.
Занятие №
Место проведения: аудитория.
Литература:
1. Венцель Е.С. Исследование операций. Задач, принципы, методология. – М.: Наука, 1980.
2. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе. – М.:ЮНИТИДАНА, 2001
Учебные вопросы и расчет времени
№п/п | Учебные вопросы | Время, мин | Методические указания |
1. 2. |
Основная задача ЛП (ОЗЛП). Существование решения. |
1. Вводная часть. Организационный момент. План занятия. Основные требования.
2. Основная часть.
1. Основная задача ЛП (ОЗЛП).
Любую задачу линейного программирования можно свести к стандартной форме, так называемой «основной задаче линейного программирования» (ОЗЛП), которая формируется так: найти неотрицательные значения переменные x 1 , x 2 , …, xn , которые удовлетворяли бы условиям – равенствам:
a 11 x 1 + a 12 x 2 + … +a 1n xn = b 1 ,
a 21 x 1 + a 22 x 2 + … +a 2n xn = b 2 , (6.1.)
………………………………..
am 1 x 1 +am 2 x 2 + … +amn xn = bm .
и обращали бы в максимум линейную функцию этих переменных:
(6.2.)
Случай, когда L надо обратить не в максимум, а в минимум, легко сводится к простому: изменить знак L на обратный (максимизировать не L, а L`=L). Кроме того, от любых условий – неравенств можно перейти к условиям – равенствам ценой введения некоторых новых «дополнительных» переменных. Пусть требуется найти неотрицательные значения переменных x 1 ,x 2 ,x 3 , удовлетворяющие ограничениям – неравенствам
и обращающие в максимум линейную функцию от этих переменных:
Начнём с того, что приведём условия (6.3.) к стандартной форме, так, чтобы знак неравенства был ³, а справа стоял нуль. Получим:
А теперь обозначим левые части неравенств (6.5.) соответственно через y 1 и y 2 :
Из условий (6.5.) и (6.6.) видно, что новые переменные y 1 , y 2 также должны быть неотрицательными.
Какая же теперь перед нами стоит задача? Найти неотрицательные значения переменных x 1 ,x 2 ,x 3 ,y 1 ,y 2 такие, чтобы они удовлетворяли условиям – равенствам (6.6.) и обращали в максимум линейную функцию этих переменных (то, что в L не входит дополнительные переменные y 1 , y 2 , неважно: можно считать, что они входят, но с нулевыми коэффициентами). Перед нами – основная задача линейного программирования (ОЗЛП). Переход к ней от первоначальной задачи с ограничениями – неравенствами (6.3.) «куплен» ценой увеличения числа переменных на два (число неравенств).
2. Существование решения ОЗЛП и способы его нахождения.
Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x 1 , x 2 , …, x n , удовлетворяющие m условиям – равенствам:
a 11 x 1 +a 12 x 2 +…+a 1n xn =b 1 ,
a 21 x 1 +a 22 x 2 +…+a 2n xn =b 2 , (7.1.)
……………………………
am 1 x 1 +am 2 x 2 +…+amn xn =bm
и обращающие в максимум линейную функцию этих переменных:
Для простоты предположим, что все условия (7.1.) линейно независимы (r =m ), и будем вести рассуждения в этом предположении.
Назовём ДОПУСТИМЫМ решением ОЗЛП всякую совокупность неотрицательных значений x 1 , x 2 , …, xn , удовлетворяющую условиям (7.1.).
ОПТИМАЛЬНЫМ назовём то из допустимых решений, которое обращает в максимум функцию (7.2.).
Требуется найти оптимальное решение. Всегда ли эта задача имеет решение? Нет, не всегда.
1. Может оказаться, что уравнения (7.1.) вообще несовместимы (противоречат друг другу).
2. Может оказаться и так, что они совместимы, но не в области неотрицательных решений, т.е. не существует ни одной совокупности чисел x 1 ³0, x 2 ³0, …, xn ³0, удовлетворяющей условиям (7.1.).
3. Наконец, может быть и так, что допустимые решения ОЗЛП существуют, но среди них нет оптимального: функция L в области допустимых решений не ограничена сверху.
Чтобы представить себе принципиальную сторону ОЗЛП, обратимся к геометрической интерпретации. Пусть число уравнений m на два меньше числа переменных n (n m =k =2). Такой частный случай даёт возможность геометрической интерпретации ОЗЛП на плоскости.
Мы знаем, что n линейно независимых уравнений (7.1.) всегда можно разрешить относительно какихто m базисных переменных, выразив их через остальные, свободные, число которых равно n m =k (в нашем случае k =2). Предположим, что свободные переменные – это x 1 и x 2 (если это не так, то всегда можно заново перенумеровать переменные), а остальные: x 3 , x 4 , …, xn – базисные. Тогда вместо m уравнений (7.1.) мы получим тоже m уравнений, но записанных в другой форме, разрешённых относительно x 3 , x 4 , …;
x 3 =a 31 x 1 +a 32 x 2 +b 3 ,
x 4 =a 41 x 1 +a 42 x