Сервис для решения задач по линейному программированию

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

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

Последние два шага служат непосредственно для получения ответа. (см. шаг 4 - шаг 5)

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

Посмотреть план решение этой задачи в картинках

По условию задачи: x₁ ≥ 0     x₂ ≥ 0.

Если бы это было единственным условием, то область допустимых решений имела бы вид, как на рисунке (вся первая четверть).

Большие картинки

Рассмотрим неравенство 1 системы ограничений.

x₁ - 2 x₂  ≤  4

Построим прямую:   x₁ - 2 x₂ = 4

Пусть x₁ =0 => - 2 x₂ = 4 => x₂ = -2

Пусть x₂ =0 => x₁ = 4

Найдены коородинаты двух точек (0, -2) и (4 ,0). Соединяем их и получаем необходимую прямую (1).

Нас интересуют точки расположенные выше или ниже построенной прямой (1) ?
Вернемся к исходному неравенству.

x₁ - 2 x₂  ≤  4

Преобразуем неравенство, оставив в левой части только x₂

- 2 x₂  ≤  - x₁ + 4

x₂  ≥  1/2 x₁ - 2

Знак неравенства  ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (1).

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

Большие картинки

Рассмотрим неравенство 2 системы ограничений.

x₁ - x₂  ≥  1

Построим прямую:   x₁ - x₂ = 1

Пусть x₁ =0 => - x₂ = 1 => x₂ = -1

Пусть x₂ =0 => x₁ = 1

Найдены коородинаты двух точек (0, -1) и (1 ,0). Соединяем их и получаем необходимую прямую (2).

Нас интересуют точки расположенные выше или ниже построенной прямой (2) ?
Вернемся к исходному неравенству.

x₁ - x₂  ≥  1

Преобразуем неравенство, оставив в левой части только x₂

- x₂  ≥  - x₁ + 1

x₂  ≤  x₁ - 1

Знак неравенства  ≤ . Следовательно, нас интересуют точки расположенные ниже построенной прямой (2).

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

Большие картинки

Рассмотрим неравенство 3 системы ограничений.

x₁ + x₂  ≥  2

Построим прямую:   x₁ + x₂ = 2

Пусть x₁ =0 => x₂ = 2

Пусть x₂ =0 => x₁ = 2

Найдены коородинаты двух точек (0, 2) и (2 ,0). Соединяем их и получаем необходимую прямую (3).

Нас интересуют точки расположенные выше или ниже построенной прямой (3) ?
Вернемся к исходному неравенству.

x₁ + x₂  ≥  2

Преобразуем неравенство, оставив в левой части только x₂

x₂  ≥  - x₁ + 2

Знак неравенства  ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (3).

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

Большие картинки

Строим вектор C = (-1, 1), координатами которого являются коэффициенты функции F.

Вектор C нарисован не в масштабе, так как он не помещается на рисунке.

Большие картинки

Будем перемещать "красную" прямую, перпендикулярно вектору C, от правого нижнего угла к левому верхнему.

"Красная" прямая называется линией уровня. В каждой точке линии уровня значение функции F есть величина постоянная.

В точке, в которой "красная" прямая в первый раз пересечет область допустимых решений, функция F достигает своего наименьшего значения.

В точке, в которой "красная" прямая в последний раз пересечет область допустимых решений, функция F достигает своего наибольшего значения.

Есть предположение, что функция F достигает наибольшего значения на луче, который имеет свое начало в точке А (см. рисунок).
Проверим это предположение.

Найдем координаты точки A.
Точка A одновременно принадлежит прямым (2) и (3).

		x1	-	x2	=	1	=>	x1 = 3/2
		x1	+	x2	=	2		x2 = 1/2

Вычислим значение функции F в точке A (3/2,1/2).

F (A) = -1 * 3/2 + 1 * 1/2 = -1

На основании уравнения прямой (2) на которой находится луч, имеющей свое начало в точке А, можно записать параметрическое уравнение луча следующим образом:

x₁ = 3/2 + 1 * t

x₂ = 1/2 + 1 * t

где   t ≥ 0

Предположим, что при t = 1 мы имеет точку В.
Найдем координаты точки B.

x₁ = 3/2 + 1 * 1 = 5/2

x₂ = 1/2 + 1 * 1 = 3/2

Вычислим значение функции F в точке B (5/2,3/2).

F (B) = -1 * 5/2 + 1 * 3/2 = -1

F(A) = F(B)

Тогда можно сделать вывод, что и в любой точке луча, имеющего свое начало в точке А, функция F достигает своего наибольшего значения.

Большие картинки