1.2. Решение систем т линейных уравнений с двумя переменными

Дана система .

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

Определение 15. Решением каждого неравенства системы является полуплоскость, которая содержит граничную прямую и располагается по одну сторону от неё.

Определение 16. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью решения системы (ОР).

Определение 17. Область решения системы, удовлетворяющая условиям , называется областью неотрицательных, или допустимых, решений (ОДР).

Лекция 2

Пример 1. Найти ОР и ОДР системы неравенств и определить координаты угловых точек ОДР

РЕШЕНИЕ. Найдём ОР первого неравенства: . Построим прямую линию (рис. 1.2). Подставим координаты точки (0, 0) в неравенство: так как координаты точки (0, 0) не удовлетворяют ему, то решением неравенства (1.1) является полуплоскость, не содержащая точку (0.0).

Аналогично найдём решения остальных неравенств системы. Получим, что ОР и ОДР системы неравенств является выпуклый многогранник АВСD.

Х₂

В

С

А

(1.4)

(1.3)

D

Х₁

(1.2)

(1.1)

Рис. 1.2

Найдём угловые точки многогранника. Точку А определим как точку пересечения прямых

Решая систему, получим А(3/7, 6/7).

Точку В найдём как точку пересечения прямых

Из системы получим В(5/3, 10/3). Аналогично найдём координаты точек С и D: C(11/4, 9/4), D(21/10; 3/10).

Пример 2. Найти ОР и ОДР системы неравенств

РЕШЕНИЕ. Построим прямые и определим решения неравенств (1.5)-(1.7). ОР и ОДР являются неограниченные многогранные области ACFM и ABDEKM соответственно (рис. 1.3).

Пример 3. Найти ОР и ОДР системы неравенств

РЕШЕНИЕ. Найдём решения неравенств (1.8)-(1.10) (рис. 1.4). ОР представляет неограниченную многогранную область АВС; ОДР – точка В.

Пример 4. Найти ОР и ОДР системы неравенств

РЕШЕНИЕ. Построив прямые, найдём решения неравенств системы. ОР и ОДР не существует (рис. 1.5).

2. Графический метод

2.1. Постановка задачи

2.2. Алгоритм решения задач

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

2. Строим вектор , координатами которого являются коэффициенты целевой функции.

3. Проводим линию уровня , которая перпендикулярна .

4. Линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном , для задач на минимум.

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

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

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

5. Находим координаты точки экстремума и значение целевой функции в ней.