Раздел II. Задачи математического программирования

В этом разделе показано применение различных методов решения задач математического программирования (задач линейного программирования, транспортных задач). Для каждого метода приводится подробное решение примеров, аналогичных 2-му, 3-му и 4-му заданиям контрольной работы.

Литература: [1,8-11,16,18]

§1 Основные сведения из теории линейного программирования.

Задача математического программирования (3)(или (4))называется задачей линейного программирования (ЛП), если целевая функцияfесть линейная функция, а множество допустимых решений Х задается с помощью линейных неравенств или линейных уравнений:

max f(x)=c₁x₁+c₂x₂+…+c_nx_n (1)

при ограничениях

a₁₁x₁+a₁₂x₂+…+a_1nx_n≤b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n≤b₂ (2)

…………………………

a_k1x₁+a_k2x₂+…+a_knx_n≤b_k

x₁≥0,…, x_n≥0 (3)

(1)-(3) -это стандартная постановка задачи ЛП (в общем случае в ограничениях (2) могут быть различные соотношения вида “≥”, “≤”, “=”).Здесьc₁,…,c_n - коэффициенты при целевой функции,a₁₁,...,a_nn -коэффициенты при ограничениях,b₁,…,b_k- свободные члены при ограничениях. Все они являются известными числами (заданы); Неизвестными являются переменныеx₁,…,x_n

В задачах (1) - (3)требуется найти такие значения переменныхx₁*,...,x_n* (точку максимума), чтобы:

1)Эти переменные удовлетворяли воем ограничениям (2)и (3)(условие допустимости);

2)В точке х* = (х₁*,...,x_n* )целевая функцияfпринимала максимальное значениеf(x*) (условие оптимальности).

Аналогично ставится задача на минимум.

Свойства задач линейного программирования

1.Допустимое множество задачи ЛП либо пусто, либо является выпуклым многогранником вRⁿ(как пересечение полупространств, описываемых неравенствами (2)-(3)). Оно может быть кfк ограниченным, так и неограниченным; в любом случае это замкнутый многогранник.

2.Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации - ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение.

3.Оптимальные решения задачи ЛП (если они существуют) всегда находятся на границе допустимого множества. Точнее, если существует единственное оптимальное решение, то им является какая-либо вершина многогранника допустимых решений; если две или несколько вершин являются оптимальными решениями, то любая их выпуклая комбинация также является оптимальным решением (т.е. существует бесконечное множество точек максимума или минимума).

Методами решения задач ЛП являются: графический метод (в случае двух переменных), симплекс-метод или его разновидности (в общем случае).

§2. Решение задачи лп графическим методом :

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

max f(x) = x₁- x₂

при ограничениях

(1) 3х₁+2х₂≤14,

(2) x₁– 4x₂≤ 0,

(3) 3x₁– x₂≥ 0,

(4) –x₁+ x₂≤ 2

(5) x₁≥ 0,

(6) x₂≥ 0.

Решение. На плоскости R²построим допустимое множество, описываемое шестью неравенствами. Это будет пересечение шести полуплоскостей (каждое неравенство-ограничение задает на R²полуплоскость). Например, первую полуплоскость 3x₁+2х₂≤14 строим так. Проводим прямую 3x₁+2х₂=14, которая является границей этой полуплоскости. Чтобы определить, какую из полуплоскостей, лежащих по обе стороны от прямой 3x₁+2х₂=14, описывает неравенство 3x₁+2х₂≤14, достаточно поставить в это неравенство координаты начала координат, т.е. (0,0). Если неравенство выполняется, то берем ту полуплоскость, которая содержит начало координат, если не выполняется, то берем полуплоскость, не содержащую начала координат. В нашем случае 3*0 + 2*0≤14. На рис. 1в кружочках написаны номера линий (границ полуплоскостей), а полуплоскости обозначены стрелками. В результате пересечения построенных шести полуплоскостей получаем многогранник ОАВС. который и является допус­тимым множеством нашей задачи. Можно проверить, что любая точка этого многогранника удовлетворяет всем шести неравенствам, а для любой точки вне этого многогранника хотя бы одно неравенство из шести будет нарушено.

Таким образом, геометрически наша задача свелась к тому, чтобы в пределах многогранника ОАВС найти точку х* =(x₁*,x₂*). в которой целевая функцийf(x) =x₁-x₂получит максимальное значение.

Благодаря свойству 3(см. выше) мы заранее знаем, что точкой максимума нашей целевой функции является одна или некоторые из вершин О,А,В или С.

Для того, чтобы определить эту вершину, проведем какую-либо линию уровня целевой функции, т.е. проведем прямую f(x)=с₁, где с-const. Для простоты возьмем с=0,тогда линия уровня есть x₁-x₂=0.Увеличивая правую часть этого уравнения (например,x₁-x₂=1, x₁-x₂=3и т.д.), мы обнаружим параллельное смещение линии уровня вниз, причем, чем больше правая часть, тем дальше. Если же уменьшим правую часть (например, x₁-x₂=-1,x₁-x₂=-2и т.д.), то наблюдаем смещение вверх.

Отсюда понятно, что, смещая линию уровня в сторону возрастания целевой функции, мы найдем ту вершину многогранника ОАВС, которая соответствует точке максимума. Как видно из рисунка 1,это есть точка С.

Чтобы сразу определить направление возрастания функции t, вычисляют ее градиентf. Для линейной функции градиент всегда равен вектору, составленному из коэффициентов этой функции.

Для нашей целевой функции f(x)= x₁-x₂градиент f =(1,-1) (см. рис, 1). Известно, что градиент перпендикулярен линии уровня и показывает направление возрастания функции, а антиградиент, т.е. вектор -fпоказывает направление убывания функции.

Итак, "двигая" линию уровня x₁-x₂=0в сторону вектора f,находим точку максимума С.

Координаты точки С найдем решая совместно уравнения линий 1и 2, пересекающихся в точке С:

3x1+2x2=14

x1-4x2=0

Ответ: х*=(4,1) -точка максимума,

f(x*) = 3 -максимальное значение целевой функции.

Отсюда получаем алгоритм графического метода:

1)построить на плоскости допустимое множество,

2)построитьлинию уровня целевой функции,

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

4)найтии вычислить координаты точки максимума или минимум,

5)вычислить значение целевой функции в найденной точке.

Пример 2.(Случай бесконечного множества оптимальных решений):

minf(x)=--x1-2x2

при ограничениях

x₁+2x₂≤7

2x₁+x₂≤8

x₂≤3

x₁,x₂≥0

Как видно из рис. 2,наиболее удаленным в сторону антиградиента -f=(1,2)местом касания линии уровняf(x)=с с допустимым множествомOABCDявляется грань ВС (т.е. выпуклая оболочка вершинB=(l, 3)и С=(3,2)).Поэтому любая точка грани ВС является точкой минимума целевой функции.

Ответ: х*=(1,3)+(1-)(3,2)=(3-2,2+) для любого[0, 1] - точка минимума,

f(x*)=-7 - минимальное значение целевой функции.

Пример 3.(Случай отсутствия оптимального решения ввиду неограниченности целевой функции на допустимом множестве):

minf(x) == -x₁-2x₂

при ограничениях .

x₁+x₂1

2x₁-x₂-1

x₁-2x₂≤0

x₁,x₂≥0

Допустимое множество этой задачи представляет собой неограниченный многогранник (рис. 3).

При параллельном переносе линии уровня f(x)=с вдоль антиградиента -f=(1,2) она всегда пересекает допустимое множество, т.е. нет "наиболее удаленной точки касания", а целевая функция неограниченно убывает.

Ответ:Точки минимума нет; целевая функция неограниченна снизу.

Пример 4.(Случай отсутствия оптимального решения ввиду пустоты допустимого множества):

maxf(x)=x₁+x₂

при ограничениях

-x₁+x₂≤-1

-x₁-x₂≤-1

x₁,x₂≥0

Как показано на рис, 4,полуплоскости, образованные первыми двумя неравенствами, не пересекаются (система не совместна); Поэтому нет ни одной допустимой точки.

Графический метод применяется и в том случае, когда в задаче ЛП число линейно независимых ограничений-неравенств (каноническая форма) ровно на два меньше числа переменных. Об этом подробно можно почитать, например, в [8, стр. 49].