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

Пусть хорошие люди смотрят хорошие решения
English

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

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

F = 3 x1 - x2

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

Знак системы x1 - x2 8
3 x1 - x2 3
2 x1 + x2 4

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

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

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

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

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

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

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

Рисунок №0.  Графический метод линейного программирования.

Шаг №1

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

x1 - x2  ≤  8

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

Пусть x1 =0 => - x2 = 8 => x2 = -8

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

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

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

x1 - x2  ≤  8

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

- x2  ≤  - x1 + 8

x2  ≥  x1 - 8

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

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

Рисунок №1.  Графический метод линейного программирования.

Шаг №2

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

3 x1 - x2  ≥  3

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

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

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

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

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

3 x1 - x2  ≥  3

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

- x2  ≥  - 3 x1 + 3

x2  ≤  3 x1 - 3

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

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

Рисунок №2.  Графический метод линейного программирования.

Шаг №3

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

2 x1 + x2  ≥  4

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

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

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

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

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

2 x1 + x2  ≥  4

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

x2  ≥  - 2 x1 + 4

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

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

Рисунок №3.  Графический метод линейного программирования.

Шаг №4

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

Рисунок №4.  Графический метод линейного программирования.

Шаг №5

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

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

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

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

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

Знак системы 3 x1 - x2 = 3   =>   x1 = 7/5
2 x1 + x2 = 4 x2 = 6/5

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

F (A) = 3 * 7/5 - 1 * 6/5 = 3

Координаты любой точки луча, имеющего свое начало в точке А, можно записать следующим образом:

x1 = 7/5 + 1 * t

x2 = 6/5 + 3 * t

где   t ≥ 0

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

x1 = 7/5 + 1 * 1 = 12/5

x2 = 6/5 + 3 * 1 = 21/5

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

F (B) = 3 * 12/5 - 1 * 21/5 = 3

F(A) = F(B)

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

Рисунок №5.  Графический метод линейного программирования.

Ответ:

x1 = 7/5 + 1 * t

x2 = 6/5 + 3 * t

где   t ≥ 0

Fmin = 3









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


Ссылки