Реферат: План чтения лекции по учебной дисциплине «Математические методы»
Начнём с того, что приведём условия (6.3.) к стандартной форме, так, чтобы знак неравенства был ³, а справа стоял нуль. Получим:
(6.5.)
А теперь обозначим левые части неравенств (6.5.) соответственно через y 1 и y 2 :
(6.6.)
Из условий (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.2.)
Для простоты предположим, что все условия (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 2 +b 4 , (7.3.)
……………………