И. В. Корытов С. С. Дашиева линейное программирование в примерах и задачах Симплексметод Метод искусственного базиса Двойственные задачи Решение
 Скачать 328.07 Kb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Восточно-Сибирский государственный технологический университет И.В.Корытов С.С.Дашиева ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ в примерах и задачах Симплекс-метод Метод искусственного базиса Двойственные задачи Решение двойственной задачи с использованием теорем двойственности Типовой расчет (задания из 20 вариантов) Улан-Удэ 2002 2 3 Введение Пособие содержит материал, относящийся к основным вопросам темы «Линейное программирование». Здесь рас- сматривается только алгебраический подход к решению задач. Предполагается, что студент знаком с теоретически- ми сведениями, касающимися излагаемых вопросов, и уме- ет решать основную задачу линейного программирования геометрическим методом. Основным математическим аппа- ратом решаемых ниже задач являются элементарные преоб- разования матриц, применяемые в виде метода Жордана – Гаусса с выбором ведущего элемента. Пособие посвящено практическому решению задач. Ход решения построен с выделением этапов и шагов, снаб- женных необходимыми комментариями, и может одновре- менно служить образцом оформления при выполнении сту- дентом самостоятельной работы. Разбираемые примеры по- добраны в определенной последовательности по схеме: ре- шение исходной задачи линейного программирования – со- ставление условий двойственной задачи – решение двойст- венной задачи двумя способами. Метод искусственного ба- зиса с точки зрения вычислительных процедур не отличает- ся от стандартного симплекс-метода, дополнительные дей- ствия связаны с видоизменением целевой функции путем добавления специального слагаемого, называемого штраф- ной функцией. Смысл этих действий понятен из примера, поэтому метод искусственного базиса рассматривался не под отдельным заголовком, а в ходе решения одной из за- дач. Задания типового расчета составлены таким образом, что одна из взаимно двойственных задач решается обычным симплекс-методом, а другая – методом искусственного ба- зиса. Пособие адресовано студентам третьего курса эконо- мических специальностей. Решение задачи линейного программирования симплекс-методом Пример 1. Решить задачу линейного программирова- ния симплекс-методом, введя при необходимости искусст- венный базис. 0 , 0 5 6 10 2 3 12 4 2 min 5 3 2 1 1 2 2 1 2 1 2 1 ≥ ≥ ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≤ ≤ ≥ + ≥ + → + = x x x x x x x x x x F Приведение условия к каноническому виду Так как система ограничений состоит из неравенств, для приведения условия к каноническому виду нужно вве- сти в каждое неравенство балансовые переменные 6 5 4 3 , , , x x x x : 6 , , 1 , 0 5 6 10 2 3 12 4 2 6 1 5 2 4 2 1 3 2 1 K = ≥ ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = + = + = − + = − + j x x x x x x x x x x x j Матрица системы ограничений 4 5 ⎟⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − 5 1 0 0 0 0 1 6 0 1 0 0 1 0 10 0 0 1 0 2 3 12 0 0 0 1 4 2 не содержит в себе единичную матрицу, следовательно ба- лансовые переменные не образуют базиса. Умножение на 1 − обеих частей первого и второго уравнений приведет к недопустимому базисному решению. Поэтому необходимо ввести в эти уравнения искусственные переменные 2 1 и r r : 0 , 0 ; 6 , , 1 , 0 5 6 10 2 3 12 4 2 2 1 6 1 5 2 2 4 2 1 1 3 2 1 ≥ ≥ = ≥ ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = + = + = + − + = + − + r r j x x x x x r x x x r x x x j K Выражение искусственных переменных через свобод- ные: 2 3 10 , 4 2 12 4 2 1 2 3 2 1 1 x x x r x x x r + − − = + − − = Составление штрафной функции: ). 6 5 22 ( ) 2 3 10 4 2 12 ( ) ( 4 3 6 1 4 2 1 3 2 1 2 1 x x x x M x x x x x x M r r M + + − − = = + − − + + − − = + В задаче минимизации штрафная функция вводится в целевую функцию со знаком «+» 1 : 1 В задаче максимизации, соответственно, со знаком «–». 22 ) 6 5 ( ) 5 3 ( ) 6 5 22 ( 5 3 4 3 2 1 4 3 6 1 2 1 M Mx Mx x M x M x x x x M x x F + + + − + − = = + + − − + + = Условие задачи с искусственным базисом в канониче- ском виде: 0 , 0 ; 6 , , 1 , 0 5 6 10 2 3 12 4 2 22 ) 6 5 ( ) 5 3 ( 2 1 6 1 5 2 2 4 2 1 1 3 2 1 4 3 2 1 ≥ ≥ = ≥ ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = + = + = + − + = + − + = − − − − − − r r j x x x x x r x x x r x x x M Mx Mx x M x M F j K Расширенная матрица задачи линейного программиро- вания: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − − − 5 0 0 1 0 0 0 0 1 0 6 0 0 0 1 0 0 1 0 0 10 1 0 0 0 1 0 2 3 0 12 0 1 0 0 0 1 4 2 0 22 0 0 0 0 5 6 3 5 1 M M M M M В матрице отделены сплошными линиями: столбец, соот- ветствующий переменной F , строка коэффициентов целе- вой функции и столбец свободных членов. Пунктирной ли- нией отделены столбцы единичной матрицы. Ранг расширенной матрицы 5 = rang , следовательно, количество базисных переменных равно пяти. Базисные переменные: 2 1 6 5 , , , , r r x x F 6 7 Свободные переменные: 4 3 2 1 , , , x x x x Шаг 1. Составление первой симплекс-таблицы В задаче с искусственным базисом первая симплекс- таблица соответствует первому искусственному базисному решению. Симплекс-таблица 1 БП F 1 x 2 x 3 x 4 x 5 x 6 x 1 r 2 r Реше ние Отноше- ние F 1 5M-3 6M-5 -M -M 0 0 0 0 22M 1 r 0 2 4 -1 0 0 0 1 0 12 12:4=3 2 r 0 3 2 0 -1 0 0 0 1 10 10:2=5 5 x 0 0 1 0 0 1 0 0 0 6 6:1=6 6 x 0 1 0 0 0 0 1 0 0 5 5:0 ∞ → Комментарий к симплекс-таблице 1. Решение (искусственное базисное) в 8-мерном про- странстве X =(0,0,0,0,6,5,12,10). Решение в двумерном (по количеству исходных пере- менных в условии задачи) пространстве X =(0,0). Данная точка находится за пределами многоугольника решений. Значение целевой функции F (0,0)=22 M – «штраф- ное», так как точка не принадлежит многоугольнику реше- ний. Проверка критерия оптимальности: задача на мини- мизацию, в строке целевой функции имеются положитель- ные коэффициенты при свободных переменных 1 x и 2 x , следовательно, оптимальное решение не достигнуто. Необ- ходимо выбрать среди свободных включаемую в базис пе- ременную. Выбор включаемой в базис переменной: наибольший положительный коэффициент 5 6 2 − = M с при переменной 2 x Проверка критерия допустимости: среди оценочных отношений (последний столбец таблицы) встречаются ко- нечные положительные, следовательно, возможен выбор исключаемой из базиса переменной. Выбор исключаемой переменной: среди оценочных отношений минимальным является отношение, соответст- вующее переменной 1 r , которая и будет исключена из бази- са на этом шаге. Ведущим элементом при пересчете будет элемент, стоящий на пересечении строки, соответствующей исклю- чаемой переменной 1 r (ведущей строки), и столбца, соот- ветствующего включаемой переменной 2 x (ведущего столбца). В таблице ведущий элемент обведен рамкой. Пересчет таблицы в матричной записи. Элементы ведущей строки делятся на ведущий эле- мент: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − − − 5 0 0 1 0 0 0 0 1 0 6 0 0 0 1 0 0 1 0 0 10 1 0 0 0 1 0 2 3 0 3 0 4 1 0 0 0 4 1 1 2 1 0 22 0 0 0 0 5 6 3 5 1 M M M M M 8 9 Далее выполняются элементарные преобразования над строками матрицы, в результате которых на месте ведущего столбца окажется столбец единичной матрицы: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − − + + − − − − 5 0 0 1 0 0 0 0 1 0 3 0 4 1 0 1 0 4 1 0 2 1 0 4 1 2 1 0 0 1 2 1 0 2 0 3 0 4 1 0 0 0 4 1 1 2 1 0 15 4 0 4 5 2 3 0 0 4 5 2 1 0 2 1 2 1 M M M M M Базисные переменные: 2 6 5 2 , , , , r x x x F Свободные переменные: 1 4 3 1 , , , r x x x Шаг 2. Составление следующей симплекс-таблицы Так как в базисе осталась еще одна искусственная пе- ременная, то новая таблица соответствует второму искусст- венному базисному решению. Симплекс-таблица 2 БП F 1 x 2 x 3 x 4 x 5 x 6 x 1 r 2 r Реше- ние Отноше- ние F 1 2 1 2 − M 0 4 5 2 1 − M -M 0 0 4 5 2 3 + − M 0 15 4 + M 2 x 0 2 1 1 4 1 − 0 0 0 4 1 0 3 3: 2 1 =6 2 r 0 2 0 2 1 -1 0 0 2 1 − 1 4 4:2=2 5 x 0 2 1 − 0 4 1 0 1 0 4 1 − 0 3 3: 2 1 − <0 6 x 0 1 0 0 0 0 1 0 0 5 5:1=5 Комментарий к симплекс-таблице 2. Решение (искусственное базисное) в 8-мерном про- странстве X =(0,3,0,0,3,5,0,4). Решение в двумерном пространстве X =(0,3). Данная точка также находится за пределами многоугольника реше- ний. Значение целевой функции F (0,3)=4 M +15 – «штраф- ное», так как точка не принадлежит многоугольнику реше- ний. Проверка критерия оптимальности: задача на мини- мизацию, в строке целевой функции имеются положитель- ные коэффициенты при свободных переменных 1 x и 3 x , следовательно, оптимальное решение не достигнуто. Необ- ходимо выбрать среди свободных включаемую в базис пе- ременную. Выбор включаемой в базис переменной: наибольший положительный коэффициент 2 1 2 1 − = M с при переменной 1 x Проверка критерия допустимости: среди оценочных отношений (последний столбец таблицы) встречаются ко- нечные положительные, следовательно, возможен выбор исключаемой из базиса переменной. Выбор исключаемой переменной: среди оценочных отношений минимальным является отношение, соответст- вующее переменной 2 r , которая и будет исключена из бази- са на этом шаге. Ведущим элементом при пересчете будет элемент, стоящий на пересечении ведущей строки, соответствующей исключаемой переменной 2 r , и ведущего столбца, соответ- ствующего включаемой переменной 1 x Пересчет таблицы в матричной записи. 10 11 Элементы ведущей строки делятся на ведущий эле- мент: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − − + + − − − − 5 0 0 1 0 0 0 0 1 0 3 0 4 1 0 1 0 4 1 0 2 1 0 2 2 1 4 1 0 0 2 1 4 1 0 1 0 3 0 4 1 0 0 0 4 1 1 2 1 0 15 4 0 4 5 2 3 0 0 4 5 2 1 0 2 1 2 1 M M M M M Далее выполняются элементарные преобразования над строками матрицы, в результате которых на месте ведущего столбца окажется столбец единичной матрицы: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − − − − − + − + − − − 3 2 1 4 1 1 0 2 1 4 1 0 0 0 4 4 1 8 3 0 1 4 1 8 3 0 0 0 2 2 1 4 1 0 0 2 1 4 1 0 1 0 2 4 1 8 3 0 0 4 1 8 3 1 0 0 16 4 1 8 9 0 0 4 1 8 9 0 0 1 M M Базисные переменные: 6 5 2 1 , , , , x x x x F Свободные переменные: 2 1 4 3 , , , r r x x Шаг 3. Составление очередной симплекс-таблицы Искусственных переменных в базисе нет, следователь- но, новая таблица соответствует первому допустимому ба- зисному решению. Симплекс-таблица 3 БП F 1 x 2 x 3 x 4 x 5 x 6 x 1 r 2 r Реше- ние F 1 0 0 8 9 − 4 1 − 0 0 8 9 + − M 4 1 + − M 16 2 x 0 0 1 8 3 − 4 1 0 0 4 1 4 1 − 2 1 x 0 1 0 4 1 2 1 − 0 0 2 1 − 2 1 2 5 x 0 0 0 8 3 4 1 1 0 4 1 − 4 1 4 6 x 0 0 0 4 1 − 2 1 0 1 4 1 2 1 − 3 Комментарий к симплекс-таблице 3. Решение (допустимое базисное) в 8-мерном простран- стве X =(2,2,0,0,4,3,0,0). Решение в двумерном пространстве X =(2,2). Данная точка является угловой точкой многоугольника решений. Значение целевой функции F (2,2)=16 свободно от «штрафа», так как точка принадлежит многоугольнику ре- шений. Проверка критерия оптимальности: задача на мини- мизацию, в строке целевой функции все коэффициенты при свободных переменных отрицательны, следовательно, по- лучено оптимальное решение. Таким образом, решение X =(2,2), при котором целе- вая функция достигает своего минимального значения F (2,2)=16, будет ответом в данной задаче. 12 13 Составление условия двойственной задачи Пример 2. Составить условие задачи, двойственной к данной. 0 , 0 5 6 10 2 3 12 4 2 min 5 3 2 1 1 2 2 1 2 1 2 1 ≥ ≥ ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≤ ≤ ≥ + ≥ + → + = x x x x x x x x x x F Приведение условия к стандартному виду Поскольку в исходной задаче требуется найти мини- мум целевой функции, то ограничения в системе необходи- мо привести к неравенствам типа " " ≥ 0 , 0 5 6 10 2 3 12 4 2 min 5 3 2 1 1 2 2 1 2 1 2 1 ≥ ≥ ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ − ≥ − − ≥ − ≥ + ≥ + → + = x x x x x x x x x x F Работа с расширенными матрицами Расширенная матрица исходной задачи: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − 5 0 1 6 1 0 10 2 3 12 4 2 5 3 F Матрица, транспонированная к матрице исходной за- дачи (расширенная матрица двойственной задачи): ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − 5 6 10 12 0 1 2 4 5 1 0 3 2 3 Z Составление ограничений и целевой функции двойст- венной задачи Ограничения двойственной задачи (на основе первых двух строк расширенной матрицы): ⎩ ⎨ ⎧ − + ≥ − + ≥ 3 2 1 4 2 1 2 4 5 3 2 3 y y y y y y Целевая функция двойственной задачи (на основе по- следней строки расширенной матрицы): max 5 6 10 12 4 3 2 1 → − − + = y y y y Z Условие двойственной задачи 4 , , 1 , 0 5 2 4 3 3 2 max 5 6 10 12 3 2 1 4 2 1 4 3 2 1 K = ≥ ⎩ ⎨ ⎧ ≤ − ≤ − + → − − + = j y y y y y y y y y y y Z j 14 15 Решение двойственной задачи симплекс- методом Пример 3. Решить двойственную задачу, построенную в примере 2, симплекс-методом. 4 , , 1 , 0 5 2 4 3 3 2 max 5 6 10 12 3 2 1 4 2 1 4 3 2 1 K = ≥ ⎩ ⎨ ⎧ ≤ − ≤ − + → − − + = j y y y y y y y y y y y Z j Приведение условия к каноническому виду Так как система ограничений состоит из неравенств, для приведения условия к каноническому виду нужно вве- сти в каждое неравенство балансовые переменные 5 4 , y y : 6 , , 1 , 0 5 2 4 3 3 2 6 3 2 1 5 4 2 1 K = ≥ ⎩ ⎨ ⎧ = + − = + − + j y y y y y y y y y j Матрица системы ограничений ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − − 5 1 0 0 1 2 4 3 0 1 1 0 3 2 содержит в себе единичную матрицу, следовательно, балан- совые переменные образуют естественный базис. Условие задачи в каноническом виде: 6 , , 1 , 0 5 2 4 3 3 2 0 5 6 10 12 6 3 2 1 5 4 2 1 4 3 2 1 K = ≥ ⎩ ⎨ ⎧ = + − = + − + = + + − − j y y y y y y y y y y y y y Z j Расширенная матрица канонической формы двойст- венной задачи: ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − 5 1 0 0 1 2 4 0 3 0 1 1 0 3 2 0 0 0 0 5 6 10 12 1 Ранг расширенной матрицы 3 = rang , следовательно, количество базисных переменных равно трем. Базисные переменные: 6 5 , , y y Z Свободные переменные: 4 3 2 1 , , , y y y y Шаг 1. Составление первой симплекс-таблицы В задаче с естественным базисом первая симплекс- таблица соответствует первому допустимому базисному решению. Симплекс-таблица 1 БП Z 1 y 2 y 3 y 4 y 5 y 6 y Реше- ние Отноше- ние Z 1 -12 -10 6 5 0 0 0 5 y 0 2 3 0 -1 1 0 3 3:2= 2 3 6 y 0 4 2 -1 0 0 1 5 5:4= 4 5 16 17 Комментарий к симплекс-таблице 1. Решение (допустимое базисное) в 6-мерном простран- стве Y =(0,0,0,0,3,5). Решение в 4-мерном (по количеству исходных пере- менных в условии двойственной задачи) пространстве Y =(0,0,0,0). Данная точка является угловой в многогранни- ке решений. Значение целевой функции в начальной точке Z (0,0,0,0)=0. Проверка критерия оптимальности: задача на макси- мизацию, в строке целевой функции имеются отрицатель- ные коэффициенты при свободных переменных 1 y и 2 y , следовательно, оптимальное решение не достигнуто. Необ- ходимо выбрать среди свободных включаемую в базис пе- ременную. Выбор включаемой в базис переменной: наибольший по модулю отрицательный коэффициент 12 1 − = b при пе- ременной 1 y Проверка критерия допустимости: все оценочные от- ношения конечные положительные, следовательно, возмо- жен выбор исключаемой из базиса переменной. Выбор исключаемой переменной: среди оценочных отношений минимальным является отношение, соответст- вующее переменной 6 y , которая и будет исключена из ба- зиса на этом шаге. Ведущим элементом при пересчете будет элемент, стоящий на пересечении ведущей строки, соответствующей исключаемой переменной 6 y , и ведущего столбца, соответ- ствующего включаемой переменной 1 y Пересчет таблицы в матричной записи. Элементы ведущей строки делятся на ведущий эле- мент: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − 4 5 4 1 0 0 4 1 2 1 1 0 3 0 1 1 0 3 2 0 0 0 0 5 6 10 12 1 Далее выполняются элементарные преобразования над строками матрицы, ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − ⋅ + − ⋅ + − ⋅ + − ⋅ + − − ⋅ − − ⋅ + − ⋅ + − ⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ − ⋅ + − ⋅ + − ⋅ + 4 5 4 1 0 0 4 1 2 1 1 0 ) 2 ( 4 5 3 ) 2 ( 4 1 0 ) 2 ( 0 1 ) 2 ( 0 1 ) 2 ( 4 1 0 ) 2 ( 2 1 3 ) 2 ( 1 2 ) 2 ( 0 0 12 4 5 0 12 4 1 0 12 0 0 12 0 5 12 4 1 6 12 2 1 10 12 1 12 12 0 1 в результате которых на месте ведущего столбца окажется столбец единичной матрицы: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − 4 5 4 1 0 0 4 1 2 1 1 0 2 1 2 1 1 1 2 1 2 0 0 15 3 0 5 3 4 0 1 Базисные переменные: 5 1 , , y y Z Свободные переменные: 6 4 3 2 , , , y y y y Шаг 2. Составление следующей симплекс-таблицы Новая таблица соответствует допустимому базисному решению. 18 19 Симплекс-таблица 2 БП Z 1 y 2 y 3 y 4 y 5 y 6 y Реше- ние Отноше- ние Z 1 0 -4 3 5 0 3 15 5 y 0 0 2 2 1 -1 1 2 1 − 2 1 2 1 :2= 4 1 1 y 0 1 2 1 4 1 − 0 0 4 1 4 5 4 5 : 2 1 = 2 5 Комментарий к симплекс-таблице 2. Решение (допустимое базисное) в 6-мерном простран- стве Y =( 4 5 ,0,0,0, 2 1 ,0). Решение в 4-мерном пространстве Y =( 4 5 ,0,0,0). Дан- ная точка является угловой в многограннике решений. Значение целевой функции в начальной точке Z ( 4 5 ,0,0,0)=15. Проверка критерия оптимальности: задача на макси- мизацию, в строке целевой функции имеется отрицательный коэффициент при свободной переменной 2 y , следователь- но, оптимальное решение не достигнуто. Необходимо вы- брать среди свободных включаемую в базис переменную. Выбор включаемой в базис переменной: единственный отрицательный коэффициент 4 2 − = b при переменной 2 y Проверка критерия допустимости: все оценочные от- ношения конечные положительные, следовательно, возмо- жен выбор исключаемой из базиса переменной. Выбор исключаемой переменной: среди оценочных отношений минимальным является отношение, соответст- вующее переменной 5 y , которая и будет исключена из ба- зиса на этом шаге. Ведущим элементом при пересчете будет элемент, стоящий на пересечении ведущей строки, соответствующей исключаемой переменной 5 y , и ведущего столбца, соответ- ствующего включаемой переменной 2 y Пересчет таблицы в матричной записи. Элементы ведущей строки делятся на ведущий эле- мент: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − 4 5 4 1 0 0 4 1 2 1 1 0 4 1 4 1 2 1 2 1 4 1 1 0 0 15 3 0 5 3 4 0 1 Далее выполняются элементарные преобразования над строками матрицы, ⎟⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − ⋅ + ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − ⋅ − ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − ⋅ + ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − ⋅ − ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − ⋅ + − ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − ⋅ + ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − ⋅ + ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − ⋅ + − − ⋅ + ⋅ − ⋅ + ⋅ − ⋅ + ⋅ + − ⋅ + ⋅ + 2 1 4 1 4 5 2 1 4 1 4 1 2 1 2 1 0 2 1 2 1 0 2 1 4 1 4 1 2 1 1 2 1 2 1 0 1 2 1 0 0 4 1 4 1 2 1 2 1 4 1 1 0 0 4 4 1 15 4 4 1 3 4 2 1 0 4 2 1 5 4 4 1 3 4 1 4 4 0 0 4 0 1 в результате которых на месте ведущего столбца окажется столбец единичной матрицы: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − 8 9 8 3 4 1 4 1 8 3 0 1 0 4 1 4 1 2 1 2 1 4 1 1 0 0 16 2 2 3 4 0 0 1 20 21 Базисные переменные: 2 1 , , y y Z Свободные переменные: 6 5 4 3 , , , y y y y Шаг 3. Составление следующей симплекс-таблицы Новая таблица соответствует допустимому базисному решению. Симплекс-таблица 3 БП Z 1 y 2 y 3 y 4 y 5 y 6 y Реше- ние Z 1 0 0 4 3 2 2 16 2 y 0 0 1 4 1 2 1 − 2 1 4 1 − 4 1 1 y 0 1 0 8 3 − 4 1 4 1 − 8 3 8 9 Комментарий к симплекс-таблице 3. Решение (допустимое базисное) в 6-мерном простран- стве Y =( 8 9 , 4 1 ,0,0,0,0). Решение в 4-мерном пространстве Y =( 8 9 , 4 1 ,0,0). Дан- ная точка является угловой в многограннике решений. Значение целевой функции в начальной точке Z ( 8 9 , 4 1 ,0,0)=16. Проверка критерия оптимальности: задача на макси- мизацию, в строке целевой функции все коэффициенты при свободных переменных положительны, следовательно, по- лучено оптимальное решение. Таким образом, решение Y =( 8 9 , 4 1 ,0,0), при котором целевая функция достигает своего максимального значения Z ( 8 9 , 4 1 ,0,0)=16, будет ответом в данной задаче. 22 23 Решение двойственной задачи с использованием теорем двойственности Пример 4. Решить двойственную задачу, построенную в примере 2, используя теоремы двойственности. Использование первой теоремы двойственности Информация для решения двойственной задачи с ис- пользованием теорем двойственности содержится в сим- плекс-таблице, полученной на последнем шаге решения ис- ходной задачи: БП F 1 x 2 x 3 x 4 x 5 x 6 x Реше- ние F 1 0 0 8 9 − 4 1 − 0 0 16 2 x 0 0 1 8 3 − 4 1 0 0 2 1 x 0 1 0 4 1 2 1 − 0 0 2 5 x 0 0 0 8 3 4 1 1 0 4 6 x 0 0 0 4 1 − 2 1 0 1 3 Таблица взята без столбцов, соответствующих искус- ственным переменным. Первая теорема двойственности. Если одна из двой- ственных задач имеет решение, то другая также имеет решение, причем оптимальные значения их целевых функций равны. Согласно первой теореме двойственности в данной за- даче 16 min max = = F Z Использование теоремы о соответствии переменных исходной и двойственной задач Таблица соответствия переменных: Переменные исходной задачи Основные Балансовые 1 x 2 x 3 x 4 x 5 x 6 x 5 y 6 y 1 y 2 y 3 y 4 y Балансовые Основные Переменные двойственной задачи Теорема. Строго положительным компонентам оп- тимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального реше- ния другой задачи. Теорема дает возможность установить, какие перемен- ные двойственной задачи принимают при оптимальном ре- шении нулевые значения. Таблица соответствия значений и знаков переменных: Компоненты оптимального решения исходной задачи 1 x =2 2 x =2 3 x =0 4 x =0 5 x =4 6 x =3 5 y =0 6 y =0 1 y >0 2 y >0 3 y =0 4 y =0 Знаки компонент оптимального решения двойственной за- дачи Использование второй теоремы двойственности Вторая теорема двойственности позволяет найти ос- тавшиеся ненулевые значения компонент оптимального ре- шения двойственной задачи. Вторая теорема двойственности. Компоненты оп- тимального решения одной из двойственных задач равны 24 25 абсолютным значениям коэффициентов при соответст- вующих переменных, находящихся в сроке целевой функции симплекс-таблицы, содержащей оптимальное решение дру- гой задачи. Согласно второй теореме двойственности таблицу со- ответствия значений и знаков переменных можно допол- нить значениями переменных 1 y и 2 y : Компоненты оптимального решения исходной задачи 1 x =2 2 x =2 3 x =0 4 x =0 5 x =4 6 x =3 5 y =0 6 y =0 1 y = 8 9 2 y = 4 1 3 y =0 4 y =0 Компоненты оптимального решения двойственной задачи Эта таблица и содержит окончательное решение двой- ственной задачи Y =( 8 9 , 4 1 ,0,0). Таким образом, первая теорема двойственности дает оптимальное значение целевой функции, а вторая теорема двойственности – значения всех компонент оптимального плана двойственной задачи. Эти значения, как видно, сов- падают со значениями, полученными с помощью симплекс- метода (см. пример 3). Восстановление последней симплекс-таблицы двойст- венной задачи Решение двойственной задачи уже получено, однако, его можно представить более наглядно, а именно в виде симплекс-таблицы, соответствующей оптимальному реше- нию двойственной задачи. Согласно теореме и таблице соответствия переменных, а также условию, в симплекс-таблице, содержащей опти- мальное решение двойственной задачи, базисными будут принимающие ненулевое значение переменные 1 y и 2 y Строки в последней симплекс-таблице исходной зада- чи удобнее переставить таким образом, чтобы они следова- ли в порядке возрастания номеров соответствующих пере- менных двойственной задачи, а строка целевой функции находилась внизу таблицы: БП F 1 x 2 x 3 x 4 x 5 x 6 x Реше- ние 3 y 5 x 0 0 0 8 3 4 1 1 0 4 4 y 6 x 0 0 0 4 1 − 2 1 0 1 3 5 y 1 x 0 1 0 4 1 2 1 − 0 0 2 6 y 2 x 0 0 1 8 3 − 4 1 0 0 2 F 1 0 0 8 9 − 4 1 − 0 0 16 Затем нужно подготовить бланк таблицы двойствен- ной задачи с таким же порядком расположения строк и с учетом количества ограничений и, следовательно, базисных переменных: БП Z 1 y 2 y 3 y 4 y 5 y 6 y Реше- ние 3 x 1 y 0 1 0 4 x 2 y 0 0 1 Z 1 0 0 Далее транспонируются «неединичные» столбцы из- мененной последней симплекс-таблицы исходной задачи: 26 27 БП Z 1 y 2 y 3 y 4 y 5 y 6 y Реше- ние 1 y 0 1 0 8 3 4 1 − 4 1 8 3 − 8 9 2 y 0 0 1 4 1 − 2 1 2 1 − 4 1 4 1 Z 1 0 0 4 3 2 2 16 Для окончательного получения последней симплекс- таблицы двойственной задачи остается умножить элементы столбцов 3 y , 4 y , 5 y и 6 y во всех строках, кроме строки целевой функции 2 , на (–1): БП Z 1 y 2 y 3 y 4 y 5 y 6 y Реше- ние 1 y 0 1 0 8 3 − 4 1 4 1 − 8 3 8 9 2 y 0 0 1 4 1 2 1 − 2 1 4 1 − 4 1 Z 1 0 0 4 3 2 2 16 В результате получилась такая же симплекс-таблица, как и после применения симплекс-метода в примере 3. 2 Коэффициенты в строке целевой функции умножаются на (–1) в двой- ственной задаче на минимизацию, в нашем примере двойственная зада- ча – на максимизацию. Типовой расчет «Основная задача линейного программирования» Задание для самостоятельной работы Дано условие задачи линейного программирования. Требуется: 1) Решить исходную задачу графическим методом. 2) Решить исходную задачу симплекс-методом, введя при необходимости искусственный базис. 3) Составить условие задачи, двойственной к данной. 4) Решить двойственную задачу симплекс-методом, введя при необходимости искусственный базис. 5) Решить двойственную задачу с использованием теорем двойственности. Индивидуальные условия (в 20 вариантах) 0 , 0 8 4 2 2 max 3 2 1 2 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ + ≤ + − ≥ + → − = x x x x x x x x x x F 1 Вариант 0 , 0 10 2 2 2 4 min 2 2 1 2 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ + ≤ + − ≥ + → − = x x x x x x x x x x F 2 Вариант 28 29 0 , 0 4 0 3 4 4 min 3 2 1 2 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≥ + ≥ − ≤ − → − = x x x x x x x x x x F 3 Вариант 0 , 0 10 2 2 2 4 max 2 2 1 2 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ + ≥ − ≥ + → − = x x x x x x x x x x F 4 Вариант 0 , 0 5 8 2 2 2 max 2 1 2 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ + ≥ + − ≤ + − → − = x x x x x x x x x x F 5 Вариант 0 , 0 3 3 3 2 2 3 max 2 1 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≥ + ≤ + − → + = x x x x x x x x x F 6 Вариант 0 , 0 4 0 2 min 3 2 1 2 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≤ − ≥ + → + = x x x x x x x x x F 7 Вариант 0 , 0 2 6 4 4 max 3 2 1 2 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≤ + ≥ + → + = x x x x x x x x x F 8 Вариант 0 , 0 4 7 3 min 2 1 2 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≤ + ≥ + → − = x x x x x x x x x F 9 Вариант 0 , 0 3 2 2 2 2 max 4 3 2 1 2 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≥ + ≥ − → − = x x x x x x x x x F 10 Вариант 0 , 0 21 3 12 2 5 max 3 2 1 2 1 2 1 2 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ + ≤ + ≤ → + = x x x x x x x x x F 11 Вариант 0 , 0 5 21 2 3 21 3 max 2 2 1 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≤ + ≤ + → + = x x x x x x x x x F 12 Вариант 0 , 0 18 3 8 6 max 4 2 1 2 1 2 1 2 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ + ≤ + ≤ → + = x x x x x x x x x F 13 Вариант 0 , 0 6 26 4 3 12 2 max 2 1 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≤ + ≤ + → + = x x x x x x x x x F 14 Вариант 30 31 0 , 0 18 3 21 2 3 6 max 2 2 1 2 1 2 1 2 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ + ≤ + ≤ → + = x x x x x x x x x F 15 Вариант 0 , 0 5 12 2 21 3 max 3 2 1 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≤ + ≤ + → + = x x x x x x x x x F 16 Вариант 0 , 0 21 3 21 3 2 5 max 2 2 1 2 1 2 1 2 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ + ≤ + ≤ → + = x x x x x x x x x F 17 Вариант 0 , 0 6 8 18 3 max 4 2 1 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≤ + ≤ + → + = x x x x x x x x x F 18 Вариант 0 , 0 12 2 26 3 4 6 max 2 1 2 1 2 1 2 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ + ≤ + ≤ → + = x x x x x x x x x F 19 Вариант 0 , 0 6 21 3 2 18 3 max 2 2 1 1 2 1 2 1 2 1 ≥ ≥ ⎪ ⎩ ⎪ ⎨ ⎧ ≤ ≤ + ≤ + → + = x x x x x x x x x F 20 Вариант Литература 1. Вентцель Е.С. Исследование операций. – М.: Совет- ское радио, 1972. 2. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в примерах и задачах. В 2-х ч. Ч.2: Учеб. посо- бие для втузов. – М.: Высшая школа, 1999. 3. Исследование операций в экономике / Н.Ш. Кремер, Б.А.Путко и др.; под ред. Н.Ш.Кремера. – М.: Банки и бир- жи, ЮНИТИ, 1997. 4. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Ма- тематическое программирование. – М.: Высшая школа, 1986. 5. Сборник задач по математике для втузов. Ч.4. Мето- ды оптимизации. Уравнения в частных производных. Инте- гральные уравнения / Вуколов Э.А., Ефимов А.В. и др.; под ред. А.В.Ефимова. – М.: Наука, 1990. 6. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике: Учебник: В 2-х ч. Ч.1. – М.: Фи- нансы и статистика, 1999. |