Логотип

Решение задач по математике онлайн

Главная >> Пример №7. Функция неограниченно возрастает.

Графический метод решения задачи линейного программирования.

Данное решение является образцом работы программы, представленной на сайте.

Задача:
Найти наибольшее значение функции

F = 2 x1 + 2 x2

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

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

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

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

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

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

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

Подставив координаты любой точки A (x1, x2), принадлежащей области допустимых решений, в выражение функции F, можно получить значение функции в данной точке F(A).

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

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

Риунок №0. Линейное программирование.

Шаг №1

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

4 x1 - 5 x2  ≤  4

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

Пусть x1 =0 => - 5 x2 = 4 => x2 = -4/5

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

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

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

4 x1 - 5 x2  ≤  4

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

- 5 x2  ≤  - 4 x1 + 4

x2  ≥  4/5 x1 - 4/5

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

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

Риунок №1. Линейное программирование.

Шаг №2

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

3 x1 + 2 x2  ≥  1

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

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

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

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

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

3 x1 + 2 x2  ≥  1

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

2 x2  ≥  - 3 x1 + 1

x2  ≥  - 3/2 x1 + 1/2

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

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

Риунок №2. Линейное программирование.

Шаг №3

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

- 4 x1 + 3 x2  ≤  4

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

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

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

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

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

- 4 x1 + 3 x2  ≤  4

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

3 x2  ≤  4 x1 + 4

x2  ≤  4/3 x1 + 4/3

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

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

Риунок №3. Линейное программирование.

Шаг №4

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

Вектор C нарисован не в масштабе, так как он не помещается на рисунке.

Риунок №4. Линейное программирование.

Шаг №5

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

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

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

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

Риунок №5. Линейное программирование.

Ответ:

Fmax = + ∞











© 2010–2016
По всем вопросам пишите по адресу matematika1974@yandex.ru


Ссылки