Линейное программирование

Линейное программирование 1.1 Примеры задач линейного программирования 1.1.1 Задача планирования выпуска продукции (планирование производства) Машиностроительное предприятие для изготовления четырех видов продукции использует токарное, фрезерное, сверлильное, расточное и шлифовальное оборудование, а также комплектующие изделия. Кроме того, сборка изделий требует выполнения сборочно-наладочных работ. Нормы затрат всех видов ресурсов на изготовление каждого из изделий приведены в таблице (см. табл. 1.1). В этой же таблице указан имеющийся фонд каждого из ресурсов и прибыль от реализации одного изделия каждого вида. Таблица 1.1−Нормы затрат на изготовление одного изделия Общий Нормы затрат на объем Ресурсы изготовление одного ресуризделия сов 1 Производительность оборудования (чел.-час) Токарного 2 3 4 5 6 550 - 620 - 64270 Фрезерного 40 30 20 20 4800 Сверлильного 86 110 150 52 22360 Расточного 160 92 158 128 26240 Шлифовального - 158 30 50 7900 Комплект изделия (шт.) 3 4 3 3 520 4,5 4,5 4,5 4,5 720 Сборочно-наладочные работы (чел.-час.) Продолжение таблицы 1.1 Нормы затрат на изготовление одного изделия Ресурсы 1 Прибыль от реализации одного изделия (руб.) 2 3 315 278 4 573 5 370 Общий объем ресурсов 6 Надо составить такой план выпуска продукции, чтобы получить максимальную прибыль. Построим математическую модель данной задачи. Пусть x 1 – планируемое количество изделий 1-го типа, x 2 , x 3 , x 4 – планируемое количество изделий 2-го, 3-го, 4-го типов соответственно. Тогда f=315x 1 +278x 2 +573x 3 +370x 4 (1.1) прибыль предприятия. Так как нам надо получить как можно большую прибыль, то будем искать наибольшее (максимальное) значение функции f. Общие объемы ресурсов накладывают на нашу задачу ограничения 550x 1 + 620x 2 ≤ 64270 40x 1 + 30x 2 + 20x 3 + 20x 4 ≤ 4800 86x 1 + 110x 2 +150x 3 + 52x 4 ≤ 22360 160x 1 + 92x 2 + 158x 3 + 128x 4 ≤ 26240 (1.2) 158x 2 + 30x 3 + 50x 4 ≤ 7900 3x 1 + 4x 2 + 3x 3 + 3x 4 ≤ 520 4.5x 1 + 4.5x 2 + 4.5x 3 + 4.5x 4 ≤ 720. Так как целевая функция и ограничения являются линейными, то это задача линейного программирования. 2 1.1.2 Задача планирования капитальных вложений Для электроснабжения трех стройплощадок используются две трансформаторные подстанции. Первая стройплощадка потребляет 130 кВт, а вторая и третья по 140 кВт. Мощность первой ТП – 250 кВт, а второй 160 кВт. Расстояние от первой ТП – 600, 400, 200 м, до первой, второй и третьей площадки соответственно. От второй ТП: − 500, 300 и 200 м соответственно. Требуется составить схему электроснабжения с минимальными капитальными вложениями. Капитальные вложения для устройства линий рассчитываются по следующей формуле: 3 2 ∑ ∑ j =1 i =1 Sij K0 3U j 3 2 lij = α ∑ ∑ Sij lij , j =1 i =1 (1.3) где: S ij – мощность, потребляемая j-ой площадкой от i-ой ТП, кВт; l ij – расстояние от j-ой площадки до i-ой ТП, м.; α – постоянный множитель. Итак, нам надо минимизировать функцию f=α(6S 11 +4S 12 +2S 1 3 +5S 21 +3S 2 2 +2S 2 3 ), при ограничениях: S 11 + S 21 =130; (1.4) S 12 + S 22 =140; S 13 + S 23 =140; (1.5) S 11 + S 12 + S 13 =250; S 21 + S 22 + S 23 =160 . Как и в предыдущем примере имеем задачу линейного программирования. 1.2 Основные определения ОПРЕДЕЛЕНИЕ 1.1. Задача, состоящая в нахождении наибольшего (наименьшего) значения функции (1.6) f(x)=с 1 x 1 +c 2 x 2 + … + c n х n 3 на множестве точек x T =(x 1 ,…,x n ), удовлетворяющих системе ограничений вида: a 11 x 1 + a 12 x 2 +…+ a 1n x n < R 1 > b 1 a 21 x 1 + a 22 x 2 +…+ a 2n x n < R 2 > b 2 . . . . . . . . . . a m1 x 1 + a m2 x 2 +…+ a mn x n < R m > b m (1.7) называется задачей линейного программирования общего вида. Здесь: f( x )=с 1 x 1 + c 2 x 2 + … + c n x n – целевая функция; R i, i = 1, m – операции отношения =, ≥,≤; c i , i = 1, n ; a ij , i = 1, m, j = 1, n ; b i , i = 1, m – заданные константы. T ОПРЕДЕЛЕНИЕ 1.2. Всякую точку x =(x 1 ,…,x n ), компоненты которой удовлетворяют всем ограничениям системы (1.7), будем называть допустимой точкой или допустимым решением задачи, или допустимым планом задачи. Задача линейного программирования состоит, таким образом, в нахождении такой допустимой точки x (0) (такого допустимого плана) среди множества допустимых точек, при которой целевая функция принимает max (min) значение. Допустимое решение x (0) = (x 1 (0) ,…,x n (0 ) ) T , доставляющее целевой функции оптимальное значение (оптимум), будет называться оптимальным решением или оптимальным планом задачи. В дальнейшем будем говорить, к примеру, только о нахождении max целевой функции. Задачу линейного программирования, представленную в виде: 4 f = с 1 x 1 + c 2 x 2 + … + c n x n → max (min) a 11 x 1 + … + a 1n x n = b 1 a 21 x 1 + … + a 2n x n = b 2 . . . . . . . a m1 x 1 + … + a mn x n = b m x i ≥ 0, i = 1, n ; (1.8) будем считать канонической задачей линейного программирования. Введением дополнительных переменных, мы можем любое ограничение вида неравенства свести к ограничениям – равенствам. Если не на все переменные наложено требование неотрицательности (слабые ограничения), то такие переменные можно заменить разностью двух новых переменных, каждая из которых неотрицательна. Проиллюстрируем сказанное на примере. Пример 1.1. Привести к каноническому виду задачу: f = x 1 –2x 1 +x 3 → max x 1 + 2x 2 + 3x 3 ≤ 5 2x 1 +3x 2 – 4x 3 = 3 –x 1 + x 2 – x 3 ≥ 2 x 1 ≥ 0, x 2 ≥ 0. (1.9) Введем две дополнительные неотрицательные переменные x 4 и x 5 в первом и третьем ограничениях, так, чтобы получить ограничения – равенства. Кроме того, переменную x 3 представим в виде: x3 = x3‫ – ׳‬x3‫״‬, (1.10) где: x 3 ‫ ≥ ׳‬0, x 3 ‫ ≥ ״‬0. Получим: f = x 1 – 2x 1 + x 3 ‫ – ׳‬x 3 ‫ → ״‬max, x 1 + 2x 2 + 3(x 3 ‫ – ׳‬x 3 ‫ ) ״‬+ x 4 = 5 2x 1 + 3x 2 – 4(x 3 ‫ – ׳‬x 3 ‫ = ) ״‬3 (1.11) – x 1 – x 2 – (x 3 ‫ – ׳‬x 3 ‫ – ) ״‬x 5 = 2 x 1 ≥ 0, x 2 ≥ 0, x 3 ‫≥ ׳‬0, x 3 ‫≥ ״‬0, x 4 0, x 5 ≥ 0, а это уже задача в канонической форме. 5 Введя в рассмотрение векторы T T c =(c1, c2, … cn), x = (x1, … , xn) , b = (b1,…, bm) , A= a11 … a1n a21 … a2n ....... am1 … amn можем переписать задачу (1.6),(1.7) линейного программирования в форме: f = c · x → max(min)  Ax = b  x ≥ 0. (1.12) (1.13) 1.3 Геометрическая интерпретация двумерной задачи линейного программирования и ее решение Рассмотрим двумерную задачу: f = c 1 x 1 + c 2 x 2 → max(min), (1.14) a 1 1 x 1 + a 12 x 2 < R 1 > b 1 a 2 1 x 1 + a 22 x 2 < R 2 > b 2 . . . . . (1.15) a m1 x 1 + a m2 x 2 < R m > b m . Каждое из ограничений a i1 x 1 +a i2 x 2 < R i > b i определяет в плоскости, с системой координат x 1 o x 2 множество точек, лежащих по одну сторону от прямой a i1 x 1 +a i2 x 2 =b i (т.е. полуплоскость). Множество всех точек плоскости, координаты которых удовлетворяют всем ограничениям, т.е. принадлежат сразу всем полуплоскостям, определяемым отдельными ограничениями, будет представлять собой допустимое множество. Очевидно, что, если множество не пусто, то это будет некоторый многоугольник (возможно и неограниченный, возможно вырождающийся в отрезок, точку). Многоугольник будет выпуклым, что легко показать, т.е. любые две его точки можно соеди6 нить отрезком, точки которого принадлежат допустимому множеству. ОПРЕДЕЛЕНИЕ 1.3. Множество D-точек n-мерного евклидова пространства будем называть выпуклым, если для любых x (1 ) =(x 1 (1) ,…,x n (1) ) T и x (2) =(x 1 (2) ,…,x n (2) ) T из множества D и любых α ≥0, β≥0 таких, что α+β=1, точка x=αx (1 ) +βx (2) также принадлежит D. ОПРЕДЕЛЕНИЕ 1.4. Вершиной выпуклого множества в R n назовем такую точку, которую нельзя представить в виде x=αx (1) +βx (2) , α>0, β>0, α+β=1, ни при каких x (1) ,x (2 ) . Проиллюстрируем вышесказанное примерами. Примеры: изобразить множество точек, удовлетворяющих системе неравенств. 1) 2x 1 – 3x 2 ≤ 2 3x 1 – x 2 ≤ 1 − x1 + 1 x2 ≤ 1 2 x1 ≥ 0 2) –x 1 + x 2 ≤ 1 x 1 – 2x 2 ≤ 1 x1 ≥ 0 x2 ≥ 0 x2 ≥ 0 3) 3x +x ≥3 4 1 2 x1 + x2 ≤ 1 x 2 ≤1 4) 3x2 − 1 x1 ≤ 3 2 x 1 + x 2 ≥1 x 1 + x 2 ≤1 x 2 – x 1 ≥–1 Построив допустимые множества, убедимся в вышесказанном. Рассмотрим теперь геометрическую интерпретацию решения задачи линейного программирования. Пусть допустимая область задачи (1.14)−(1.15) оказалась непустой (в соответствии с рисунком 1.1). 7 x2 f =amin (x1(0) , x2(0) ) – точка максимума f=amах Точка минимума n= grad f f = c1 x1 + c2 x2 = a х1 Рисунок 1.1 - Геометрическая интерпретация задачи линейного программирования Мы хотим найти те точки допустимой области, координаты которых доставляют целевой функции наибольшее значение. Построим линию уровня целевой функции f=c 1 x 1 +c 2 x 2 =a . Получим множество точек, в точках которого f принимает одно и тоже значение a . Перемещая линию уровня в направлении вектора grad f=(c 1, c 2 )=n, нормального к линии уровня, будем получать в пересечении этой линии с допустимой областью точки, в которых целевая функция принимает новое значение, большее чем значение на предшествующих линиях уровня. Пересечение допустимой области с линией уровня в том ее положении, когда дальнейшее перемещение дает пустое множество, и будет множеством точек максимума задачи линейного программирования. Перемещая линию уровня в направлении противоположном вектору n, аналогичным образом найдем точки минимума. Пример 1.2. f = x2 – 2x1 → max –x1 + x2 ≤ 1 x1 – 2x2 ≤ 1 x1 ≥ 0, x2 ≥ 0 8 x2 f = –2x1 + x2 = 0 f =1 n (–2,1) 1 x1 –2 –1 0.5 1 Рисунок 1.2 - Геометрическая интерпретация задачи линейного программирования Точка максимума: x=(0, 1) T ; f max =f(0, 1)=1. Легко представить, что задача имеет бесчисленное множество оптимальных решений, а может их не иметь вовсе, как например: f = x1 + x2 → min(max); x1 + x2 ≥ 1 –x1 + x2 ≤ 1 x1 – 2x2 ≤ 2 x1 ≥ 0, x2 ≥ 0. Целевая функция достигает минимального значения в точках отрезка x 1 +x 2 =1, между точками (0, 1) и (1, 0), а максимального значения функция не достигает (не ограничена в допустимой области). 9 x2 K f=K n(1,1) 1 –1 1 2 x1 –1 f =1 Рисунок 1.3 − Геометрическая интерпретация задачи линейного программирования 1.3.1 Свойства задачи линейного программирования Рассмотренные примеры позволяют сформулировать основные свойства задачи линейного программирования. Свойство 1. Допустимая область задачи линейного программирования выпукла, если она не пуста. Свойство 2. Если допустимая область имеет вершины и задача линейного программирования имеет решение, то оно достигается по крайней мере в одной из вершин. Свойство 3. Множество решений задачи линейного программирования выпукло. Свойство 4. Если допустимая область ограничена, то любая задача линейного программирования имеет оптимальное решение. Свойство 5. Необходимым и достаточным условием существования решения задачи линейного программирования на максимум (минимум) является ограниченность 10 целевой функции сверху (соответственно снизу) в допустимой области. Все перечисленные свойства справедливы и в общем случае (n≥2). Свойства задачи линейного программирования наталкивают на следующую схему решения задачи линейного программирования, известную как симплeкс-метод. Именно: пусть рассматриваемая задача имеет непустое допустимое множество с вершинами. Тогда: 1) тем или иным способом находим какую-нибудь вершину допустимого множества и по определенным критериям определяем, не является ли она оптимальной. Если вершины нет, то допустимая область пуста. Если вершина оптимальна, то задача решена. Если нет, то 2) используя определенные правила проверяем, нельзя ли утверждать, что задача не имеет оптимального решения (целевая функция не ограничена сверху или, соответственно, снизу на допустимом множестве). Если утверждать это можно, то задача неразрешима. Если нельзя, то 3) по определенному правилу ищем новую, лучшую вершину и переходим к пункту 1). Итак, для реализации предложенной схемы необходимо указать способ нахождения вершины допустимого множества, критерий оптимальности или неразрешимости, способ перехода от одной вершины к другой, лучшей. 11 1.3.2 Обоснование симплекс метода Пусть имеется задача линейного программирования в канонической форме: f = c1x1 + c2x2 K cnxn → max a11x1 + … + a1n xn = b1 (1.16) . . . . . . . . . (1.17) am1 x1 + … +amn xn = bm x1≥0, …, xm≥0 . Вводя в рассмотрение векторы Aj=(a1j , a2j ,…, amj )T , j= 1,n ; (1.18) мы можем переписать задачу в форме f = ( c , x) → max; A1x1 + A2x2 +…+ Anxn =b ; (1.19) x ≥ 0; и трактовать ее следующим образом: из всех разложений вектора b по векторам A 1 ,…, A n , с неотрицательными коэффициентами требуется выбрать хотя бы одно такое, коэффициенты x i , i=1,n, которого доставляют целевой функции f оптимальное значение. Не ограничивая общности считаем ранг матрицы А равным m и n>m (случай n=m тривиален). Дадим ряд определений. ОПРЕДЕЛЕНИЕ 1.5. Ненулевое допустимое решение x =(x 1 ,…,x n ) T называется опорным, если векторы Aj , соответствующие отличным от нуля координатам вектора x , линейно-независимы. ОПРЕДЕЛЕНИЕ 1.6. Ненулевое опорное решение назовем невырожденным, если оно имеет точно «m» положительных координат. ОПРЕДЕЛЕНИЕ 1.7. Если число положительных координат опорного решения меньше m, то оно называется вырожденным. 12 ОПРЕДЕЛЕНИЕ 1.7. Упорядоченный набор из «m» линейно − независимых векторов A i , соответствующих положительным координатам опорного решения назовем базисом. Пример 1.3. Дана система ограничений задачи: 2x1 + x2 + 3x3 = 2 x1 − 2x3 + x4 = 1 x1 ≥0, x2 ≥0, x3≥0, x4 ≥0. (1.20) Здесь m=2; A1=  2  , A2 =  1 , A3 =  3  , A4=  0  , b =  2  .  1 0  − 2  1  1 (1) T (2) Очевидно, что x =(0, 2, 0, 1) , x =(1, 0, 0, 0) T , x (3) =( 1 , 1, 0, 1 ) T , являются допустимыми решениями за2 2 дачи. Очевидно, что x (1) , x (2 ) – являются опорными решениями, поскольку системы векторов { A2, A4} и { A3}, линейно независимы, а x (3 ) не является опорным решением, так как { A1, A2, A4 } – линейно зависимы. Опорное решение x (1) − невырожденное, а x (2 ) – вырожденное. Базис невырожденного опорного решения определяется естественным образом. Для x (1 ) − это { A2, A4}. Приведем теорему, увязывающую понятие опорного решения и вершины допустимого множества. ТЕОРЕМА 1.1. Вектор x = (x 1 ,…,x n ) тогда и только тогда является опорным решением задачи, когда точка x является вершиной допустимого множества. Доказательство. Необходимость. Пусть x – опорное решение задачи (1.19). Если x = 0, то невозможность ее представления в виде x = αx (1) + βx ( 2) , где α >0, β >0 и x (1) ≠ x ( 2) – допустимые решения, очевидна. Пусть x ≠ 0 и x = ( x1 , x2 ,..., xk , 0,...,0 123 ) , n −k где x 1 >0, x 2 >0,…, x k >0. 13 Предположим, в противоречие с теоремой, что точка x не является вершиной допустимого многогранника: x (1) = ( x1(1) , x2(1) ,..., xn(1) ) и x ( 2) = ( x1( 2) , x2( 2) ,..., xn( 2) ) , x = α x (1) + β x ( 2) , α > 0 , β > 0 , α + β = 1. Так как последние n-k координат точки x равны нулю, то и последние n-k координат, как точки x (1) , так и точки x (2 ) должны быть равны 0.Таким образом, можно записать: x (1) = ( x1(1) , x2(1) ,..., xk(1) ,0,...,0), x ( 2) = ( x1(2) , x2(2) ,..., xk(2) ,0,...,0) . Ввиду допустимости точек x (1) и x ( 2) имеем: b = x1(1) A1 + x2(1) A2 + ... + xk(1) Ak (1.21) b = x1( 2) A1 + x2( 2) A2 + ... + xk( 2) Ak . (1.22) Вычитая почленно (1.22) из (1.21), получим: ( x1(1) − x1( 2) ) A1 + ( x2(1) − x2( 2) ) A2 + ... + ( xk(1) − xk( 2) ) Ak = 0 . (1.23) Точки x (1) и x (2) различны, следовательно, среди коэффициентов при A i (i=1,2,…,k) в (1.23) есть отличные от нуля. А это означает, что векторы A 1 , A 2 ,…, A k линейно зависимы, что противоречит тому, что x=(x 1 ,x 2 ,…,x k ,0,…,0)– опорное решение задачи. Следовательно, наше предположение неверно и x вершина допустимого многогранника. Достаточность. Пусть наоборот, точка x– вершина допустимого многогранника. Если x = 0, то x по условию опорное решение. Пусть, x ≠0 и для определенности x=(x 1 ,x 2 ,…,x k ,0,…,0), где x 1 >0, x 2 >0,…,x k >0. Предположим снова от противного, что при этом вектор x=(x 1 ,x 2 ,…,x k ,0,…,0) являясь, конечно, допустимым для нашей задачи, не является опорным решением. Тогда векторы A 1 , A 2 ,…, A k – линейно зависимы, т.е. существуют такие действительные числа α 1 , α 2 ,…, α k не все равные нулю, что справедливо равенство: α1 A1 + α 2 A2 + ... + α k Ak = 0 . (1.24) 14 Являясь допустимым, вектор x удовлетворяет условию: x1 A1 + x2 A2 + ... + xk Ak = b . (1.25) Умножим обе части равенства (1.24) на некоторый параметр θ и сначала вычтем почленно (1.24) из (1.25), а затем сложим (1.24) и (1.25).Получим: ( x1 − θα1 ) A1 + ( x 2 − θα 2 ) A2 + K + ( x k − θα k ) Ak = b , ( x1 + θα1 ) A1 + ( x 2 + θα 2 ) A2 + K + ( x k + θα k ) Ak = b . Так как x i >0 (i=1,2,…,k), то, очевидно, можно найти такое достаточно малое значение θ 0 > 0 множителя θ, что и в первом и во втором из полученных равенств, все коэффициенты будут неотрицательными. Тогда эти равенства (при θ = θ 0 ) означают, что n- мерные векторы x (1) = ( x1 − θ 0 α 1 ; x 2 − θ 0 α 2 ;K ; x k − θ 0 α k ;0; K ;0) и x (1) = ( x1 + θ 0 α 1 ; x 2 + θ 0 α 2 ;K ; x k + θ 0 α k ;0;K ;0) являются допустимыми (причем различными) решениями задачи. При этом, очевидно, имеем: 1 x (1) + 1 x ( 2) = ( x , x , K , x ,0, K ,0 ) = x , 1 2 k 2 2 а это противоречит тому, что x– вершина допустимого многогранника. Следовательно, x не может не быть опорным решением. Теорема доказана. Таким образом, задача о нахождении вершины допустимого множества свелась к задаче нахождения опорного решения, а, следовательно, к нахождению базиса. Будем считать, что исходный базис Ai1 , Ai 2 ,…, Ai m дан. Отправляясь от него покажем, как найти опорное решение. Сформулируем условие оптимальности решения, условие отсутствия решения. Покажем, как перейти к базису, дающему лучшее решение. Дан базис A i1 , A i 2 ,…, A i m . Тогда: 15 b= xi10 A i1 + xi 20 A i 2 +…+ xi m0 A i m =[ A i1 ,…, A i m ]*( xi10 ,…, xi m0 )T, ( xi10 ,…, xi m0 )T =[ A i1 ,…, A i m ]–1 * (b1,…,bm)T, дополнив найденный вектор нулевыми значениями переменных ( xi m +1 ,…, xi n ), получаем опорное решение. Исследуем его на оптимальность, для этого исследуем целевую функцию. Предварительно введем обозначения: x B = ( xi1 ,…, xi m ) T – вектор базисных переменных; B = [ A i1 ,…, A i m ]– матрица базисных векторов; x D =( x i m +1 ,…, xi n )– вектор свободных переменных; c B =( ci1 ,…, сi m ) T – вектор из коэффициентов целевой функции при базисных неизвестных; сD= ( ci m+1 ,…, ci n )T – вектор из коэффициентов целевой функции при свободных переменных; D=[ A i m +1 ,…, A i n ] – матрица свободных векторов (векторов, не вошедших в базис). С учетом введенных обозначений ограничения (1.19) можно переписать в виде: Bx B +Dx D =b. (1.26) Выразим базисные переменные через свободные x B =B −1 ( b–Dx D )= B − 1 b– B − 1 Dx D , (1.27) (при x D =0 получаем базисные компоненты опорного решения). Подставим x B в целевую функцию: f= c ВТ x B + c DТ x D = c ВТ B − 1 b–( c ВТ B − 1 D– c DТ )x D . Обозначим: α =(α 1 ,…,α n -m )=( c ВТ B − 1 D– c DТ ) и назовем его вектором оценок. (1.28) (1.29) Очевидно, что n −m α x c = ∑ α j ⋅ xi m + j . j =1 16 (1.30) Отметим, что произведение B − 1 A j представляет разложение вектора A j по базису, следовательно, в столбцах матрицы B − 1 D стоят разложения векторов, не попавших в базис (свободных) по базису. Проанализируем выражение для целевой функции (1.28): а) если все компоненты вектора оценок неотрицательные, то максимальное значение целевой функции достигается при x B = B − 1 b и x D =0, то есть построенное опорное решение – оптимальный план (решение) исходной задачи; б) если среди компонент вектора оценок α есть отрицательные, то опорное решение не оптимально, поскольку, как видно из (1.28)−(1.30), возможно увеличить значение f за счет некоторых компонент вектора x D ; при этом возможны две ситуации: 1) отрицательны компоненты вектора оценок, к примеру, α k1 , α k2 ,…,α ks и при этом, по крайней мере у одного из свободных векторов Aim + k1 , Aim + k 2 ,…, Aim + ks все компоненты разложения по базису не положительны, тогда из (1.27) видно, что можно неограниченно увеличить компоненты вектора x B за счет увеличения компоненты вектора x D , а, следовательно, целевая функция не ограничена; 2) в случае положительных компонент разложения по базису свободных векторов существует лучшее опорное решение, которое можно получить, введя в базис свободный вектор A S , соответствующий наименьшей из отрицательных компонент вектора оценок (с целью максимально прирастить f ) и, выведя из базиса тот вектор A i r , исходного базиса, для которого: min xi k0 xi k s > 0 xi k s = xi r0 xi (1.31) rs где: xi k 0 – компоненты x B ; xi k s – компоненты вектора A S , вводимого в базис, k= 1, m . Заменив базис, мы можем вновь перейти к построению опорного решения и его исследования. 17 Отметим, что координаты всех векторов в новом базисе могут быть найдены через координаты векторов в старом базисе по формулам:  xkj  x , при k = r  ′ =  ks xkj (1.32) x  x − rj x , j = 0, n , k = 1, m , k ≠ r.  kj xrs ks В итоге алгоритм решения задачи линейного программирования можно изобразить схемой, представленной на рисунке 1.4. 1.3.3 Нахождение начального базиса. В заключении обратимся к вопросу построения начального базиса. Здесь отметим, что, если в исходной задаче все ограничения имели вид “ ≤ ”, то в качестве начального базиса (как легко показать) можно брать базис из векторов при дополнительных переменных. В общем случае для построения начального базиса используется специальный прием, известный как метод искусственного базиса, изложенный ниже. Итак, пусть дана задача линейного программирования в канонической форме: f = c · x → max;  Ax = b  x ≥ 0. 18 (1.33) Исходные данные: Векторы b, A1 ,…, An , c, исходный базис Вычисление координат х ij векторов b, A1 ,…, An и оценок α j , j = 1, n Замена в базисе вектора Все α j ≥ 0? Конец: 1 опорное решение оптимально A i r на A S Отыскание s: α s = min αj α j <0 x xi0 и r : r0 = min x rs x is > 0 xis = min x /x x >0 ∃ α j : все x ≤0 ij 1 Конец: целевая функция не ограничена Рисунок 1.4 – Схема алгоритма решения задачи линейного программирования 19 Рассмотрим вспомогательную задачу: G = –y1 – y2 – … – ym → max; a11x1 + … + a1nxn + y1 = b1 a21x1 + … + a2nxn + 0·y1 + y2 = b2 (1.34) . . . . . . . . . . . . . am1x1 + … + amnxn + 0*y1 + …+ym = bm x i ≥ 0, i = 1, n , y i ≥ 0, i = 1, m . Так как целевая функция этой задачи ограничена сверху нулем, то задача имеет оптимальное решение. Переменные y 1 , y 2 , ….,y m называются искусственными переменными. Очевидно, что векторы A n+1 =(1,0,…,0) T , A n+2 =(0,1,0,…,0) T ,…, A n+m =(0,0,…,1) Т образуют базис для опорного решения x = ( 0, 0, ..., 0, b1 , b2 , ..., bm ) , 1424 3 n который называют искусственным базисом. Решая вспомогательную задачу симплекс-методом, мы найдем оптимальное решение x (0) =( x1(0) ,…, x n(0) , y1(0) ,…, y(m0) ). Если в этом решении, среди искусственных переменных есть положительные, то исходная задача линейного программирования неразрешима, если же yi(0) = 0 , i = 1, m , то базис, соответствующий оптимальному решению вспомогательной задачи, можно взять в качестве исходного базиса основной задачи. 20 1.3.4 Решение в форме симплекс − таблиц. В случае небольшого числа ограничений и переменных, приведенный в предыдущем разделе алгоритм можно легко реализовать без помощи ЭВМ, оформляя решение в виде симплекс-таблиц. Итак, дана задача: f = ( c , x ) → max A1 x1 + A2 x2 +…+Anxn=b, x ≥0 (1.35) и найден исходный базис A i1 , A i 2 ,…, A i m . Находим разложения всех векторов A1 ,…,An и b по базису. Полученные результаты заносим в таблицу 1.2. Таблица 1.2 - Симплекс таблица b c1 № п/п Базис cB. (опорное A1 решение) c2 … cn A2 … An 1 A i1 ci 2 Ai2 3 1 x10 x11 x12 … x1n ci 2 x20 x21 x22 … x2n A i3 ci 3 x30 x31 x32 … x3n . . . . . . . . m Aim xm0 xm1 xm2 … xmn ∑ cik xk0 α1 α2 … αn Оценки ci m f = m k =1 Здесь в столбце «Базис» указываются вектора A i k попавшие в базис; в столбце c B. записываются коэффициенты ci при соответствующих неизвестных из целевой функk ции; в столбце b (опорное решение) записываются координаты разложения вектора b по базису, то есть опорный план; в столбцах A1 , A2 ,…,A n записывают координаты разложения этих векторов по базису, то есть столбцы матрицы B − 1 D. После этого заполняют строку «Оценки»: 21 m f = ∑ ci k xk0 − значение целевой функции для k =1 найденного опорного решения и оценки m α j =z j −c j = ∑ ci xkj − c j – компоненты вектора k =1 k α= c ВТ B − 1 A j −c j . Далее , согласно алгоритму , выясняем , будет ли най денное опорное решение оптимальным , если да , то это решение ( план ) в столбце «b», а если нет , то выбираем вектор подлежащий вводу в базис , вектор подлежащий выводу из базиса и переходим к нахождению следующего опорного решения , заполняя новую таблицу . Пример 1.4. f = 5x1 + 10x2 → max 4x1 + 3x2 ≤ 96 5x1 + 8x2 ≤ 144 x1 + 4x2 ≤ 48 x1 ≥0, x2 ≥0 . Приведем задачу к каноническому виду : f= 5x1 + 10x2 + 0 · x3 + 0 ·x4+0 ·x5 → max 4x1 + 3x2 + x3 = 96 5x1 + 8x2 + x4 = 144 x1 + 4x2 + x5 = 48 xi ≥ 0, i = 1, 5 . Введя векторы :  96   4   b = 144 , A1 =  5  , A2  48  1     3  0  1     = 8 , A3 = 0 , A4 =  1 , A5 =  4  0  0       можем записать задачу в виде : f = 5x1 + 10x2 + 0 · x3+0 · x4 + 0 · x5 → max x1 A 1 + x2 A 2 + x3 A 3+ x4 A 4 + x5 A 5 = b 22  0  0  1   xi ≥ 0, i = 1, 5 . Очевидно, что векторы A 3 , A 4 , A 5 образуют базис и столь же очевидно, что относительно этого базиса: b = 96 A 3 + 144 A 4 + 48 A 5 A1 = 4 A3 + 5 A4 + 1 A5 A2 = 3 A3 + 8 A4 + 4 A5 A3 = 1 A3 + 0 A4 + 0 A5 A4 = 0 A3 + 1 A4 + 0 A5 A5 = 0 A3 + 0 A4 + 1 A5 Заполняем первую симплекс таблицу 1.3: Таблица 1.3 - Симплекс таблица b (опор5 10 № Базис cB ное реп/п A1 A2 шение) A3 A4 A5 1 A3 96 4 3 1 2 A4 144 5 8 1 3 A5 48 1 4 1 f =0 α 1=-5 α 2=-10 α 3=0 α 4=0 α 5=0 Оценки Поскольку среди α j есть отрицательные, то план не оптимален. Находим min α j =α 2 =–10, следовательно, в ноj =1,5 вый базис будем вводить вектор A 2 и столбец A 2 назовем ведущим. Найдем отношение координат вектора b к соответствующим, но только положительным координатам вектора A 2 и выберем минимальное из них: min (96/3, 144/8, 48/4) = 48/4. Из этого следует, что из базиса надо вывести A 5 . Строку « A 5 » будем называть ведущей. Число 4, стоящее на пересечении ведущей строки и ведущего столбца, будем называть ведущим элементом. 23 Переходим к нахождению нового опорного решения, для чего составляем новую симплекс таблицу с новым базисом A 3 , A 4 , A 2 . Заполнение новой симплекс таблицы начинаем с заполнения строки, соответствующей вновь вводимому вектору А 2 . Она получается делением элементов ведущей строки на ведущий элемент. Остальные элементы таблицы можно найти исходя из формулы xij′ = xij − xrj xrS xis , (1.36) где: xij′ – искомый элемент в новой таблице; x r S – ведущий элемент; x rj – элемент, стоящий в проекции элемента x ij на ведущий столбец; x is – элемент, стоящий в проекции x ij на ведущую строку. Таблица 1.4 Вторая симплекс таблица b 5 10 № Базис cB (опорное п/п A1 A2 решение) A3 A4 A5 1 A3 60 13/14 1 -3/4 2 A4 48 3 1 -2 3 A2 10 12 1/4 1 1/4 f=120 α 1=-5/2 5/2 Оценки Так как min α j = α1 = −5 / 2 <0 , то план не оптимален и в базис следует ввести A 1 . 24 Найдем: min ( 1360/ 4 , 483 , 112/ 4 ) = 48 / 3, то есть из базиса выводим A4 . Составляем симплекс таблицу (таблица 1.5). Таблица 1.5 Третья симплекс таблица b 5 10 № Базис cB (опорное п/п A1 A2 решение) A3 A4 A5 1 A3 8 1 -13/12 17/12 2 A1 5 16 1 1/3 -2/3 3 A2 10 8 1 -1/12 5/12 f =160 5/6 5/6 Оценки Так как все α j ≥ 0, то найденное опорное решение x 1 =16, x 2 =8, x 3 =8, x 4 =0, x 5 =0 доставляет целевой функции f максимальное значение f max = 5·16+10·8 =160. 1.4 Двойственная задача линейного программирования 1.4.1 Пример прямой и двойственной задачи линейного программирования Обратимся к задаче рационального использования ресурсов. Пусть для осуществления l технологических процессов T 1 ,…,T l предприятию требуется m ресурсов S 1 ,…, S m . Запасы ресурсов каждого вида ограничены и равны b 1 ,…,b m . 25 Известен расход ресурсов {a ij }, i= 1, m , j= 1, l на единицу продукции по каждому технологическому процессу и стоимость единицы продукции каждого типа c j , j= 1, l . Тогда, как нам известно, задача определения такого плана выпуска продукции x j , при котором доход от ее реализации будет максимальным, является задачей линейного программирования: l ∑ с j x j → max ; (1.37) ∑ a ij x j ≤ bi , i = 1, m ; (1.38) j =1 l j =1 x j ≥ 0, j = 1, l и ее решение может быть найдено симплекс-методом. Зададимся вопросом, какова с точки зрения предприятия ценность имеющихся в его распоряжении ресурсов. При решении этого вопроса будем иметь в виду, что ресурсы, которые предприятие не может полностью использовать, имеют для него очень низкую ценность, в том смысле, что предприятие не будет нести даже небольшие расходы на увеличение запасов этих ресурсов. Заметим при этом, что рыночная цена этих ресурсов может быть большой (скажем дорогостоящее неиспользуемое или используемое не на полную мощность оборудование). Наибольшую ценность будут иметь те ресурсы, которые в наибольшей степени ограничивают выпуск продукции, а следовательно и доход предприятия. Итак, можно считать, что каждый вид ресурса обладает некоторой, говорят, «теневой ценой», определяющей ценность данного ресурса для предприятия с точки зрения дохода от реализации выпускаемой продукции и зависящей от наличного запаса этого ресурса и потребности в нем для выпуска продукции. Ясно, что варьируя план выпуска продукции, мы тем самым варьируем теневые цены используемых ресурсов, а потому ставится задача нахождения оптимальных теневых цен, которые соответствуют максимальному доходу предприятия, то есть оптимальному распределению ре26 сурсов. Оптимальные теневые цены называют объективно обусловленными или оптимальными оценками. Построим математическую модель для определения оптимальных теневых цен. Обозначим через y i теневую цену ресурса S i . Величины y i должны быть такими, чтобы теневая цена ресурсов, используемых в любом технологическом процессе, на производство единицы продукции не была меньше получаемого дохода от единицы продукции. m ∑ a ij y j ≥ с j , j = 1, l . i =1 (1.39) Оптимальными теневыми ценами естественно считать такие, которые минимизируют общую теневую стоимость ресурсов, то есть величину m g * = ∑ b i y i → min. (1.40) i =1 Задача нахождения минимума целевой функции (1.40) при условиях (1.39) представляет собой задачу линейного программирования и называется двойственной по отношению к задаче (1.37)–(1.38). 1.4.2 Общая формулировка прямой и двойственной задачи Дадим достаточно общее определение двойственной задачи по отношению к прямой, заданной в виде: f = c 1 x 1 + c 2 x 2 + …+ c n x n → max при условиях (1.41) a11 x1 + a12 x2 +…+ a1n xn < R1 > b1 a21x1 + a22 x2 +…+ a2n xn < R2 > b2 . . . . . . . . . . . . . (1.42) am1 x1 + am2 x2 +…+ amn xn < Rm > bm x1 ≥ 0, x2 ≥ 0 ,…, xn ≥ 0, где: R1,R2, …, R n – операция отношения вида либо =, либо ≤ одновременно. 27 Очевидно, что любую задачу линейного программирования можно представить в одной из двух указанных форм. Тогда двойственной по отношению к задаче (1.41)−(1.42) будем называть задачу: f *=b1y1+b2y2+…+bmym → min (1.43) при условиях a11y1 + a21y2 +…+ am1ym ≥ c1 a12y1 + a22y2 +…+ am2ym ≥ c2 …………………………… (1.44) a1ny1 + a2ny2 +…+ amnym ≥ cn и, если в прямой задаче R i ≡ ( ≤ ), i= 1, n , то y1 ≥ 0, y2 ≥ 0,…, yn ≥ 0 . (1.45) Сформулируем правила построения двойственной задачи: а) целевая функция исходной задачи (1.41)−(1.42) задается на максимум, а целевая функция двойственной задачи (1.43)−(1.45) – на минимум; б) матрица системы сильных ограничений двойственной задачи получится из матрицы системы ограничений прямой задачи транспонированием; в) число переменных двойственной задачи равно числу сильных ограничений прямой, а число ограничений в двойственной задаче равно числу переменных прямой; г) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены системы сильных ограничений прямой задачи, а правыми частями системы сильных ограничений двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи. Отметим, что если все R i ≡( ≤ ) и, следовательно, в двойственной задаче выполнены условия (1.45) – переменные неотрицательны, то пара задач (1.41)–(1.42) и (1.43)–(1.45) называется симметричной . 28 1.4.3 Свойства двойственной задачи Приведем теоремы, устанавливающие зависимости между решениями прямой и двойственной задач. ТЕОРЕМА 1.2. Значение целевой функции задачи (1.41)–(1.42) при любом допустимом плане x не превышает значения целевой функции задачи (1.43)–(1.45) при любом ее допустимом плане y: f( x ) ≤ f * (y). Если для каких-нибудь x и у значения целевых функций совпадают, т.е. f( x ) = f * (y), то . x - оптимальное решение (1.41)–(1.42), y– оптимальное решение (1.43)– (1.45). Доказательство. Пусть x =(x 1 ,x 2 ,…,x n ) – допустимое решение задачи (1.41)–(1.42), у=(y 1 ,y 2 ,….,y m ) – допустимое решение задачи (1.43)–(1.45). Подставим решение x в ограничения (1.42), умножим первое равенство на y 1 , второе на y 2 ,…, m–е на y m и сложим полученные равенства: ( a11 x1 + a12 x2 +K+ a1n xn ) y1 + ( a 21 x1 + a 22 x2 +K+ a 2 n xn ) y 2 +K + ( a m1 x1 + a m2 x 2 + K + a mm x n ) y m = b1 y1 + b 2 y 2 + K + b m y m . Перегруппируем слагаемые в левой части: ( a11 y1 + a 21 y 2 +K+ a m1 y m ) x1 + ( a12 y1 + a 22 y 2 +K+ am2 y m ) x2 +K + ( a1n y1 + a2n y 2 +K+ a mn y m ) xn = b1y1 + b2 y 2 +K+ bm y m . (1.46) Так как y – допустимое решение задачи (1.43)–(1.45), то для любого j (j=1,2,…,n) , имеем: a1j y 1 + a 2j y 2 + K + a mj y n ≥ c j . Заменяя в (1.46) суммы, заключенные в скобки, соответствующими c j и учитывая, что x j ≥ 0 , получаем: c1 x1 + c2 x2 +K+ cn xn ≤ b1y1 + b2 y 2 +K+ bm y m , или, что тоже самое f( x )≤f * (y). Первая часть теоремы доказана. Пусть для каких-нибудь x ,y имеем: ( c,x ′ )>( b T ,y). Допустим от противного, что x не является оптимальным решением задачи (1.41)–(1.42). Это значит, что есть такое другое допустимое решение x ′ задачи (1.41)–(1.42), что ( c,x ′ ) > ( c,x ) = ( b T ,y), 29 а это противоречит первой части данной теоремы. Следовательно, при нашем условии x– оптимальное решение задачи (1.41)–(1.42). Аналогично показывается, что y оптимальное решение задачи (1.43)–(1.45).Теорема доказана. ТЕОРЕМА 1.3. Если одна из пар двойственных задач (1.41)–(1.42) или (1.43)–(1.45) имеет оптимальное решение, то и другая также имеет оптимальное решение, причем их оптимумы совпадают (max f=min f * ). Если целевая функция одной из пары двойственных задач не ограничена (для прямой – сверху, а для двойственной − снизу), то допустимая область другой задачи пуста. Доказательство. Ввиду взаимной двойственности задач (1.41)–(1.42) и (1.43)–(1.45) достаточно провести доказательство, принимая за исходную одну из задач. Пусть, например, задача (1.41)–(1.42) имеет оптимальные решения, и x (0) = ( x1(0) , x2(0) ,..., xn(0) ) – одно из них, найденное симплекс-методом, и Ai1 , A i 2 ,..., A i m – его базис. Тогда на последней итерации имеем α j = z j −c j ≥ 0 (j=1,2,…,n) так что z j ≥ c j , j=1,2,…,n, или, в векторной форме ( z1 , z 2 ,..., z n )≥(c1 ,c2 ,...,cn ) . (1.47) При рассмотрении симплекс-метода мы выяснили, что вектор ( z1 , z 2 ,..., z n ) может быть найден по формуле ( z1 , z 2 ,..., z n ) = (ci1 ,ci 2 ,...,ci m ) B −1 A = c B B −1 A , где B − 1 – матрица, обратная к базисной матрице B = ( A i1 , A i 2 ,..., A i m ) , A –матрица системы ограниченийуравнений задачи (1.42): A = ( A1 , A2 ,..., An ) .Следовательно, из (1.47) имеем: (ci1 ,ci 2 ,...,ci m ) B −1 A ≥ (c1 ,c2 ,...,cn ) = c (1.48) Введем обозначение: (ci1 ,ci 2 ,..., ci m ) B −1 = y = (y1 , y 2 ,..., y m ). Тогда неравенство (1.48) принимает вид 30 yA≥ c. Оно означает, что вектор y = c B B −1 является допустимым решением задачи (1.43)-(1.45). Докажем, что y– оптимальное решение задачи (1.43) – (1.45). Имеем: (0) (y , b) = ((ci1 ,ci 2 ,...,ci m ) , B -1b ) = ((ci1 ,ci 2 ,...,ci m ) ,( x1(0) , x2(0) ,..., xm )) = = ci1 xi(0) + ci 2 xi(0) +...+ ci m xi(0) ) = (c, x (0) ) . 1 2 m Таким образом, значение целевой функции задачи (1.43) –(1.45) при её допустимом решении y совпадает с значением целевой функции задачи (1.41)–(1.42) при её допустимом решении x (0) . Согласно теореме 1.2 это означает, что y оптимальное решение задачи (1.43)–(1.45). Первая часть теоремы доказана. Докажем вторую её часть. Пусть известно, что целевая функция, например, задачи (1.41)–(1.42) не ограничена сверху на допустимом множестве. Допустим, от противного, что задача (1.43)–(1.45) имеет при этом допустимое решение, и пусть y – одно из них. Ввиду неограниченности целевой функции задачи (1.41)–(1.42) найдётся такое допустимое её решение x, для которого значение целевой функции будет больше числа (b,y): (c, x ) > (b,y ) , что противоречит теореме 1.2. Теорема доказана. При доказательстве первой части теоремы мы установили следующее: если B – базисная матрица оптимального опорного решения канонической задачи (1.41)–(1.42), то y = c B B −1 – оптимальное решение двойственной к (1.41)–(1.42) задачи (1.43)-(1.45). Этим фактом мы будем пользоваться в дальнейшем. Рассмотрим, в качестве примера, следующую задачу и двойственную к ней. 31 f =5x1+10x2 → max 4x1 + 3x2 ≤ 96 f *=96y1+144y2+48y3 → min 4y1 + 5y2 + y3 ≥ 5 5x1 + 8x2 ≤ 144 3y1 + 8y2 + 4y3 ≥ 10 x1 + 4x2 ≤ 48 x1 ≥ 0, y1 ≥ 0, y2 ≥ 0, y3 ≥ 0. x2 ≥ 0. Оптимальное решение прямой задачи, приведенное в последней симплекс таблице: x T =(16,8,8,0,0) получено в базисе A 3 , A 1 , A 2 . Найдем матрицы B, B − 1 143 12 –13 17 B= 058 ; 4 –8 ; B − 1 = (1/12) 0 014 –1 5 y* = cB B − 1 = (0, 5/6, 5/6); max f = f (x * ) = 160 = min f *(y * ). В том случае, когда среди векторов A 1 , A 2 , …, A n прямой задачи(1.41)−(1.42) имеется m – единичных ( Aj1 , Aj2 ,…, Ajm ), решение двойственной задачи может быть найдено проще, а именно, компоненты вектора y k =α jk +c jk , k = 1, m ; y * =(y 1 ,…, y m ) T , где α jk – элементы строки оценок в последней симплекстаблице решения прямой задачи, а c jk – соответствующие коэффициенты целевой функции прямой задачи. Рассмотрев предыдущий пример, можем убедиться, что поскольку в исходной задаче векторы A 3 , A 4 , A 5 единичные, то : y1 = α3 + c3 = 0 + 0 = 0 y2 = α4 + c4 = 5/6 + 0 = 5/6 y3 = α5 + c5 = 5/6 + 0 = 5/6 y * = (0; 5/6; 5/6). 32 1.4.4 Анализ чувствительности Нас будет интересовать вопрос: какое воздействие окажут изменения, вносимые в те или иные параметры задачи линейного программирования, на ее решение, на решение двойственной задачи, на оптимальные значения целевой функции ? А именно, изучим: а) воздействие дополнительного количества дефицитного ресурса; б) воздействие дополнительного количества недефицитного ресурса; в) воздействие изменений в коэффициентах целевой функции. Для наглядности исследований рассмотрим прямую и двойственную задачи линейного программирования и их геометрическое решение (рисунок 1.5). Пример 1.5. f = 2x1 + 3x2 → max x1 + x2 ≤ 4 –x1 + x2 ≤ 2 x1 ≥ 0, x2 ≥ 0 f *= 4y1 + 2y2 → min y1 – y2 ≥ 2 y1 + y2 ≥ 3 y1 ≥ 0, y1 ≥ 0 33 x2 y2 f *= 4y1 + 2 y2 =c0 =11 M(1,3) f = 2x1 + 3x2 = 11 M(2.5;0.5) x1 y1 f * = (4 +∆b1) y1 + (2 + ∆b2) y2 = c1 f max = f x 1 =1 x2 =3 = 11 * f min = f* y 1 = 2.5 y 2 = 0.5 = 11 Рисунок 1.5 - Решение задачи линейного программирования геометрическим способом. Приведем заключительную симплекс-таблицу решения прямой задачи. Таблица 1.6 – Заключительная c1 Базис cB b 2 опорн. A1 A1 2 1 1 A2 3 3 f = 11 αj симплекс-таблица c2 c3 c4 3 A2 A3 A4 1 1/2 1/2 2,5 y1 –1/2 1/2 0,5 y2 Очевидно, что значение целевой функции задачи линейного программирования f = f (b 1 , b 2 ,…, b m ) зависит, вообще говоря, от запасов ресурсов. Изменение ресурсов b i на малую величину ∆b i , i = 1,2,...,m ведет к изменению значения max f =min f * , но изменение min f * происходит, 34 при малых ∆b i , не за счет изменения точки, в которой достигается min f * (допустимая область двойственной задачи вообще не изменится при изменении b i ), а за счет изменения наклона поверхности (линии) уровня целевой функции f * , коэффициенты которой зависят от b i +∆b i . Следует отметить, что при больших изменениях b i , i= 1, m или даже некоторых из них, оптимальное решение двойственной задачи может перейти в другую угловую точку. Нас будет интересовать в каких пределах изменение запасов b i на величину ∆b i не влечет изменения двойственных оценок (теневых цен). Множество таких значений ∆b i будем называть областью устойчивости решения двойственной задачи. Рассмотрим влияние на устойчивость двойственных оценок приращений ∆b i дефицитных и недефицитных ресурсов. Очевидно, что увеличение недефицитных ресурсов не приведет к увеличению прибыли, а появление дополнительного количества дефицитных ресурсов улучшает, вообще говоря, оптимальное значение целевой функции. Однако необходимо принять во внимание, что изменение оптимального решения за счет увеличения количества дефицитных ресурсов приведет к улучшению значения целевой функции (прямой задачи) только в том случае, если сумма дополнительных издержек по обеспечению дополнительным количеством ресурса не превышает сумму прибыли, полученной в результате его использования. В рассмотренном примере увеличение ∆b 2 на величину большую 2, то есть b 2 +∆b 2 >4, при фиксированном b 1 =4, перемещает оптимальное решение двойственной задачи в точку y 1 =3, y 2 =0 и min f * = max f =12. Таким образом, увеличение на 1 единицу произошло за счет увеличения ресурса b 2 на величину ≥2. Причем, начиная со значения b 2 =4, этот ресурс перестает быть дефицитным. При 0<∆b 2 <2 и ∆b 1 >0 точка минимума f * не меняется, а значение целевой функции f * увеличивается, а следовательно, увеличивается и значение целевой функции прямой задачи. Это и есть область устойчивости двойственных оценок дефицитных ресурсов. Здесь же отметим, что если 35 b 1 =4, b 2 >4, то уменьшая недефицитный ресурс b 2 на величину ∆b 2 <0, мы при b 2 +∆b 2 <4 добьемся того, что оптимальное решение двойственной задачи будет достигаться в точке (2,5; 0,5) и ресурс y 2 станет дефицитным, но значение min f * = max f уменьшится. В общем случае рассмотрим иной подход к изучению влияния ∆b i на область устойчивости двойственных оценок. Пусть B– матрица векторов исходной задачи, составляющих базис, в котором решение прямой задачи оптимально. Тогда последняя симплекс-таблица 1.7 формально может быть получена так: Таблица 1.7 – Итоговая симплекс-таблица Базис Опорное c2 c1 cB решение A i1 … Aim ci 1 ... ci B−1 b … cn A1 A2 … An B − 1 A1 B − 1 A2 … B − 1 An α1 α2 … αn m Оценка Очевидно, что изменения запасов ресурсов на величины ∆b i не окажет влияния ни на разложения векторов A 1 ,…, A n по базису, ни на значения A j , а стало быть и на значения двойственных оценок, если только B − 1 ( b+∆ b), будет оставаться допустимым опорным решением задачи линейного программирования, т.е. его компоненты будут оставаться неотрицательными. Условия неотрицательности компонент вектора B − 1 ( b+∆ b) позволит определить область устойчивости двойственных оценок и выяснить порознь влияние дополнительного количества дефицитных и недефицитных ресурсов. В рассматриваемом примере  1 1 B =   , − 1 1   36  4 b =   ,  2 1 / 2 B −1 =  1 / 2 −1/ 2 . 1 / 2  Оптимальное опорное решение (значения базисных переменных): 1  B −1b =   .  3 Пусть мы внесли изменения в вектор правых частей (увеличили запасы ресурсов)  4 + ∆b1  , b + ∆b =   2 + ∆b   2 тогда оптимальное опорное решение новой задачи (значения базисных переменных): 1 1 1    1   2 + ∆b1 − 1 − ∆b2  1 + ∆b1 − ∆b2  2 2 2 = 2  B − 1( b + ∆ b ) =  1 1 1 1      2 + ∆b1 + 1 + ∆b2   3 + ∆b1 + ∆b2      2 2 2 2 при условиях: 1 + (1/2)∆b1 –(1/2)∆b2 ≥ 0 3 + (1/2)∆b1 + (1/2)∆b2 ≥ 0 ∆b1 ≥ 0, ∆b2 ≥ 0. Область устойчивости двойственных оценок в этом случае нетрудно изобразить геометрически (рисунок 1.6). ∆b2 ∆b1 Рисунок 1.6 – Область устойчивости 37 Итак, область устойчивости: ∆b 1 – любое неотрицательное и ∆b 2 может принимать значения 0 ≤ ∆b 2 ≤2+∆b 1 . В частности, при ∆b 1 = 0, 0≤∆b 2 ≤2 . В задачах большей размерности мы сможем, вообще говоря, лишь проверять попадают ли компоненты вектора B − 1 (b+∆b) в область устойчивости. Обратимся к вопросу влияния вариации коэффициентов целевой функции (c 1 ,…,c n ) прямой задачи на оптимальное решение. В частности нас интересует вопрос устойчивости решения прямой задачи относительно вариации коэффициентов целевой функции. Легко видеть, что вариация c 1 ,…,c n не оказывает влияния на допустимую область задачи линейного программирования и нас интересует область изменения ∆c 1 , ∆c 2 ,…, ∆c n , в которой точка достижения оптимального решения не изменится. Очевидно, что если рассматривать в качестве прямой задачи двойственную, то решение проблемы будет аналогично рассмотренному выше (роль b 1 ,…,b m будут играть c 1 ,…, c n ). Например, в рассмотренном примере базисом оптимального решения двойственной задачи будут естественно векторы A 1 =(1,1) T и A 2 =(−1,1) T . Оптимальное опорное решение (значение базисных переменных) −1 1 − 1  2   0, 5 0, 5   2   2, 5  − 1    =  B с =     =   . 1 1 3 − , 5 , 5 3 , 5          Для изучения устойчивости внесем изменения в вектор цен с + ∆c = (2 + 3∆c 1 + ∆c 2 ). Найдем оптимальное опорное решение новой двойственной задачи (значение базисных переменных). 3 1  1  1 + ∆ с + + ∆ с  2 + ∆ с 1 2 2 2   0.5 0.5  1 2 − 1 = . B (с + ∆с ) =      − 0.5 0.5  3 + ∆с2   − 1 − 1 ∆с + 3 + 1 ∆с     2 1 2 2 2 Потребуем: 5/2 + (1/2)∆c 1 + (1/2)∆c 2 ≥ 0 1/2 − (1/2)∆c 1 + (1/2)∆c 2 ≥ 0 ∆c 1 ≥ 0, ∆c 2 ≥ 0, 38 что определяет область устойчивости решения прямой задачи относительно вариации коэффициентов (см. рисунок 1.7). ∆c2 Область устойчивости -5 -1 ∆c1 1 -5 Рисунок 1.7 − Область устойчивости 1.4.5 Экономическая интерпретация двойственных задач Экономическую интерпретацию двойственных задач и двойственных оценок рассмотрим на примере. Для производства продукции двух видов А и В используются ресурсы трех видов I,II,III. Запасы ресурсов – b i , затраты ресурсов a ij на производство единицы продукции каждого вида и цена c j единицы продукции приведены в таблице 1.8. Таблица 1.8 – Таблица выпускаемой продукции Ресурсы А В I II III 1 2 1 2 1 4 1 ci Запасы ресурсов 10 30 8 39 Требуется так спланировать производство, чтобы прибыль от реализации продукции была максимальной. Оценить теневые цены ресурсов и произвести анализ решения двойственной задачи. Обозначим xi, i = 1, 3 план выпуска продукции А, В, С, y i – теневые цены ресурсов I,II,III типа. Тогда прямая и двойственная задачи имеют вид: f = 2x1 + x2 → max x1 + x2 ≤ 10 2x1 + 4x2 ≤ 30 x1 ≤ 8 x1 ≥ 0 x3 ≥ 0 f * = 10y1 + 30y2 + 8y3 → min y1 + 2y2 + y3 ≥ 2 y1 + 4y2 + 0y3 ≥ 1 y1 ≥ 0 y2 ≥ 0 y3 ≥ 0. Решение прямой и двойственной задач приведено в заключительной симплекс-таблице 1.9. Таблица 1.9 – Симплекс-таблица Базис 2 1 сВ b А1 А2 2 8 1 А1 1 2 1 А2 4 А4 Оценки f=18 А3 А4 А5 1 –4 1 1 1 –1 2 1 Оптимальный план производства продукции вида А: x 1 =8; вида В: x 2 =2; f max =18. Ресурсы типа I и III имеют теневые цены, большие нуля, поэтому дефицитны и в оптимальном плане используются полностью, что легко проверить по 1-му и 3-му ограничениям прямой задачи. Ресурс II типа имеет теневую цену равную нулю, является недефицитным и в оптимальном плане недоиспользуется в объеме 6 ед., что легко вычисляется из 2-го ограничения прямой задачи. Увеличение запасов дефицитного ресурса I типа ведет к увеличению прибыли от дополнительно произведенной продукции на одну единицу за счет следующих изменений в плане выпуска продукции: выпуск продукции вида В увеличивается на одну едини40 цу, выпуск продукции вида А остается на прежнем уровне, а использование ресурса II типа увеличивается на 4 единицы (результаты получены из компонент столбца A 3 и легко проверяются непосредственной проверкой). По аналогии при увеличении запасов дефицитного ресурса III типа на одну единицу прибыль от реализации дополнительно произведенной по новому оптимальному плану продукции также возрастает на одну единицу, при этом, как видно из последнего столбца симплекс – таблицы 1.9 необходимо увеличить выпуск продукции вида А на одну единицу и одновременно выпуск продукции вида В сократить на одну единицу. Использование ресурса II типа уменьшится еще на 2 единицы. 41