Неравенства на плоскости и линейное программирование

Краткое содержание

Этот урок переносит изучение неравенств на плоскость. В нём доказывается, что прямая делит плоскость на две полуплоскости, в каждой из которых задающее её линейное выражение сохраняет знак, и отсюда выводится метод пробной точки. Область решений системы линейных неравенств описывается как пересечение полуплоскостей, с её вершинами, и доказывается, что она выпукла; затем изучаются области, ограниченные коническими сечениями. Урок завершается линейным программированием: поиском наибольшего или наименьшего значения линейной функции на многоугольной области, основная теорема которого гарантирует, что на выпуклом ограниченном многоугольнике оба значения достигаются в вершинах, а в неограниченной области, имеющей хотя бы одну вершину, всякое существующее оптимальное значение также достигается в одной из них, и задачами о производстве, о рационе и о перевозках.

Цели обучения

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

Полуплоскости

В уроке об уравнении прямой было показано, что всякая прямая есть множество точек, удовлетворяющих уравнению $Ax + By + C = 0$ , где $A$ и $B$ не равны нулю одновременно: если $B \neq 0$ , то, разрешая уравнение, получаем $y = -\frac{A}{B}x - \frac{C}{B}$ , прямую с угловым коэффициентом $-\frac{A}{B}$ ; если $B = 0$ , уравнение сводится к $x = -\frac{C}{A}$ , вертикальной прямой. Если вместо равенства потребовать неравенство, множество решений перестаёт быть линией и становится областью. В уроке об уравнениях и неравенствах первой степени решением линейного неравенства с одним неизвестным был промежуток числовой прямой; при двух неизвестных решением является полуплоскость.

Пусть $r$ есть невертикальная прямая и $P = (x_0, y_0)$ есть точка. Будем говорить, что $P$ лежит выше $r$ , если $y_0$ больше ординаты точки прямой $r$ с абсциссой $x_0$ , и ниже, если меньше. Если $r$ вертикальна, так же говорят о точках, лежащих справа и слева от неё. Каждое из этих двух множеств является открытой полуплоскостью с границей $r$ ; если добавить к нему прямую, получается замкнутая полуплоскость.

ТеоремаПолуплоскости

Пусть $r$ есть прямая $Ax + By + C = 0$ , где $A$ и $B$ не равны нулю одновременно, и пусть $E(x, y) = Ax + By + C$ . Выражение $E$ имеет постоянный знак по каждую сторону от $r$ : оно положительно во всех точках одной из двух открытых полуплоскостей и отрицательно во всех точках другой. Точнее, если $B > 0$ , оно положительно выше $r$ и отрицательно ниже; если $B < 0$ , наоборот; а если $B = 0$ , оно положительно справа от $r$ при $A > 0$ и слева от неё при $A < 0$ .

Доказательство

$\dato{q}{A x_0 + B y_1 + C = 0}$
Пусть $P = (x_0, y_0)$ есть точка, не лежащая на $r$ , и предположим сначала, что $B \neq 0$ . Вертикальная прямая, проходящая через $P$ , пересекает $r$ в единственной точке $Q = (x_0, y_1)$ , ордината которой получается, если выразить $y$ из уравнения $r$ ; точка $Q$ удовлетворяет этому уравнению.
$E(x_0, y_0) = \resaltar{(A x_0 + B y_0 + C) - (A x_0 + B y_1 + C)} = \dato{dif}{\resaltar{B \cdot (y_0 - y_1)}}$
Вычтем этот нуль из значения $E$ в точке $P$ : члены с $x_0$ и свободные члены сокращаются, и остаётся произведение.
$B > 0 \rightarrow \left( E(x_0, y_0) > 0 \leftrightarrow y_0 > y_1 \right)$
Если $B > 0$ , то по правилу знаков, изученному в уроке о таблицах знаков и неравенствах, произведение имеет знак $y_0 - y_1$ : оно положительно, когда $P$ лежит выше $r$ , и отрицательно, когда лежит ниже.
$B < 0 \rightarrow \left( E(x_0, y_0) > 0 \leftrightarrow y_0 < y_1 \right)$
Если $B < 0$ , произведение имеет знак, противоположный знаку $y_0 - y_1$ : выражение отрицательно выше $r$ и положительно ниже.
$E(x_0, y_0) = \resaltar{(A x_0 + C) - (A x_1 + C)} = \resaltar{A \cdot (x_0 - x_1)}$
Если $B = 0$ , то $A \neq 0$ , и $r$ есть вертикальная прямая $x = x_1$ , где $x_1 = -\frac{C}{A}$ . Повторяем вычисление с точкой прямой $r$ , имеющей ту же ординату, что и $P$ .
$A > 0 \rightarrow \left( E(x_0, y_0) > 0 \leftrightarrow x_0 > x_1 \right)$
Если $A > 0$ , выражение положительно в точности тогда, когда $x_0 > x_1$ , то есть справа от $r$ ; если $A < 0$ , то слева от неё. Во всех случаях знак $E$ в точке зависит только от того, по какую сторону от $r$ лежит эта точка.

Теорема говорит больше, чем используется на практике: не нужно помнить, какой знак соответствует каждой стороне, потому что достаточно знать знак $E$ в одной-единственной точке стороны, чтобы знать его во всех. В этом и состоит метод пробной точки.

Чтобы изобразить неравенство $Ax + By + C > 0$ , или со знаком $<$ , $\ge$ или $\le$ , проводят прямую $Ax + By + C = 0$ и вычисляют значение выражения в пробной точке, не лежащей на ней, обычно в начале координат. Если точка удовлетворяет неравенству, множество решений есть полуплоскость, которая её содержит; если не удовлетворяет, то другая. Если неравенство строгое, прямая не входит в множество решений и рисуется штриховой линией; если нестрогое, она входит в него и рисуется сплошной.

ПримерПолуплоскость по пробной точке

Изобразить множество решений неравенства $2x - 3y + 6 > 0$ .

Доказательство

$2x - 3y + 6 = 0, \quad (0, 2), \quad (-3, 0)$
Проводим граничную прямую через точки её пересечения с осями: при $x = 0$ получаем $y = 2$ , а при $y = 0$ получаем $x = -3$ .
$2 \cdot 0 - 3 \cdot 0 + 6 = \resaltar{6} > 0$
Начало координат не лежит на прямой. Вычисляем в нём значение выражения: оно положительно, так что начало координат удовлетворяет неравенству.
$2x - 3y + 6 > 0 \leftrightarrow \resaltar{y < \frac{2}{3}x + 2}$
Множество решений есть полуплоскость, содержащая начало координат. Теорема это подтверждает: так как $B = -3 < 0$ , выражение положительно ниже прямой.
$2 \cdot (-3) - 3 \cdot 0 + 6 = \resaltar{0}$
Неравенство строгое: точки прямой, например $(-3, 0)$ , обращают выражение в нуль и ему не удовлетворяют. Граница исключается и рисуется штриховой линией.

Далее в этом уроке

Системы линейных неравенств
Ограниченные, неограниченные и пустые области
Выпуклость
Области, ограниченные коническими сечениями
Линейное программирование
Линии уровня
Неограниченные области и несколько оптимальных решений
Моделирование
Решённые задачи
Квадрат, описанный с помощью модулей
Производство в мастерской
Рацион наименьшей стоимости
Исчезающая область
Наибольшее значение на криволинейной границе
Задачи для самостоятельного решения
Ближе к началу координат
Бесконечно много оптимальных решений
Перевозки между двумя складами
Когда вершина не целая
Оптимальная вершина в зависимости от параметра

Продолжите чтение с бесплатным аккаунтом

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

Создать аккаунт Войти

Получите доступ ко всему курсу

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

Создать аккаунт Войти