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

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

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

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

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

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

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

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

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

3 x₁ + 2 x₂  ≥  6

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

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

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

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

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

3 x₁ + 2 x₂  ≥  6

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

2 x₂  ≥  - 3 x₁ + 6

x₂  ≥  - 3/2 x₁ + 3

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

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

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

- x₁ + x₂  ≤  1

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

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

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

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

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

- x₁ + x₂  ≤  1

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

x₂  ≤  x₁ + 1

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

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

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

x₁ - 2 x₂  ≤  1

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

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

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

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

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

x₁ - 2 x₂  ≤  1

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

- 2 x₂  ≤  - x₁ + 1

x₂  ≥  1/2 x₁ - 1/2

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

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

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

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

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

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

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