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

и другие интересные типовые задачи
English

Пример №10. Решение задачи линейного программирования графическим методом.
Область допустимых решений - пустое множество

Данное решение сделано калькулятором, представленным на сайте.
Задача:
Найти наибольшее значение функции

F = x1 + x2

при следующих ограничениях:

Знак системы 3 x1 + 5 x2 30
4 x1 - 3 x2 12
x1 - 3 x2 6

x1 ≥ 0     x2 ≥ 0
Решение:

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

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

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

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

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

По условию задачи: x1 ≥ 0     x2 ≥ 0.

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

Шаг №1

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

3 x1 + 5 x2  ≤  30

Построим прямую:   3 x1 + 5 x2 = 30

Пусть x1 =0 => 5 x2 = 30 => x2 = 6

Пусть x2 =0 => 3 x1 = 30 => x1 = 10

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

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

3 x1 + 5 x2  ≤  30

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

5 x2  ≤  - 3 x1 + 30

x2  ≤  - 3/5 x1 + 6

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

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

Шаг №2

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

4 x1 - 3 x2  ≤  12

Построим прямую:   4 x1 - 3 x2 = 12

Пусть x1 =0 => - 3 x2 = 12 => x2 = -4

Пусть x2 =0 => 4 x1 = 12 => x1 = 3

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

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

4 x1 - 3 x2  ≤  12

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

- 3 x2  ≤  - 4 x1 + 12

x2  ≥  4/3 x1 - 4

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

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

Шаг №3

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

x1 - 3 x2  ≥  6

Построим прямую:   x1 - 3 x2 = 6

Пусть x1 =0 => - 3 x2 = 6 => x2 = -2

Пусть x2 =0 => x1 = 6

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

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

x1 - 3 x2  ≥  6

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

- 3 x2  ≥  - x1 + 6

x2  ≤  1/3 x1 - 2

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

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

Ответ:

Область допустимых решений - пустое множество.









© 2010-2021

Если у Вас есть замечания, пожалуйста, пишите siteReshmat@yandex.ru


Ссылки