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

x6 21 3x1,

F 2x1 3 5 x5 ,

или

Здесь вновь в скобках записано базисное решение. Линейная функция возросла на величину ∆F = 3х2б = 3∙5 = 15 единиц. Однако решение не является оптимальным, так как линейную функцию можно увеличить на величину ∆F = 2х1б, если х1 перевести из свободной переменной (где в базисном решении она принимает значение равное нулю) в базисные. Система уравнений (18) определяет наибольшее возможное значение для х1: х1 = min{∞; 3/1; 11/2; ∞} = 3. Второе уравнение является разрешающим, переменная х3 переходит в свободные, при этом ∆F = 2х1б = 2∙3 = 6.

Далее. Базисные переменные: х1, х2, х4, х6. Свободные переменные: х3, х5. Выражаем новые базисные переменные через новые свободные переменные, начиная с разрешающего уравнения (его используем при записи выражения для х1). После преобразований получаем:

Третье допустимое базисное решение (3; 5; 0; 5; 0; 12) тоже не является оптимальным, поскольку при свободной переменной х5 в выражении линейной функции (19) содержится положительный коэффициент. Переводим х5 в базисные переменные. При определении наибольшего возможного значения для х5

11

следует обратить внимание на первое уравнение в системе (19), которое не дает ограничений на рост х5, так как свободный член и коэффициент при х5 имеют одинаковые знаки. Поэтому х5 = min{∞; 5; 1; 12/9} = 1. Третье уравнение является разрешающим, и переменная х4 переходит в свободные; ∆F = 3х5б = 3∙1 = 3.

Базисные переменные: х1, х2, х5, х6. Свободные переменные: х3, х4. После преобразований запишем:

Коэффициенты перед свободными переменными в правой части линейной функции (19) отрицательные, поэтому больше увеличивать значение функции невозможно. Максимальное значение функции F = 24 достигается в допустимом базисном решении (6; 4; 0; 0; 1; 3) соответствующем угловой точке многогранника допустимых решений.

Р е ш е н и е. Введем дополнительные неотрицательные переменные у5 и у6 со знаком «минус», так как неравенства имеют вид «≥». Получим систему уравнений:

Если в начале в качестве базисных взять дополнительные переменные, то получим недопустимое базисное решение: (0; 0; 0; 0; -2; -3). В данном случае в

12

качестве базисных удобно взять переменные у3 и у4. Каждая из этих переменных входит только в одно уравнение и коэффициенты перед ними положительны, поэтому в качестве первоначального получим допустимое базисное решение.

Базисные переменные: у3, у4. Свободные переменные: у1, у2, у5, у6. Выражаем базисные переменные через свободные:

В правой части линейной функции (24) перед свободными переменными есть отрицательные коэффициенты, следовательно, значение функции Z можно уменьшить на величину равную ∆Z = – 4у1б, если у1 перевести из свободной переменной в базисную. Наибольшее возможное значение: у1 = min{1; 2} = 1, т.е. первое уравнение является разрешающим; у3 становится свободной перемен-

ной, ∆Z = – 4∙1 = – 4.

Далее. Базисные переменные: у1, у4. Свободные переменные: у2, у3, у5, у6. После преобразований:

Переменную у2 переводим в базисные, так как коэффициент перед ней в линейной функции (25) отрицательный. Наибольшее возможное значение у2 = min{3; 3/5} = 3/5, второе уравнение разрешающее у4 переходит в свободные пе-

ременные; ∆Z = (– 5/3)∙3/5 = – 1.

Базисные переменные: у1, у2. Свободные переменные: у3, у4, у5, у6. Получим после преобразований:

13

Решение (26) оптимальное, поскольку в выражении для Z нет свободных переменных у3, у4, у5, у6 с отрицательными коэффициентами.

2. Двойственные задачи

Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряженной по отношению к исходной. Двойственная задача к двойственной задаче образует исходную задачу линейного программирования.

В общем случае задачу линейного программирования можно записать в стандартной форме (4):

Если воспользоваться матричной формой записи задачи (27), то это выражение можно записать в виде:

где полностью опущены переменные величины, неравенства заменены вертикальной линией и линейная (целевая) функция записана внизу.

Транспонируем матрицу (28) и элемент F заменим на Z, получим:

14

Заменяя неотрицательные переменные х на неотрицательные переменные у, неравенства вида «≤» (27) на неравенства противоположного смысла «≥», восстановим по матрице (29) двойственную задачу к задаче линейного программирования (27):

Для дальнейшего изучения задачи линейного программирования и двойственной к ней задачи, с помощью символов суммирования, запишем их в иной форме. Получим задачу линейного программирования:

2.1. Основное неравенство двойственности

Каждое неравенство в системе (31) умножим на соответствующее уi, и сложим все эти неравенства:

15

Аналогично, каждое неравенство в системе (32) умножим на соответствующее хj и сложим все эти неравенства. Получим:

Левые части неравенств (33) и (34) одинаковые по величине. Обозначим эту величину символом А. Можем записать:

Мы получили теорему, в которой х и у представляют собой допустимые векторы.

Теорема 5. Для всех допустимых значений переменных линейная функция не превышает линейной функции двойственной задачи, т.е. справедливо неравенство: F(x) ≤ Z(y).

2.2.Первая теорема двойственности

Взадаче (27) отыскивается максимум функции F. Предположим, что допустимый вектор х представляет собой оптимальный вектор, т.е. такой при котором достигается максимальное значение линейной функции. Это значит, что для любых допустимых х справедливо неравенство F(х ) ≥ F(х). Аналогично, для двойственной задачи. Если у – допустимое оптимальное решение, то для любого допустимого вектора у справедливо неравенство Z(y ) ≤ Z(у).

Теорема 6. Если х и у допустимые решения взаимно двойственных задач, для которых выполняется равенство

Действительно, пусть х любое допустимое решение исходной задачи (27), тогда, в силу основного неравенства двойственности (37), можем записать F(х)

16

≤ Z(y ) = F(х ). Отсюда следует неравенство F(х) ≤ F(х ), доказывающее оптимальность решения х . Аналогично показывается оптимальность решения y .

Первая (основная) теорема двойственности. 7. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны: F(х ) = Z(y ).

Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы.

Рассмотренные выше примеры (13) и (21) подтверждают первое предложение данной теоремы. Задачи в этих примерах взаимно двойственные.

2.3. Вторая теорема двойственности.

Для рассмотрения второй теоремы двойственности, взаимно двойственные задачи (31) и (32) приведем к канонической форме, превратив системы неравенств в системы уравнений дополнением неотрицательных переменных, получим исходную каноническую задачу:

i 1

yi 0, i 1, m, ym j 0, j 1, n.

Каждое уравнение в системе (38) умножим на соответствующее уi, и сложим все эти уравнения:

Аналогично, каждое уравнение в системе (39) умножим на соответствующее хj и сложим все эти уравнения, получим:

17

Равенства (40) и (41) справедливы для всех допустимых значений переменных. Оптимальные решения являются допустимыми переменными, следовательно, данные равенства справедливы для оптимальных решений. Первые слагаемые в равенствах (40) и (41) одинаковые по величине числа. Правые части равенств (40) и (41) при оптимальных решениях, согласно первой теореме двойственности, равны. Равенство (41) умножим на минус единицу и сложим его с равенством (40), учитывая сказанное, получим:

Все множители и все слагаемые в равенстве (42) неотрицательные числа. Для того чтобы сумма неотрицательных слагаемых была равна нулю необходимо потребовать равенства нулю каждого слагаемого. Получаем теорему.

Теорема 8. Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i = 1, 2,

…, m и j = 1, 2, …, n:

Переменные, являющиеся сомножителями в каждом слагаемом в равенстве (42) и для каждой пары, которых рассматриваются условия (43), называются соответствующими переменными.

Вторая теорема двойственности. 9. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции исходной задачи, выраженной через свободные переменные её оптимального решения.

Для взаимно двойственных задач (13) и (21, 22) запишем соответствующие переменные:

18

и выпишем их линейные функции при оптимальных решениях. Получим:

Сравнивая равенства (45) и (46) обнаруживаем справедливость последней теоремы.

2.4. Третья теорема двойственности

Предположим, что двойственная задача имеет геометрическое решение, соответствующее рис. 2. Линейная функции при оптимальных решениях равна:

Изменяя величины b1 и b2, мы можем менять значение линейной функции. При этом изменяется наклон линии уровня. Изменение этого наклона должно быть ограниченным. Если линия уровня коснется другой угловой точки, то оптимальное решение мо-

жет уйти из данной точки (см. рис. 2). Иными словами возможно в некоторых пределах изменять величины b1 и b2 не изменяя оптимального решения, но изменяя значение линейной функции (47). В выражении (47) функцию Z можно заменить на функцию F , согласно, с первой теоремой двойственности. Тогда значение «игреков» в выражении (47) (и в более общем выражении, когда количество слагаемых больше) будет равно частным производным по соответствующим величинам b. Справедлива теорема:

Третья теорема двойственности. 10. Компоненты оптимального решения двойственной задачи равны значениям частных производных линейной функции F по соответствующим аргументам, т.е.

Компонента оптимального решения двойственной задачи показывает величину изменения линейной функции F с изменением соответствующего значения b на одну единицу и называется объективно обусловленной оценкой этой величины b.

П р и м е р 4. Для изготовления четырех видов продукции используется три вида сырья. Запасы, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице.

При решении задачи на максимум общей стоимости выпускаемой продукции были получены следующие результаты: х 1 = 0, х 2= 0, х 3= 400, х 4 = 550. Требуется: 1) Сформулировать прямую оптимизационную задачу на максимум общей стоимости продукции, указать оптимальную производственную программу (пояснить, почему х 1 и х 2 не вошли в оптимальный план); 2) Сформулировать двойственную задачу и найти ее оптимальный план; 3) Проанализировать использование ресурсов в оптимальном плане; 4) Как изменится общая стоимость выпускаемой продукции и план ее выпуска, если запас сырья первого вида увеличить на 100 кг, а второго — уменьшить на 150кг? 5) Целесообразно ли выпускать изделие "Д" ценой 10 единиц, если нормы затрат сырья 2, 4 и 3 кг?

Р е ш е н и е. Сформулируем прямую оптимизационную задачу на максимум общей стоимости продукции. Обозначим х1, х2, х3, х4 количество единиц выпускаемой продукции вида А, Б, В, Г соответственно. Если нормы расхода сырья на одну единицу продукции умножить на количество единиц выпускаемой продукции и сложить по всем видам продукции, то получим расходы сырья по производственной программе, которые не должны превышать запасов соответствующего сырья, т.е. получим систему неравенств:

20