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

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

Для восстановления математической модели ЗЛП необходимо выполнить следующие этапы:

1. Ввести переменные задачи линейного программирования в соответствии с размерностью пространства.

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

3. Построить уравнения прямых, соответствующих сторонам многоугольника, определить знаки неравенств, соответствующих искомым полуплоскостям.

4. Используя заданный градиент, построить целевую функцию ЗЛП.

Пример восстановления математической модели ЗЛП

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

														max (min)
0	0	0	2	12	11	13	8	3	6	14	0	7	7	mах

Решение. Данная ЗЛП имеем 2 переменные, т.к. каждая из точек задана двумя координатами. Обозначим первую переменную , а вторую – .

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

Построение точек , и единственный правильный способ их соединения представлены на рис.1.

Рис.1. Многоугольник, составляющий множество планов ЗЛП

На рис.2 приведен пример ошибочного соединения вершин множества (полученное множество не является выпуклым).

А₅

А₃

А₂

А₄

А₁

Рис.2. Пример ошибочного соединения вершин в порядке нумерации

После определения порядка следования вершин (в данном случае получили многоугольник , ), необходимо построить уравнения прямых, отрезки которых являются сторонами многоугольника. Так как уравнение прямой можно определить с помощью координат двух точек (х₁,y₁), (x₂,y₂), принадлежащей этой прямой, составим уравнения, используя вершины многоугольника, в соответствии с уравнением прямой, проходящей через точки: . В данном случае получим уравнение сторон:

1) сторона : точки О(0;0) и А₁(0;2), тогда , или .

2) сторона : точки А₁(0;2) и А₄(3;6), тогда , или .

3) сторона : точки А₄(3;6) и А₂(12;11), тогда , или .

4) сторона : точки А₂(12;11) и А₃(13;8), тогда , или .

5) сторона : точки А₃(13;8) и А₅(14;0), тогда , или .

6) сторона : точки А₅(14;0) и О(0;0), тогда , или .

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

Например, возьмем точку (1,1), которая является внутренней для многоугольника , (рис. 1). Тогда:

1) для прямой : 1≥0, т.е. ;

2) для прямой : 4-3+6=7≥0, т.е. .

3) для прямой : 5-9+39=35≥0, т.е. .

4) для прямой : -3-1+47=43≥0, т.е. .

5) для прямой : -8-1+112=103≥0, т.е. .

6) для прямой : 1≥0, т.е. .

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

Перенесем вправо свободные члены, чтобы привести задачу к скалярной форме:

Для определения целевой функции воспользуемся вектором-градиентом . Как известно, градиент имеет вид , а так как исходная задача – задача линейного программирования, то коэффициенты вектора-градиента будут постоянными и соответствовать коэффициентам при соответствующих переменных, т.е. в данном случае . Целью решения, согласно условию задачи, является поиск максимума. Тогда ЗЛП примет вид:

,