Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
![]()
|
Теорема 4.7 (правило Блэнда для устранения зацикливания). Пусть при вы- полнении условий перехода к новой вершине выбирается «первое подходящее l, а затем первое подходящее r», то есть { } min : 0 , j l j J = ∉ ∆ < min : 0, , k kl l kl r k J β = ∈ α > θ = α где : 0 min il i l i a il ∀ > β θ = α Тогда зацикливание симплекс-метода невозможно. Иначе, а л г о р и т м Б л э н д а можно описать следующим образом: 1) выбираем небазисный столбец l с наименьшим индексом (т. е. самый левый) с отрицательной оценкой замещения; 2) среди всех строк выбираем ту, для которой достигается минимум отно- шения (преобразованной) правой части и коэффициента вводимого столбца в таблице при условии, что этот коэффициент больше нуля. Если такой мини- мум достигается на нескольких строках, выбираем строку, соответствующую вектору (переменной) с наименьшим индексом. Замечание. В задаче на минимум условия ∆ j < 0 ( 0) j c < следует заменить на ∆ j > 0 ( 0). j c > Пример 4.8 (вырожденное оптимальное решение). Решить методом искус- ственного базиса задачу линейного программирования: 1 2 ( ) 4 max, Z X x x = + → 1 2 1 2 1 2 1 2 2 12, 9, 2 18, 2; x x x x x x x x + ≤ + ≤ − ≤ + ≥ 1 2 0, 0. x x ≥ ≥ 126 Решение. Введем дополнительные (Д) и искусственные (И) неизвестные: Д И 1 2 3 1 2 4 1 2 5 1 2 6 7 2 12, 9, 2 18, 2; x x x x x x x x x x x x x + ≤ + + ≤ + − ≤ + + ≥ − + 0, 1, 7. j x j ≥ = Составим расширенную задачу. Так как рассматриваемая задача на макси- мум, то x 7 вводится в целевую функцию с коэффициентом −M. Имеем: 1 2 7 ( ) 4 max, Z X x x Mx = + − → 1 2 3 1 2 4 1 2 5 1 2 6 7 2 12, 9, 2 18, 2; x x x x x x x x x x x x x + + = + + = − + = + − + = ( ) 0 1,7 . j x j ≥ = Строим симплекс-таблицу (табл. 4.36). Таблица 4.36 БП 0 x x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i М-строка 0 0 0 0 0 0 0 M 0 0 Z x = 1 –4 –1 0 0 0 0 0 0 x 3 0 1 2 1 0 0 0 0 12 x 4 0 1 1 0 1 0 0 0 9 x 5 0 2 –1 0 0 1 0 0 18 0 1 1 0 0 0 –1 1 2 Прибавим к элементам М-строки элементы четвертой строки ограничений, умноженные на (−M) (табл. 4.37). Первое допустимое решение X 1 = (0, 0, 12, 9, 18, 0, 2) с базисом (A 3 , A 4 , A 5 , А 7 ) и значением целевой функции Z(X 1 ) = −2M не является оптимальным, так как в М-строке имеются отрицательные оценки, равные (−M) и соответствующие неизвестным x 1 и x 2 . По правилу Блэнда выбираем в качестве разрешающего столбец x 1 (альтернатива — x 2 ). Находим θ 01 = min{12, 9, 9, 2} = 2. Разрешающий 127 элемент 1 выделяем рамкой (табл. 4.37). Так как вектор А 7 выводится из базиса, то далее его исключаем (вычеркиваем) из рассмотрения. Таблица 4.37 БП 0 x x 1 ↓ x 2 x 3 x 4 x 5 x 6 x 7 b i θ 1 М-строка 0 –M –M 0 0 0 М 0 –2M 0 Z x = 1 –4 –1 0 0 0 0 0 0 x 3 0 1 2 1 0 0 0 0 12 12 x 4 0 1 1 0 1 0 0 0 9 9 x 5 0 2 –1 0 0 1 0 0 18 9 ← x 7 0 1 1 0 0 0 –1 1 2 2 Таблица 4.38 БП 0 x x 1 x 2 x 3 x 4 x 5 x 6 ↓ b i θ 6 М-строка 0 0 0 0 0 0 0 0 0 Z x = 1 0 –3 0 0 0 –4 8 x 3 0 0 1 1 0 0 1 10 10 ← x 4 0 0 0 0 1 0 1 7 7 x 5 0 0 –3 0 0 1 2 14 7 x 1 0 1 1 0 0 0 –1 2 — Вычеркиваем М-строку (так как состоит из нулей) (табл. 4.38). Новое базис- ное решение X 2 = (2, 0, 10, 7, 14, 0, 0) не является оптимальным. Разрешающий столбец выбираем при неизвестном x 6 (наименьшая отрицательная оценка). Находим θ 06 = min{10, 7, 7} = 7. Строку выбираем по правилу Блэнда: наимень- ший номер строки с θ 06 = 7 второй (альтернатива — третий). Выделяем рамкой разрешающий элемент. С помощью симплексных преобразований получаем табл. 4.39. Таблица 4.39 БП 0 x x 1 x 2 x 3 x 4 x 5 x 6 b i 0 Z x = 1 0 0 0 4 0 0 36 x 3 0 0 1 1 –1 0 0 3 x 6 0 0 0 0 1 0 1 7 x 5 0 0 –3 0 –2 1 0 0 x 1 0 1 1 0 1 0 0 9 Оценочная строка содержит неотрицательные числа. Допустимое базис- ное решение X 3 = (9, 0, 3, 0, 0, 7, 0) является оптимальным. Значение Z(X 3 ) = 36. Базисная переменная x 5 = 0, поэтому полученное оптимальное решение вырож- 128 денное. Итак, X * = X max = (9, 0, 3, 0, 0, 7), Z max = 36. На рис. 4.4 X * соответствует точка B. Эта точка является точкой пересечения трех прямых. Поскольку эта точка на плоскости, то для ее задания достаточно двух прямых, и, следователь- но, одно из ограничений «избыточно». На практике определить при большом числе неизвестных «избыточное» ограничение трудно. Замечание. При рассмотрении предыдущего примера вырожденное ре- шение появилось на последнем шаге. Однако в процессе симплекс-процедуры обнаруженная вырожденность на каком-то шаге может исчезнуть. Так, изме- ним коэффициенты целевой функции в примере 4.7, а ограничения оставим прежними: 1 2 ( ) 2 3 max, Z X x x = + → 1 2 1 2 1 2 1 2 2 12, 9, 2 18, 2; x x x x x x x x + ≤ + ≤ − ≤ + ≥ 1 2 0, 0. x x ≥ ≥ Из рис. 4.5 видно, что вырожденное решение соответствует точке B, а оп- тимальное невырожденное — точке C. Рис. 4.4. Случай вырожденного оптимального решения 9 6 12 9 2 B O x 2 x 1 Избыточное ограничение ν A 129 Упражнение. Показать путем выполнения симплекс-метода, что сфор- мулированная задача линейного программирования имеет промежуточное вырожденное решение, а оптимальное — невырожденное. Задачи для самостоятельного решения Решить симплекс-методом следующие задачи линейного программирования с приведением геометрической интерпретации решения задач: 4.1. 1 2 ( ) 5 max, Z X x x = + → 4.2. 1 2 ( ) 4 2 max, Z X x x = + → 1 2 1 2 1 2 1, 2 5, 2; 0, 1, 2. j x x x x x x x j − ≤ + ≤ − ≤ ≥ = 1 2 1 2 1 2 2 8, 2 4, 5; 0, 1, 2. j x x x x x x x j + ≤ − ≤ − + ≤ ≥ = 4.3. 1 2 ( ) 3 2 max, Z X x x = + → 1 2 1 2 2 1, 2 2; 0, 1, 2. j x x x x x j − + ≤ − ≤ ≥ = Рис. 4.5. Случай вырожденного промежуточного решения 9 12 x 1 9 2 B C x 2 O 2 6 Избыточное ограничение ν 130 Решить симплекс-методом следующие задачи: 4.4. 1 2 3 ( ) 2 –3 5 5 max, Z X x x x = + + → 1 2 3 1 2 3 1 2 3 4 2 3 3, 2 3 4, 2 2 6; 0, 1, 4. j x x x x x x x x x x x j − + + ≤ + − ≤ + + − ≤ ≥ = 4.5. 1 2 3 ( ) 5 –3 2 min, Z X x x x = − + → 1 2 3 1 2 3 4 3 5 8, 2 3 6; 0, 1, 3. j x x x x x x x j − + ≤ + + ≤ ≥ = 4.6. 1 2 3 ( ) 3 max, Z X x x x = + + → 1 2 3 1 2 3 1 2 3 3 2 2, 2 2 1, 4 3; 0, 1, 3. j x x x x x x x x x x j − + + ≤ − + + ≤ − + ≤ ≥ = 4.7. 1 2 3 ( ) 2 – – max(min), Z X x x x = → 1 2 3 1 2 3 1 2 3 2 6, 2 2 8, 2 3 3 5; 0, 1, 3. j x x x x x x x x x x j − + ≤ + + ≤ − + + ≤ ≥ = Решить задачи линейного программирования методом искусственного базиса: 4.8. 1 2 3 ( ) 2 3 4 max, Z X x x x = + + → 1 2 3 1 2 3 1 2 3 2 5, 4 5, 2 2 3 5; 0, 1, 3. j x x x x x x x x x x j + − = − + + ≤ − + + ≥ ≥ = 4.9. 1 2 3 ( ) 2 3 4 max, Z X x x x = + + → 1 2 3 1 2 3 1 2 3 2 5, 2 2 4, 5 2 2 8; 0, 1, 3. j x x x x x x x x x x j − + = − + + ≤ − + + ≥ ≥ = 131 4.10. 1 2 3 ( ) 2 2 min, Z X x x x = + + → 1 2 3 1 2 3 2 3 6, 2 2; 0, 1, 3. j x x x x x x x j + + ≥ + + ≥ ≥ = Решить графически и симплексным методом задачи линейного програм- мирования: 4.11. 1 2 3 4 ( ) max (min), Z X x x x x = + + + → 1 2 3 4 1 2 3 4 5 4 2 6, 4 5 2 6; 0, 1, 4. j x x x x x x x x x j + − − = + − − = ≥ = 4.12. 1 2 3 4 ( ) 3 4 7 max (min), Z X x x x x = + + + − → 1 2 3 4 1 2 3 4 2 3 7, 3 4 2 10; 0, 1, 4. j x x x x x x x x x j + + + = + + + = ≥ = 4.13. Предприятие располагает ресурсами сырья, рабочей силы и обору- дования, необходимыми для производства любого из четырех видов произ- водимых товаров. Затраты ресурсов на изготовление единицы данного вида товара, прибыль, получаемая предприятием, а также запасы ресурсов указаны в таблице. Вид ресурса Вид товара Объем ресурсов I II III IV Сырье, кг 3 5 2 4 60 Рабочая сила, ч 22 14 18 30 400 Оборудование, станко-часы 10 14 8 16 130 Прибыль на ед. товара, ден. ед. 30 24 56 48 max По этим исходным данным решить следующие задачи: а) выяснить, какой ассортимент товара надо выпускать, чтобы прибыль была максимальной; б) определить оптимальный ассортимент при дополнительном условии: то- вара I выпустить не более 7 ед., II — не менее 8 ед., а III и IV — в отношении 1 : 2; в) определить изменения в оптимальном ассортименте, найденные в случае «а», если ресурсы сырья увеличены на 50 %, а ресурсы рабочей силы и обору- дования — на 30 %; г) определить в оптимальном решении пункта «а», как повлияет на макси- мальную прибыль увеличение каждого из видов ресурсов на 1 ед. 132 4.14. Каждое из двух предприятий может производить три вида изделий. В таблице приведены данные о годовой производительности предприятий (тыс. шт.). Определить оптимальное распределение выпуска изделий по пред- приятиям (т. е. время работы каждого предприятия по производству каждого из изделий) из условия максимизации числа комплектов, в каждый из которых изделия I, II, III входят в соотношении 1 : 2 : 2. Предприятие Производительность I II III А 500 200 400 Б 250 300 150 Математическая модель задачи: ( ) 1 4 ( ) 2 500 250 max, Z X x x = + → ( ) 1 2 3 4 5 6 1 4 2 5 2 5 3 6 1, 1, 2 500 250 200 300 , 200 300 400 150 ; 0, 1, 6. j x x x x x x x x x x x x x x x j + + = + + = + = + + = + ≥ = Здесь x j , 1,3 j = — время работы предприятия А по производству j-го изде- лия; x j , 4,6 j = — время работы предприятия Б соответственно по производству каждого из изделий I, II, III. Ответы к задачам для самостоятельного решения 4.1. Z max = 11 при X * = (2, 1). 4.2. Z max = 16 при 1 2 (1 ) , X tX t X ° ° ° = + − 0 ≤ t ≤ 1, 1 2 (3; 2), (1; 6). X X ° ° = = 4.3. Z max = + ∞. 4.4. Z max = 21 при X * = (3, 0, 2, 1). 4.5. Z min = −18 при X * = (0, 6, 0). 4.6. Z max = + ∞. 4.7. Z max = 6 при 1 2 (1 ) , X X X ° ° ° = α + − α 0 ≤ α ≤ 1, 1 2 (3, 0, 0), (4, 2, 0); X X ° ° = = min 5 3 Z = − при * 1 2 (1 ) , X tX t X ∗ ∗ = + − 0 ≤ t ≤ 1, 1 5 0,0, , 3 X ∗ = 2 5 0, ,0 . 3 X ∗ = 4.8. max 110 7 Z = при 25 15 ,0, 7 7 X ∗ = 4.9. Система ограничений несовместна. 4.10. Z min = 4 при X * = (0, 0, 2). 4.11. Z max = + ∞; min 4 3 Z = при 2 2 , ,0,0 . 3 3 X = * 4.12. Z min = 0 при X° = (0, 0, 4, 3); Z max = 3 при X * = (2, 1, 0, 0). 4.13. а) x 3 = 16,25, Z max = 910; б) x 2 = 8, x 3 = 6,45, x 4 = 0,9, Z(X) = 286,4; в) x 3 = 21,25, Z(X) = 1183; г) x 3 = 16,375, Z(X) = 917. 4.14. опт 17 45 1 30 ,0, , , ,0 . 62 62 31 31 X = 134 5. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ 5.1. Понятие двойственной задачи линейного программирования Рассмотренные выше задачи линейного программирования были стати- ческими, т. е. их решения определялись из условий, которые были сформу- лированы в момент формирования модели. В действительности же условия, накладываемые на модель, могут меняться. Например, в случае с производ- ственной задачей может увеличиться запас сырья, если нашли новое место для его хранения и нового поставщика. Вследствие этого необходимо иметь инструментарий, который позволил бы оценить изменение оптимального решения при изменении параметров исходной модели. Таким инструментом является анализ чувствительности, но перед тем как переходить к нему, нам нужно ввести понятие двойственной задачи. Чтобы у читателя не возникало вопросов по поводу целесообразности рассмотрения двойственных задач, вна- чале на примере обратимся к их экономическому смыслу. Для этого вернемся к модели планирования производства. Пусть имеется некоторое предприятие, производящее продукцию n видов из m видов сырья. Обозначим через a lj количество i-го ресурса (i ∈ 1, …, m), которое тратится на производство единицы j-го продукта (j ∈1, …, n); x j — ко- личество единиц продукции P j , запланированной к производству; b i — запас сырья S i ; a ij — число единиц ресурса S i , затрачиваемого на изготовление единицы продукции P j ; c j — доход от реализации единицы продукции P j Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной. Тогда экономико-математическая модель задачи об использовании сырья в общей постановке имеет вид: ( , 1 1 2 2 ) max n n Z X c x c x c x = + + + → 135 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 , , , 0, 1, . n n n n m m mn n m j a x a x a x b a x a x a x b a x a x a x b x j n + + + ≤ + + + ≤ + + + ≤ ≥ = (5.1) Помимо величины оптимального выпуска продукции, предприятие ин- тересует рентабельность этого плана и мера дефицитности сырья. Например, если некоторая фирма посчитает нужным закупить сырье вышеуказанного предприятия, то необходимо будет установить оптимальные цены на это сы- рье. Естественно, что покупающая фирма заинтересована в том, чтобы затраты на сырье были минимальны, но при этом предприятию, продающему сырье, выгодно получить выручку с продажи не менее той, которую предприятие может получить при переработке сырья в готовую продукцию. Иными словами, требуется оценить каждый из видов сырья, используе- мых для производства продукции, таким образом, чтобы «цены» сырья были не меньше цены единицы продукции данного вида и при этом общие затраты на сырье будут минимальны. Слово «цены» не случайно взято в кавычки, так как его смысл состоит в том, что это не рыночные цены сырья, а некоторая оценка его стоимости, которую еще называют учетной, теневой ценой, объективно обусловленной оценкой. По своему смыслу они являются оценками потенциальной возможности полу- чения дополнительной прибыли за счет увеличения соответствующего ресурса в условиях оптимального функционирования управляемого экономического объекта.Мы будем придерживаться названия — теневые цены. Итак, приведем математическую постановку вышеописанной задачи. Обозначим теневые цены сырья за y 1 , y 2 , …, y m , тогда суммарная «стои- мость» (оценка затрат на всю продукцию) всего имеющегося сырья составит b 1 y 1 + b 2 y 2 + … + b m y m . Ее будем минимизировать. При этом есть условие, что доход от продажи сырья был не меньше, чем от реализации продукции, что математически можно записать так: 11 1 21 2 1 1 12 1 22 2 2 2 1 1 2 2 , , , m m m m n n mn m m a y a y a y c a y a y a y c a y a y a y c + +…+ ≥ + +…+ ≥ ≥ … + +…+ ≥ Тогда, учитывая, что теневые цены не могут быть отрицательны, получаем следующую экономико-математическую модель: 1 1 2 2 min, m m b y b y b y + +… → + 136 11 1 21 2 1 1 12 1 22 2 2 2 1 1 2 2 , , , 0, 1,. .., m m m m n n n i mn m a y a y y a y c a y a y a y c a y a y a i y m c + +…+ ≥ + +…+ ≥ … + +…+ = ≥ ≥ (5.2) Задача (5.1) называется прямой задачей линейного программирования, а (5.2) — двойственной, а вместе они образуют пару задач, которую называют двойственной парой (в некоторой литературе их еще именуют симметричными взаимно двойственными задачами). Чтобы читатель точно понял экономический смысл этих двух задач, еще раз сформулируем их основные идеи. Прямая задача: сколько и какой продукции необходимо произвести, чтобы при заданных ценах продукции и фиксированных объемах имеющегося сырья, а также известных нормах его расхода максимизировать выпуск продукции в стоимостном выражении (доход). Двойственная задача: какой должна быть оценка единицы каждого вида сырья, чтобы при заданных ценах на продукцию, запасах сырья и нормах его расхода минимизировать общую оценку затрат на всю продукцию. |