Линейное программирование Анализ многих проблем управления, в основном, экономическими объектами, приводит к целенаправленной постановке и решению следующей. - презентация

1 Линейное программирование Анализ многих проблем управления, в основном, экономическими объектами, приводит к целенаправленной постановке и решению следующей экстремальной задачи: Z(x1,x2,...,xn) extr, (1) i(x1,x2,...,xn)=0; i=1,2,...,m,(2) (x1,x2,...,xn) G.(3) Здесь: (x1,x2,...,xn)- вектор переменных - параметров управления; G - множество, элементы которого обладают определенными свойствами; Z(x1,x2,...,xn)- количественный показатель качества решения - т. н. целевая функция. Область допустимых решений задается системой ограничений (2) и множеством G (3). В задаче требуется из всех допустимых решений, то есть, решений, удовлетворяющих ограничениям (2) и (3), найти такое, которое обеспечивает экстремальное значение целевой функции - максимальное или минимальное, в зависимости от содержательной постановки задачи. Задача, сформулированная в виде (1)-(3), является задачей математического программирования - раздела прикладной математики, в котором разрабатываются методы поиска условного экстремума функции многих переменных.

2 Линейное программирование Важнейшей особенностью задачи, сформулированной в общем виде (1)-(3), является отсутствие общего, универсального метода ее решения, за исключением, разве что, полного перебора всех допустимых решений. Так, если Z и i ( i=1,2,...,m) - линейные функции параметров управления, т.е., Z=c 0 + c 1 x 1 +…+x n, i =a i1 x 1 +…+a in x n, а G - положительный ортант ( xj 0, j=1,2,...,n ) или гиперпараллелепипед евклидова n-мерного пространства, задача (1)-(3) является задачей линейного программирования.

3 Пример задачи ЛП Пример – Оптимизация размещения побочного производства лесничества Лесничество имеет 24 га свободной земли под паром и заинтересовано извлечь из нее доход. Оно может выращивать саженцы быстрорастущего гибрида новогодней ели, которые достигают спелости за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1.5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 ч. в год на свое побочное производство. Практика показывает, что требуется 20 ч. для культивации, подрезания, вырубки и пакетирования одной партии деревьев. Для ухода за одним бычком также требуется 20 ч. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб. и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам, одна новогодняя ель принесет прибыль в 2,5 руб., один бычок - 5 тыс. руб.

4 Постановка задачи 1. В качестве показателя эффективности целесообразно взять прибыль за операцию (годовую прибыль с земли в рублях). 2. В качестве управляемых переменных задачи следует взять: x 1 - количество откармливаемых бычков в год; x 2 - количество выращиваемых партий быстрорастущих новогодних елей по 1000 шт. каждая в год. 3. Целевая функция: 5000 x x2 max, где чистый доход от одного бычка, руб.; чистый доход от одной партии деревьев (1000 шт. по 2,5 руб.). 4. Ограничения: 4.1. По использованию земли, га:4 x 1 + 1,5 x По бюджету, руб.:1200 x x По трудовым ресурсам, ч:20 x x Обязательства по контракту, шт.:x Областные ограничения:x 1 0, x 2 0

5 Графическое решение задачи ЛП Отображая на графике прямые, соответствующие следующим уравнениям, 4 x 1 + 1,5 x 2 = x x 2 = x x 2 = 200 x 1 = 2 x 2 = 0 заштриховываем область, в точках которой выполняются все ограничения. Каждая такая точка называется допустимым решением, а множество всех допустимых решений называется допустимой областью. Очевидно, что решение задачи ЛП состоит в отыскании наилучшего решения в допустимой области, которое, в свою очередь, называется оптимальным. В рассматриваемом примере оптимальное решение представляет собой допустимое решение, максимизирующее функцию W=5000 x x 2. Значение целевой функции, соответствующее оптимальному решению, называется оптимальным значением задачи ЛП.

6 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Графическое решение задачи ЛП

7 Перебор всех угловых точек области допустимых решений приводит к нахождению максимального дохода в размере 34 тыс. руб. (Z=5000x x 2 ), которое лесничество может извлечь, выращивая 3,6 бычка и 6,4 партии новогодних елей. Целочисленные методы (например, перебор) дают x 1 =3 и x 2 =6, что приводит к доходу в 30 тыс. руб., x 1 =4 и x 2 =5 приводит к более оптимистичному результату в 32,5 тыс. руб., точка x 1 =3 и x 2 =7 приводит к аналогичному результату.

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

9 Задача ЛП в стандартной форме Задача ЛП в стандартной форме с m ограничениями и n переменными имеет следующий вид: Z = c 1 x 1 + c 2 x c n x n min (max) при ограничениях a 11 x 1 + a 12 x a 1n x n = b 1 ; a 21 x 1 + a 22 x a 2n x n = b 2 ;... a m1 x 1 + a m2 x a mn x n = b m ; x 1 0; x 2 0;...; x n 0 b 1 0; b 2 0;...; b m 0 В матричной форме Z = cx min (max) при ограничениях Ax = b; x 0; b 0, где A - матрица размерности m*n, x - вектор-столбец переменных размерности n*1, b - вектор-столбец ресурсов размерности m*1, с - вектор-строка оценок задачи ЛП 1*n.

10 Преобразование неравенств Ограничения в виде неравенств можно преобразовать в равенства при помощи введения так называемых остаточных или избыточных переменных. Уравнение из предыдущего примера 4x 1 + 1,5x 2 24 можно преобразовать в равенство при помощи остаточной неотрицательной переменной 4x 1 + 1,5x 2 + x 3 = 24. Переменная x 3 неотрицательна и соответствует разности правой и левой частей неравенства. Аналогично x 1 2 можно преобразовать путем введения избыточной переменной x4: x 1 - x 4 = 2.

11 Преобр-е неогр. по знаку перем-х Преобразование неограниченных по знаку переменных Переменные, принимающие как положительные, так и отрицательные значения, следует заменять разностью двух неотрицательных: x = x + - x - ; x + 0; x - 0. Пример. 3x 1 +4x 2 +5x 3 +4x 4 max 2x 1 +x 2 +3x 3 +5x 4 5 5x 1 +3x 2 +x 3 +2x x 1 +2x 2 +3x 3 +x 4 = 15 x 1 0; x 2 0; x 3 0; x 4 = знак -3x 1 -4x 2 +5x 3 -4x 4 min 2x 1 +x 2 -3x 3 +5x 4 -x 5 = 5 5x 1 +3x 2 -x 3 +2x 4 +x 6 = 20 4x 1 +2x 2 -3x 3 +x 4 = 15 x 1 0; x 2 0; x 3 0; x 4 = знак; x 4 =x 8 -x 7 -3x 1 -4x 2 +5x 3 -4x 8 +4x 7 min 2x 1 +x 2 -3x 3 +5x 8 -5x 7 -x 5 = 5 5x 1 +3x 2 -x 3 +2x 8 -2x 7 +x 6 = 20 4x 1 +2x 2 -3x 3 +x 8 -x 7 = 15 x 1,x 2,x 3,x 5,x 6,x 7,x 8 0; -3x 1 -4x 2 +5x 3 -4x 4 +4x 7 min 2x 1 +x 2 -3x 3 +5x 4 -5x 7 -x 5 = 5 5x 1 +3x 2 -x 3 +2x 4 -2x 7 +x 6 = 20 4x 1 +2x 2 -3x 3 +x 4 -x 7 = 15 x 1,x 2,x 3,x 4,x 5,x 6,x 7 0; x 8 заменили на x 4

12 Симплекс-метод ЛП Симплекс-метод представляет собой итеративную процедуру решения задач ЛП, записанных в стандартной форме, система уравнений в которой и с помощью элементарных операций над матрицами приведена к каноническому виду: x 1 + a 1,m+1 x m a 1s x s a 1n x n = b 1 ; x 2 + a 2,m+1 x m a 2s x s a 2n x n = b 2 ;... x m + a m,m+1 x m a ms x s a mn x n = b m. Переменные x 1, x 2,...,x m, входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми - в остальные, называются базисными. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Остальные n-m переменных (x m+1,...,x n ) называются небазисными переменными. Для приведения системы к каноническому виду можно использовать два типа элементарных операций над строками: 1)Умножение любого уравнения системы на положительное или отрицательное число. 2)Прибавление к любому уравнению другого уравнения системы, умноженного на положительное или отрицательное число.

13 Симплекс-метод ЛП Запись задачи в виде уравнений Z = -> max x 1 + a 1,m+1 x m a 1s x s a 1n x n = b 1 ; x 2 + a 2,m+1 x m a 2s x s a 2n x n = b 2 ;... x m + a m,m+1 x m a ms x s a mn x n = b m. тождественна записи в виде матриц a 1,m+1.. a 1s.. a 1n x 1 b a 2,m+1.. a 2s.. a 2n x 2 = b a m,m+1.. a ms.. a mn x n b m

14 Алгоритм симплекс-метода 1. Разложить векторы A0,A1,A2,...An по базису, то есть, найти все числа x kj (j=0,1,2,...,n; k=1,2,...,m ) такие, что: Учитывая тот факт, что базис представлен единичными векторами, то коэффициенты разложения определяются непосредственно параметрами задачи: x kj =akj, x k0 =a k (j=1,2,...,n; k=1,2,...,m ). При этом, координаты опорного решения x*=( x* 1, x* 2,..., x* n ) определяются следующим образом: x* ik =a k =x k0,(k=1,2,...,m ); x* j =0, (j=1,2,...,n; j {i1,i2,...,im}).

15 Алгоритм симплекс-метода 2. Найти оценки всех свободных векторов Aj, j {i1,i2,...,im}: j =с j1 x 1j +c j2 x 2j +…+c jm x mj Z 0 = с j1 x 1j +c j2 x 2j +…+c jm x mj Результаты вычислений занести в симплекс-таблицу. Полная симплекс-таблица представлена на рисунке.

16 Алгоритм симплекс-метода 3. Если все оценки j 0 (j=1,2,...,n), процесс закончен. Очередное опорное решение - оптимальное решение задачи. Координаты этого решения x*=( x* 1, x* 2,..., x* n ) однозначно определяются коэффициентами разложения вектора A0 : x* ik =a k =x k0,(k=1,2,...,m ); x* j =0, (j=1,2,...,n; j {i1,i2,...,im}).

17 Алгоритм симплекс-метода 4. Последовательно просматриваются все свободные векторы, имеющие отрицательные оценки. Если обнаруживается такой вектор Aj ( j < 0 ), для которого все x kj 0, (j=1,2,...,n), вычисления прекращаются: задача не имеет решения, так как ее целевая функция не ограничена сверху на допустимом множестве. В противном случае выполняется следующий шаг.

18 Алгоритм симплекс-метода 5. Выбирается любой вектор, имеющий отрицательную оценку (обычно предпочтение отдается вектору с максимальной по абсолютной величине отрицательной оценкой - это, как правило, сокращает общее количество вычислительных операций). Пусть, для определенности, выбран вектор As ( s < 0 ). Этот вектор будет вводиться в базис.

19 Алгоритм симплекс-метода 6. Определяется вектор, который будет выводиться из базиса. Для этого просматриваются все элементы s-го столбца симплекс-таблицы и для всех k (k=1,2,...,m ), для которых имеет место x ks >0, вычисляется отношение x ks / x rs. Из полученных отношений выбирается минимальное. Пусть для всех x ks >0, (k=1,2,...,m ; k r). Тогда из базиса будет выводиться вектор. Выполняется следующий шаг.

20 Алгоритм симплекс-метода 7. Для нового базиса пересчитываются координаты разложения всех векторов Aj (j=0,1,2,...,n): x kj = x kj – (x rj /x rs )x ks, kr, k=1,…,m. x rj =x rj /x rs. Далее, вычисляется значение целевой функции на новом опорном решении: Zнов= Zст - (x r0 /x rs ) s. В этом выражении Zнов и Zст - соответственно, новое и старое значения целевой функции. Наконец, вычисляются оценки свободных векторов в новом базисе. Здесь используется выражение: j = j - (x rj /x rs ) s При ручном счете для вычислений по формулам используется правило крест-накрест. Результаты вычислений заносятся в новую симплекс-таблицу и выполняется шаг 3.

21 Алгоритм симплекс-метода

22 Анализ чувствительности Анализ чувствительности позволяет оценить влияние этих параметров на оптимальное решение. Если обнаруживается, что оптимальное решение можно значительно улучшить за счет небольших изменений заданных параметров, то целесообразно реализовать эти изменения. Кроме того, во многих случаях оценки параметров получаются путем статистической обработки ретроспективных данных (например, ожидаемый сбыт, прогнозы цен и затрат). Оценки, как правило, не могут быть точными. Если удается определить, какие параметры в наибольшей степени влияют на значение целевой функции, то целесообразно увеличить точность оценок именно этих параметров, что позволяет повысить надежность рассматриваемой модели и получаемого решения. Решение практической задачи нельзя считать законченным, если найдено оптимальное решение. Дело в том, что некоторые параметры задачи ЛП (финансы, запасы сырья, производственные мощности) можно регулировать, что, в свою очередь, может изменить найденное оптимальное решение. Эта информация получается в результате выполнения анализа чувствительности.

23 Анализ чувствительности по лимитирующим ресурсам

24

25 Анализ чувствительности по нелимитирущим ресурсам

26 Анализ чувствительности по ресурсам

27 Анализ чувствительности по коэффициентам ЦФ Изменение коэффициентов целевой функции оказывает влия­ние на наклон прямой, которая представляет эту функцию в принятой системе координат. Вариация коэффициентов целевой функ­ции может привести к изменению совокупности связывающих ограничений и, следовательно, статуса того или иного ресурса (т.е. сделать недефицитный ресурс дефицитным, и наоборот). При анализе модели ни чувствительность к изменениям коэффи­ циентов целевой функции необходимо исследовать следующие вопросы: 1. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходят изменения опти­ мального решения? 2. На сколько следует изменить тот или иной коэффициент це­ левой функции, чтобы сделать некоторый недефицитный ресурс дефицитным, и, наоборот, дефицитный ресурс сделать недефицит­ ным?

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

29 Двойственная модель ЛП Шаг 1. Изменение направления экстремизации и неравенств в задаче. Шаг 2. Создание новой системы ограничений. Шаг 3. Наложение на переменные требования неотрицательности. В некотором смысле, двойственная задача формируется в результате "транспонирования" прямой задачи.

30 Двойственная модель ЛП Шаг 1. Изменение направления экстремизации и неравенств в

31 Двойственная модель ЛП