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

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

Пример №3. Решение задачи линейного программирования графическим методом.
Функция достигает наибольшего значения на отрезке

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

F = x1 + 2 x2

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

Знак системы x1 + 2 x2 10
x1 + 2 x2 2
2 x1 + x2 10
3 x1 + x2 3

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

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

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

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

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

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

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

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

Шаг №1

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

x1 + 2 x2  ≤  10

Построим прямую:   x1 + 2 x2 = 10

Пусть x1 =0 => 2 x2 = 10 => x2 = 5

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

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

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

x1 + 2 x2  ≤  10

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

2 x2  ≤  - x1 + 10

x2  ≤  - 1/2 x1 + 5

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

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

Шаг №2

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

x1 + 2 x2  ≥  2

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

Пусть x1 =0 => 2 x2 = 2 => x2 = 1

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

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

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

x1 + 2 x2  ≥  2

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

2 x2  ≥  - x1 + 2

x2  ≥  - 1/2 x1 + 1

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

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

Шаг №3

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

2 x1 + x2  ≤  10

Построим прямую:   2 x1 + x2 = 10

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

Пусть x2 =0 => 2 x1 = 10 => x1 = 5

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

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

2 x1 + x2  ≤  10

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

x2  ≤  - 2 x1 + 10

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

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

Шаг №4

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

3 x1 + x2  ≥  3

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

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

Пусть x2 =0 => 3 x1 = 3 => x1 = 1

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

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

3 x1 + x2  ≥  3

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

x2  ≥  - 3 x1 + 3

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

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

Шаг №5

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

Шаг №6

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

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

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

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

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

Координаты точки A (0,5) известны. (см. шаг 1)

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

F (A) = 1 * 0 + 2 * 5 = 10

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

Знак системы x1 + 2 x2 = 10   =>   x1 = 10/3
2 x1 + x2 = 10 x2 = 10/3

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

F (B) = 1 * 10/3 + 2 * 10/3 = 10

F(A) = F(B)

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

Ответ:

x1 = 0 * t + 10/3 * ( 1 - t )

x2 = 5 * t + 10/3 * ( 1 - t )

где   0 ≤ t ≤ 1

F max = 10

Замечание: изменяя параметр t можно получить координаты любой точки отрезка AB.










© 2010-2024

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


Ссылки