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

English

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

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

F = x1 + x2

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

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

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

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

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

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

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

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

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

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

Шаг №1

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

x1 + x2  ≥  1

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

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

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

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

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

x1 + x2  ≥  1

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

x2  ≥  - x1 + 1

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

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

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

Шаг №2

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

x1 - x2  ≥  1

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

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

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

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

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

x1 - x2  ≥  1

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

- x2  ≥  - x1 + 1

x2  ≤  x1 - 1

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

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

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

Шаг №3

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

x1  ≤  1

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

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

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

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

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

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

Шаг №4

Необходимо проверить, удовлетворяют ли координаты точки A (1,0) неравенству 4 системы ограничений?

2 * 1 + 1 * 0  ≥  1

2  ≥  1

Да, удовлетворяют.

Шаг №5

Необходимо проверить, удовлетворяют ли координаты точки A (1,0) неравенству 5 системы ограничений?

1 * 1 + 2 * 0  ≤  7

1  ≤  7

Да, удовлетворяют.

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

F (A) = 1 * 1 + 1 * 0 = 1

Ответ:

x1 = 1

x2 = 0

Fmax = 1









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


Ссылки