IV. Методические указания к решению задач

1. Графический метод решения задач линейного программирования

Общей задачей линейного программирования ОЗЛП называется задача, которая состоит в определении максимального (минимального) значения линейной целевой функции:

при условиях-ограничениях

где a_ij, b_i, c_j -заданные постоянные величины и k≤m.

Стандартной (или симметричной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 1 и 3, где k=m и l=n.

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 2 и 4, где k=0 и l=n.

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

План _|при котором целевая функция задачи принимает максимальное (минимальное значение, называется оптимальным.

В случае, когда требуется найти минимум функции =с₁х₁+с₂х₂+...c_nх_n, можно перейти к нахождению максимума функции F(X)=F(X)=–c₁x₁-c₂x₂-...-c_nx_n. так как min F(X)= –max F(X).

Ограничение-неравенство исходной задачи линейного программирования, имеющее вид «≤» преобразуется в ограничение- равенство добавлением к левой части дополнительных неотрицательной переменной, а ограничение-неравенство вида «≥» - в ограничение-равенство вычитанием из левой части дополнительной не отрицательной переменной.

Допустим ограничения задачи отображают наличие производственных ресурсов, тогда числовое значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса.

План называется опорный планом основной задачи линейного программирована, если система векторов, входящих в разложение с положительными коэффициентами х_j линейно независима.

Так как векторы А_j являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать m.

Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае - план вырожденный.

Свойства основной задачи линейного программирования связаны со свойствами выпуклых множеств.

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

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

Угловыми точками выпуклого множества называются точки, не являющиеся выпуклой комбинацией двух произвольных точек множества. Например, угловыми точками треугольника являются его вершины, круга - точки окружности, которые его ограничивают.

Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто).Непустое множество планов называется многогранником решений, а всякая угловая точка многогранника решений - вершиной.

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

Непустое множество планов основной задачи линейного программирования образует выпуклый многогранник, каждая вершина которого определяет опорный план. Для одного из опорных планов (т.е. в одной из вершин многогранника решений) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов).

Вершину многогранника решений, в которой целевая функция принимает максимальное значение, можно найти достаточно просто,:ли задача в стандартной форме содержит не более двух переменных:

F(X) = c_lx₁+c₂x₂

при условиях

Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость допустимых значений переменных соответственно с граничными прямыми

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

Решение задачи линейного программирования графическим методом включает следующие этапы.

1. На плоскости Х₁ОХ₂ строят прямые, уравнения которые получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Строят многоугольник решений.

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

5. Строят начальную прямую с₁х₁+с₂х₂=0 и передвигают ее в направлении вектора до крайней угловой точки многоугольника решений. В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если начальная прямая сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов .

6. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке

Минимальное значение линейной функции цели находится путем передвижения начальной прямой с₁х₁+с₂х₂=0 в направлении, противоположном вектору .

Пример

Найти максимум и минимум линейной функции:

при условиях:

Решение:

Построим на плоскости Х₁ОХ₂ многоугольник решений рис 1. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств

Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение

Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение

Многоугольником решений задачи является пятиугольник АВСДЕ, координаты точек которого удовлетворяют условию неотрицательности и неравенствам системы ограничений задачи. Для нахождения точек экстремума построим начальную прямую =0=2х₁+3х₂ и вектор (2,3). Передвигая прямую =0 параллельно самой себе в направлении вектора .

Рис. 1. Построение многоугольника решений

Найдем точку С, в которой начальная прямая принимает положение опорной прямой. Следовательно, в точке С целевая функция принимает максимальное значение, так как точка С получена в результате пересечения прямых 1 и 2, то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим: х₁=3,4; х₂=4,2; =2·3,4+3·4,2=6,8+12,6=19,4.

Для нахождения минимального значения целевой функции, задачи перемещаем начальную прямую в направлении, противоположном вектору . Начальная прямая займет положение опорной прямой в вершине Е. Целевая функция принимает минимальное значение в угловой точке Е, где х₁=1, x₂=0, a =1·2+ 3·0=2.

Найдем координаты угловых точек В, Д и А. Для этого решим следующие системы уравнений.

В результате получим координаты точек В(0;2,5), Д(2,0) и А(0,1).

Вычислим значения целевой функции во всех угловых точках многоугольника решений АВСДЕ:

F(0,1) =2·0+3·1=3

В(0;2.5) =2·0 + 3·2,5 = 7,5

С(3,4;4.2) =2·3,4 + 3·4,2 = 19,4(mах)

Д(2.0) =2·2 + 3·0 = 4.

Е(1.0) =2·1+3·0=2 (min)

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Сформулируйте общую задачу линейного программирования.

2 Дайте определение невырожденного и вырожденного опорного плана, оптимального плана.

3. Какое множество называется выпуклым?

4. Какая точка выпуклого множества называется угловой?

5. Дайте геометрическую интерпретацию задачи линейного программирования.

6. В какой точке многогранника решений целевая функция задачи линейного программирования достигает оптимального значения?

7. Какие задачи линейного программирования можно решить графическим методом?

8. Назовите особые случаи при решении задачи линейного программирования графическим методом.