Математические расчеты СЭП

 Теоретический вопрос.

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

Решение

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

Задача ЛП с двумя переменными может быть записана следующим образом:

ставится задача оптимизации целевой функции Z = c1 x1 + c2 x2 ; ограничения могут быть записаны так:

[pic 1]

x1 ≥ 0; x2 ≥ 0 ;

или  более коротко

aj1 x1 + aj2 x2≥ bj,  j= 1, …, n;  xi ≥ 0, i= 1,2.

Алгоритм графического метода решения задачи следующий:

1. Найти область допустимых решений системы ограничений задачи.
2. Построить вектор OC, определяющий направление роста функции Координатами точки C являются коэффициенты целевой функции.
3. Провести линию уровня, перпендикулярную вектору OC.
4. Перемещая линию уровня параллельно самой себе, можно в области допустимых решений найти максимум целевой функции при движении по вектору OC или минимум при движении против вектора OC. Движение линии уровня необходимо продолжать до тех пор, пока не окажется единственная точка при ее пересечении с областью допустимых решений. Эта точка и будет точкой экстремума. Если окажется, что линия уровня параллельна одной из сторон области допустимых решений, то задача имеет множество решений.
5. Найти координаты точки экстремума и значение целевой функции в ней.

Пример 2.1. Найти максимум целевой функции Z =x1 + 4x2 → max при условиях-ограничениях:

[pic 2]

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

Сначала пронумеруем ограничения задачи:

[pic 3]

В первом неравенстве заменим знак ≥ на = и построим прямую [pic 4], для этого определим две точки, через которые она проходит:

[pic 5].

Чтобы определить, какая полуплоскость будет соответствовать неравенству, необходимо подставить в неравенство координаты любой точки плоскости. Удобно подставлять координаты точки O(0,0). Если в результате подстановки неравенство получается верное, то нужно выделить (заштриховать) ту полуплоскость, в которой лежит подставляемая точка, если неверное, то выделить ту полуплоскость, в которой она не лежит. Аналогично поступаем с неравенствами (2) и (3): [pic 6] ,

[pic 7],

[pic 8],

[pic 9]

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

[pic 10]        [pic 11]

а                                б

Рис.2.1. Область допустимых решений

Кроме того, по условию задачи [pic 12], поэтому область допустимых решений всей задачи изображена штриховкой на рис.1б.

1. Вектор OC начинается в точке O(0,0) и заканчивается в точке, координаты которой соответствуют коэффициентам целевой функции. Для рассматриваемой задачи это точка (1; 4), (рис. 2. 2).

[pic 13]

Рис. 2.2. Построение линии равных значений функции

1. Линию уровня (линию равных значений функции) проводим перпендикулярно вектору OC. Перемещая линию уровня параллельно самой себе, против вектора OC, определяем минимум целевой функции – это точка O(0,0). Перемещая линию уровня параллельно самой себе, по вектору OC, определяем максимум целевой функции – это точка B.
2. Координаты точки В можно определить, решив систему уравнений соответствующих прямых, пересекающихся в этой точке:

[pic 14].

        [pic 15];        B (1,5;5,5).

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

min[pic 16]0+0=0;        max[pic 17]1,5 + 45,5= 23,5.