Список индивидуальных данных

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

1. Построить область допустимых решений задачи линейного программирования;

2. Построить линии уровня функции цели;

3. Найти точки пересечения линий уровня с границей области допустимых решений;

4. Создать html-файл «lab4_N.html» с результатами работы, график сохранить в файле с именем «varN», где N – номер варианта;

5. Подготовить теоретический материал для защиты работы и ответа на контрольные вопросы преподавателя.

Варианты:

1.	5x1-10x2 + 50  0, -x1+5x2 + 5  0, 9x1+7x2 – 63  0, x1  0, x2  0, Q = 3x1+2x2  min	2.	2x1-5x2 + 10  0, 5x1+8x2 – 40  0, -x1+7x2 + 7  0, x1  0, x2  0, Q = -x1+2x2  min
3.	3x1-2x2 + 6  0, -2x1+5x2 + 10  0, 4x1+9x2 – 36  0, x1  0, x2  0, Q = x1-x2  max	4.	3x1+7x2 – 21  0, 2x1-3x2 + 6  0, -2x1+6x2 + 12  0, x1  0, x2  0, Q = -x1+x2  min
5.	4x1-5x2 + 20  0, 5x1+6x2 – 30  0, -3x1+4x2 + 12  0, x1  0, x2  0, Q = 4x1-x2  min	6.	3x1-2x2 + 6  0, -5x1+4x2 + 20  0, 8x1+7x2 – 54  0, x1  0, x2  0, Q = -x1-x2  max
7.	8x1+4x2 – 32  0, 6x1-3x2 + 18  0, -2x1+3x2 + 6  0, x1  0, x2  0, Q = x1-5x2  min	8.	7x1-5x2 + 35  0, 10x1+8x2 – 80  0, -3x1+4x2 + 12  0, x1  0, x2  0, Q = 3x1-x2  max
9.	x1+x2  2, -x1+2x2  4, x1 +2x2  8, x1  0, x2  0, Q = 2x1-6x2  max	10.	x1+x2  4, -x1+2x2  2, x1 +2x2  10, x1  0, x2  0, Q = 2x1-x2  min
11.	x1-4x2 –4  0, 3x1 - x2  0, x1+x2 –4  0, x1  0, x2  0, Q = x1+x2  max	12.	x1+x2  4, 2x1-x2  2, -x1 -2x2  -10, x1  0, x2  0, Q = 2x1-x2  min

Пример выполнения работы

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

Решение.

На первом этапе построим область допустимых решений – многогранник решений.

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

Для этого, например, построим сначала прямую . Эта прямая проходит через точки (0;6) и (12;0) – точки ее пересечения с осями координат. Затем возьмем произвольную точку, не лежащую на этой прямой точка, например точку (0;0), и проверим, удовлетворяют ли ее координаты соответствующему неравенству или нет. Если координаты точки удовлетворяют неравенству, то вся полуплоскость, в которой находится эта точка, является допустимой (по отношению к этому условию). В противном случае, полуплоскость является недопустимой и на рисунке заштриховывается. Таким же образом поступаем со всеми неравенствами, заданными в задаче.

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

Уравнение	Х1	Х2	Х1	Х2	Точка (0,0)
1	0	6	12	0	Удовлетворяет неравенству
2	8	2	8	4	Удовлетворяет неравенству
3	0	3	3	0	Не удовлетворяет неравенству

Рисунок 3.2.

На втором этапе построим прямые – линии уровня целевой функции, то есть линии, во всех точках которых значение целевой функции постоянно. Для этого выбираем произвольные значения целевой функции, например, Q=10.

Тогда точки, в которых целевая функция принимает значение 10, лежат на прямой - линии уровня Q=10.(на рисунке эта линия обозначена точками). Все линии уровня, принадлежащие другим значениям, являются прямыми, параллельными прямой Q=10. Направление, в котором следует параллельно смещать линию уровня, чтобы достичь меньших значений, определим, построив линию уровня Q=15.

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

Уравнение	Х1	Х2	Х1	Х2
Q=10	0	4	10	0
Q=15	0	7,5	15	0

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

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

Путем параллельного переноса линий уровня в направлении меньших значений целевой функции получаем, что множеству P принадлежит одна точка, которая является точкой пересечения прямой, заданной неравенством 3, и прямой х₂=0.

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

Решением этой системы является точка х₁=3, х₂=0: P = { (3;0) }.

Решением задачи является точка (3;0), в которой целевая функция принимает минимальное значение:

Q_min=3+2,5*0=3.