В частном случае, если µ §, то система (3.2) - (3.3) состоит только из линейных неравенств, а если µ §, то ЁC из линейных уравнений.
Если математическая модель задачи линейного программирования имеет вид:
µ § (3.5)
µ § (3.6)
µ §
µ § (3.7)
то говорят, что задача представлена в канонической форме.
Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот.
Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:
если в исходной задаче требуется определить максимум лилейной функции, то следует изменить знак и искать минимум этой функции;
если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
если среди ограничений имеются неравенства, то путем вверения дополнительных неотрицательных переменных они преобразуются в равенства;
если некоторая переменная не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменнымиµ §, где µ §- свободный индекс, µ §.
Каноническая задача линейного программирования имеет вид:
Z(X) = c1x1 + c2x2 + ЎK + cnxn Ўж (max) min (3.8)
µ § (3.9)
xjЎЭ0, j = 1,2,ЎK,n
Пример 3.1. Привести к канонической форме задачу линейного программирования:
µ §
Решение
Введем в каждое уравнение системы ограничений выравнивающие переменные x4, x5, x6. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений перевранные x4, x6 вводятся в левую часть со знаком «+», а во второе уравнение вводится со знаком «-».
µ §
Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:
µ §
В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть неотрицательными. Допустим, что
µ § где µ §
Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:
µ §
Рассмотрим процесс построения математических моделей задач линейного программирования на примере.
Пример 3.2. Использование мощностей оборудования.
Предприятие имеет m моделей машин различных мощностей. Задан план по времени и номенклатуре: Т ЎЄ время работы каждой машины; продукции j-го вида должно быть выпущено не менее Nj единиц.
Необходимо составить такой план работы оборудования, чтобы обеспечить минимальные затраты на производство, если известны производительность каждой i-й машины по выпуску j-го вида продукции µ § и стоимость единицы времени, затрачиваемого i-й машиной на выпуск j-го вида продукции µ §.
Другими словами, задача для предприятия состоит в следующем: требуется определить время работы i-й машины по выпуску j-го вида продукции µ §, обеспечивающее минимальные затраты на производство при соблюдении ограничений по общему времени работы машин Т и заданному количеству продукции Nj .
По условию задачи машины работают заданное время T, поэтому данное ограничение можно представить в следующем виде:
µ §
Ограничение по заданному количеству продукции выглядит следующим образом:
µ §
Задача решается на минимум затрат на производство:
µ §
Необходимо также учесть неотрицательность переменных µ §.
Задача поставлена так, чтобы израсходовать все отведенное время работы машины, т. е. обеспечить полную загрузку машины. При этом количество выпускаемой продукции каждого вида должно быть по крайней мере не менее Nj . Однако в некоторых случаях не допускается превышение плана по номенклатуре, тогда ограничения математической модели изменяются следующим образом:
µ §
µ §
µ §
µ §
3.1.2. Графическое решение задач линейного программирования
Графический способ решения задач линейного программирования целесообразно использовать для:
решения задач с двумя переменными, когда ограничения выражены неравенствами;
решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных.
То есть графический метод используется для решения задач с двумя переменными следующего вида:
Z(X) = c1x1 + c2x2 Ўж (min) max (3.10)
µ § (3.11)
X1 ЎЭ 0, X2 ЎЭ 0 (3.12)
Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми µ § µ §. В том случае, если система неравенств совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей ЎЄ выпуклое, то областью допустимых решений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств.
Областью допустимых решений системы неравенств может быть: выпуклый многоугольник; выпуклая многоугольная неограниченная область; пустая область; луч; отрезок; единственная точка.
Целевая функция определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение Z.
Для нахождения среди допустимых решений оптимального решения используют линии уровня и опорные прямые.
Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение линии уровня в общем случае имеет вид c1x1 + c2x2 = l, где l ЁC const. Все линии уровня параллельны между собой. Их нормаль µ §
Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с областью допустимых решений и по отношению к которой эта область находится в одной из полуплоскостей.
Вектор µ § с координатами с1 и с2, перпендикулярный к этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор ЁC направление убывания Z.
Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (3.11) - (3.12) и семейство параллельных прямых (3.10), то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z.
Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение.
Для определения данной вершины построим линию уровня µ § проходящую через начало координат и перпендикулярную вектору µ §, и будем передвигать ее в направлении вектора µ § до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений. Координаты указанной точки и определяют оптимальный план данной задачи.
Заканчивая рассмотрение геометрической интерпретации задачи (3.10) ЎЄ (3.12), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 3.1- 3.4. Рис. 3.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 3.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ.
На рис. 3.3 изображен случай, когда максимум недостижим, а на рис. 3.4 ЎЄ случай, когда система ограничений задачи несовместна. Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора µ §, а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения.
B
Zmin
Z=0
0
0
Z=0
C
X1
X1
µ §
