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

English

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

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

F = x1 - 2 x2

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

Знак системы 2 x1 + x2 2
4 x1 - 6 x2 12
x2 1

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

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

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

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

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

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

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

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

Шаг №1

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

2 x1 + x2  ≥  2

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

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

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

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

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

2 x1 + x2  ≥  2

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

x2  ≥  - 2 x1 + 2

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

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

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

Шаг №2

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

4 x1 - 6 x2  ≤  12

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

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

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

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

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

4 x1 - 6 x2  ≤  12

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

- 6 x2  ≤  - 4 x1 + 12

x2  ≥  2/3 x1 - 2

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

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

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

Шаг №3

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

x2  ≥  1

Построим прямую: x2 = 1

Данная прямая параллельна оси OX1 и проходит через точку (0,1)   (3)

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

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

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

Шаг №4

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

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

Шаг №5

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

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

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

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

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

Ответ:

Fmin = - ∞









© 2010-2020, по всем вопросам пишите по адресу matematika1974@yandex.ru


Ссылки