Формы записи задачи линейного уравнения

Формы записи задачи линейного программирования Формулы (1) и (2) описывают задачу линейного программирования в смешанной форме. Кроме того, существует несколько специальных форм записи таких задач. Задачу с неотрицательными переменными, все остальные ограничения которой имеют форму уравнений, будем называть канонической формой записи задачи линейного программирования: Любая задача в смешанной форме может быть приведена к канонической. Это делается путем введения неотрицательных дополнительных переменных, которые прибавляются к левой части неравенства либо вычитаются из нее (после этого знак неравенства заменяют на «равно»). Дополнительные переменные представляют собой разность между частями неравенства. Неотрицательности переменных добиваются заменой неограниченных по знаку переменных на разность двух неотрицательных. Подробнее этот материал рекомендуется изучить самостоятельно. Задачу с неотрицательными переменными, все остальные ограничения которой имеют форму неравенств одного знака (≤, если задача на максимум, и ≥, если на минимум), будем называть стандартной формой записи задачи линейного программирования. Любая задача в смешанной форме может быть приведена к любой из стандартных форм. Подробнее этот материал рекомендуется изучить самостоятельно. Если задача линейного программирования приведена к стандартной или канонической форме, ее удобно кратко записать в матричной форме. С этой целью вводятся следующие обозначения: С = (с1, с2, . . ., сj, . . . , сn) – вектор-строка коэффициентов целевой функции,  b1     ...   bi     ...     bm  B = - вектор-столбец свободных членов (правых частей ограничений),  x1     ...   xi     ...     xn  X= - вектор-столбец переменных,  a11   ...   a i1  ...  a  m1 A = ... a ... ... ... ... ... 1j a ij ... a mj ... ... ... ... ...   ...  a in  ...   a mn  a 1n - матрица коэффициентов в левых частях ограничений (каждая ее строка соответствует ограничению, а каждый столбец – переменной). Тогда задача линейного программирования в канонической форме запишется следующим образом: max CX AX = B   X≥0 Задача в стандартной форме будет иметь вид: max CX min CX AX ≤ B или AX ≥ B .    X≥0  X≥0 В самом деле, по правилам перемножения векторов СХ = с1х1 + с2х2 + … + сnхn = n ∑ c x . Это и есть линейное выражение в целевой функции. j=1 j j Умножая матрицу А размерности (m x n) на вектор Х (n x 1), получают столбец из m выражений, т.е. матрицу (m x 1). Каждое их этих 2 выражений получают умножением строки матрицы А на столбец Х, т.е. аi1х1 n + аi2х2 + … + аi1хn = ∑ a ij x j . Тогда АХ представляет собой столбец j=1 выражений в левых частях ограничений: АХ =  n   ∑ a1 j x j   j=1    ...  n .  ∑ a ij x j   j=1   ...   n   ∑ a mj x j   j=1  Благодаря тому, что во всех ограничениях стоит один и тот же знак, этот столбец можно сравнить со столбцом В. Тогда запись АХ = В представляет собой систему уравнений в ограничениях задачи в канонической форме (АХ ≥ В или АХ ≤ В – соответственно системы неравенств в задачах в стандартной форме). Отметим, что О в этих формулах представляет собой не одно число, а нулевой вектор (столбец из n нулей), поскольку каждая из n переменных сравнивается с нулем. Примеры форм записи ЗЛП будут приведены на практикуме. Геометрическая интерпретация и графический способ решения задачи линейного программирования Решим построенную задачу производственного планирования. Для этого введем на плоскости систему координат, обозначив горизонтальную ось х1, а вертикальную – х2 (рисунок 2). Это означает, что по горизонтали мы будем откладывать производство карамели «Снежинка» (т), а по вертикали – производство карамели «Яблочная» (т). Теперь любая точка на плоскости представляет собой план задачи. Выделим на рисунке 1 любые три точки. Например, точка с координатами (500; 1500) представляет собой следующий план: кондитерская фабрика выпускает 500 т карамели «Снежинка» и 1500 т 3 карамели «Яблочная». Точка (1500; 0) означает, что фабрика выпускает 1500 т «Снежинки», а «Яблочную» не выпускает вообще. Точка О (начало координат) означает, что фабрика вообще не выпускает карамель. И т.п. x2 1500 1000 500 O 500 1000 1500 x1 Рисунок 1 – Система координат Итак, вся плоскость – планы задачи. Выберем из них допустимые планы, т.е. такие, которые фабрика сможет осуществить. Поскольку неотрицательны, обе переменные будем в рассматривать этой задаче только должны быть неотрицательную координатную четверть (все, что левее оси ординат или ниже оси абсцисс, нас не интересует). Теперь рассмотрим остальные ограничения. Начнем с ограничения по запасам сахарного песка: 0,8х1 + 0,5х2 ≤ 800. Представим себе, что фабрика обязательно должна израсходовать все 800 т сахара (не больше и не меньше). Тогда ограничение примет вид уравнения: 0,8х1 + 0,5х2 = 800*. На плоскости * Вручную такую прямую можно построить по любым двум точкам. Здесь удобно взять в качестве таких точек корневые, т.е. пересечения этой прямой с осями координат. Для нахождения пересечения с осью ординат возьмем х1 = 0. Тогда 0,8*0 + 0,5х2 = 800; х2 = 800/0,5 = 1600. Для нахождения пересечения с осью абсцисс возьмем х2 = 0. Тогда 0,8х1 + 0,5*0 = 800; х1 = 800/0,8 = 1000. Таким образом, для построения этой прямой можно соединить точки (0; 1600) и (1000; 0). Если строить график по корневым точкам неудобно, можно взять любые другие точки (зафиксировать значение одной переменной равным любому числу и вычислить из уравнения значение другой). 4 это уравнение прямой. Построим эту прямую (рисунок 3). При подстановке координат любой точки на этой прямой в левую часть уравнения, получается ровно 800 (и все такие точки лежат на этой прямой). Значит, при осуществление любого плана выпуска карамели, лежащего на этой прямой, будет израсходовано ровно 800 т сахара. Теперь «вспомним» о том, что на самом деле это ограничение – неравенство (т.е. можно израсходовать меньше 800 т сахарного песка). Следовательно, нас интересует не сама прямая, а полуплоскость. Любая прямая делит плоскость на 2 полуплоскости. Чтобы выбрать из них нужную, возьмем в любой полуплоскости произвольную точку и подставим ее в неравенство. Если оно окажется истинным, то полуплоскость выбрана верно, а если нет, то надо выбрать другую. Здесь удобно взять точку (0; 0). При подстановке получаем 0,8*0 + 0,5*0 = 0 ≤ 800. Неравенство истинно (в самом деле, запасы сахара явно позволяют не выпускать карамель, - ведь если фабрика ее не выпускает, то и сахарный песок не расходуется вообще). Следовательно, допустимые планы лежат в той полуплоскости относительно прямой, в которой лежит (0; 0). Покажем эту полуплоскость маленькой стрелкой рядом с прямой (см. рисунок 2). x2 1500 сахар 1000 500 O 500 1000 1500 x1 Рисунок 2 – Ограничение по сахарному песку 5 Теперь известно, что допустимые планы задачи могут находиться только в треугольнике, заштрихованном на рисунке 3 (это пересечение, т.е. общая часть, неотрицательной координатной четверти и выбранной полуплоскости). x2 сахар 1500 1000 500 O 500 1000 1500 x1 Рисунок 3 – Ограничение по сахарному песку Однако в задаче есть еще два ограничения – по запасам патоки и фруктового пюре. Построим аналогично ограничение по запасам патоки: 0,2х1 + 0,4х2 ≤ 600 (рисунок 4). x2 (0; 1550) (1500; 1500) 1500 патока 1000 сахар 500 (1500; 500) O 500 1000 1500 x1 Рисунок 4 – Ограничения по сахарному песку и патоке В данном случае, добавив новое ограничение, мы «отсекли» часть треугольника. Теперь допустимые планы могут находиться только в 6 четырехугольнике, заштрихованном на рисунке 5. Только в этом четырехугольнике находятся все такие планы производства карамели, для осуществления которых фабрике хватит и сахарного песка, и патоки (и обе переменные при этом неотрицательны). Все остальные планы будут недопустимыми. Например, для осуществления плана (0; 1550) не хватит патоки (хотя сахарного песка хватит). Для осуществления плана (1500; 500) хватит сахарного песка, но не хватит патоки (он тоже недопустимый). Для плана (1500; 1500) не хватит ни одного из этих ресурсов. Три плана, рассмотренные в качестве примера, на рисунке 5 выделены. Осталось рассмотреть еще одно ограничение: по запасам фруктового пюре: 0,01х1 + 0,1х2 ≤ 120. После того, как оно изображено на графике, ОДП задачи примет вид четырехугольника, представленного на рисунке 5. x2 1500 фруктовое пюре 1000 сахар патока 500 O 500 1000 1500 x1 Рисунок 5 – ОДП задачи Теперь на графике отражены все ограничения. Каждому из них соответствует прямая и полуплоскость (в том числе и ограничениям неотрицательности: для ограничения х2 ≥ 0 это ось абсцисс, а для х1 ≥ 0 – ось ординат с соответствующими полуплоскостями сверху и справа от осей). 7 Итак, заштрихованный четырехугольник – допустимые планы, из которых следует выбрать оптимальный, т.е. тот, который даст наиболее высокую прибыль. Прибыль фабрики определяется по формуле 108х1 + 140х2. Зададимся некоторым фиксированным уровнем прибыли. Например, предположим, что нужно получить прибыль 100 000 ден.ед. Все планы производства, которые позволяют получить именно такую прибыль, лежат на прямой 108х1 + 140х2 =100000 (назовем эту прямую линией уровня). На рисунке 6 она показана пунктиром под номером 1. Все допустимые планы, которые дают прибыль 100 000 ден.ед., расположены на отрезке этой прямой, который является ее пересечением с ОДП (лежит в заштрихованном четырехугольнике). Если взять другой уровень прибыли, например, 110 000 ден.ед., то можно получить другую прямую, которая на графике пройдет параллельно первой (в уравнении прямой изменился свободный член, - следовательно, она подверглась параллельному переносу). Таким образом можно изобразить бесконечное множество линий уровня (на рисунке 6 четыре линии уровня показаны пунктиром). Все линии уровня будут параллельны друг другу и перпендикулярны градиенту целевой функции. Именно вектор-градиент показывает, в каком направлении растет уровень функции (в данном случае, уровень прибыли). Координаты градиента представляют собой частные производные функции в точке. Поскольку здесь целевая функция линейная, градиент в любой точке будет одним и тем же. В самом деле, частная производная функции (108х1 + 140х2) по х1 будет равна 108, а по х2 – 140. Таким образом, координаты градиента (108; 140). Изобразить такой вектор на плоскости можно различными способами. В геометрии координаты вектора определяются разностью между координатами его конца и начала. Поэтому можно соединить, например, точки (10; 10) и (118; 150); или точки (0;1000) и (108; 1140); или точки 8 (2,1; -5) и (110,1; 135) или т.п.; - координаты всех этих векторов будут (108; 140). Изобразить градиент можно бесконечным множеством способов. Однако удобнее всего с точки зрения вычислений взять в качестве начала этого вектора точку (0; 0), а в качестве конца (108; 140). В этой задаче нас будет интересовать только направление вектора, а не его длина. Вектор (108; 140) в масштабе построенного графика будет слишком маленьким, и графиком будет неудобно пользоваться. Поэтому изобразим более длинный вектор, умножив обе координаты на одно и то же число (направление вектора при этом не меняется). Например, умножим их на 10. После этого изобразим на рисунке 6 направление градиента целевой функции задачи в виде вектора (1080; 1400). Для этого соединим начало координат с точкой (1080; 1400) (хотя можно было бы построить этот вектор и любым другим способом). x2 1500 2 3 4 направление градиента (1080; 1400) фруктовое пюре 1000 1 500 патока сахар линии уровня O 500 1000 1500 x1 Рисунок 6 – Линии уровня и направление градиента целевой функции Чтобы еще раз подчеркнуть, что вектор, изображенный на рисунке 6, представляет собой своего рода научную абстракцию, различные другие способы изобразить направление градиента показаны на рисунке 7. 9 x2 1500 фруктовое пюре 1000 сахар патока 500 O 500 1000 1500 x1 Рисунок 7 – Разные способы изобразить направление градиента Направление градиента на рисунке 6 показывает, что линия уровня под номером 3 соответствует более высокому уровню прибыли, чем под номером 2, а уровень 1 - еще ниже. Из тех линий уровня, которые изображены на рисунке 7, линии под номером 4 соответствует наиболее высокая прибыль. Однако, такую высокую прибыль невозможно получить, так как линия 4 нигде не пересекает ОДП (нет допустимых планов, дающих такой уровень прибыли). Поэтому, чтобы найти оптимальный план, мы зрительно «сдвигаем» линию уровня в направлении градиента, но не до бесконечности, а до так называемого крайнего положения. Это такое положение, в котором она еще пересекает ОДП, но если сдвинуть ее чуть дальше, то перестанет ее пересекать (рисунок 8). Крайнее положение линии уровня соответствует самому высокому уровню прибыли, который только можно получить. Как получить такой уровень прибыли? Нужно найти тот допустимый план производства, который его дает. На графике в этой задаче такой план – единственный. Это точка пересечения ОДП и крайнего положения линии уровня. На рисунке 8 она обозначена Х* и представляет собой оптимальный план задачи. 10 На графике видно, что Х* – точка пересечения прямых, которые соответствуют ограничениям по запасам фруктового пюре и сахарного песка. Следовательно, чтобы найти ее, необходимо решить систему уравнений: 0,8х1 + 0,5х2 = 800 0,01х1 + 0,1х2 =120 Отсюда х1 = 266 2/3, х2 =1173 1/3. x2 1500 Х* фруктовое пюре 1000 патока сахар 500 крайнее положение линии уровня O 500 1000 1500 x1 Рисунок 8 – Крайнее положение линии уровня и оптимальный план Х* Теперь найдем оптимум задачи, т.е. оптимальную (максимальную) величину прибыли. Для этого подставим найденный план Х* = = (266 2/3; 1173 1/3) в целевую функцию задачи: 108х1 + 140х2 =108*266 2/3 + + 140*1173 1/3 = 193066 2/3. Ответ задачи: кондитерской фабрике следует выпускать 266 2/3 т карамели «Снежинка» и 1173 1/3 т карамели «Яблочная». При этом ее прибыль составит 193067 ден.ед. Кроме того, можно сделать из решения задачи некоторые дополнительные выводы. А именно, так как оптимальный план лежит на прямых, которые соответствуют ограничениям по сахарному песку и 11 фруктовому пюре, можно утверждать, что эти ресурсы будут израсходованы полностью (соответственно 800 и 120 т). А вот патока останется в избытке. Если нужно рассчитать неизрасходованный остаток патоки, достаточно подставить оптимальный план в левую часть второго ограничения и определить разность между правой и левой частями. В следующей лекции мы рассмотрим общетеоретические основы решения таких задач. 12