Логотип

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

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

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

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

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

F = 3 x1 + 4 x2

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

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

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

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

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

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

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

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

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

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

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

Шаг №1

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

3 x1 + 4 x2  ≥  18

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

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

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

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

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

3 x1 + 4 x2  ≥  18

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

4 x2  ≥  - 3 x1 + 18

x2  ≥  - 3/4 x1 + 9/2

Знак неравенства  ≥ , следовательно, нас интересуют точки расположенные выше построенной прямой (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 системы ограничений.

x2  ≤  6

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

x2 = 6   (3)

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

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

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

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

Шаг №4

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

x1  ≤  5

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

x1 = 5   (4)

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

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

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

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

Шаг №5

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

x1 - x2  ≤  2

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

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

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

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

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

x1 - x2  ≤  2

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

- x2  ≤  - x1 + 2

x2  ≥  x1 - 2

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

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

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

Шаг №6

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

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

Шаг №7

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

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

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

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

Точка A одновременно принадлежит прямым (1) и (2). Составим систему уравнений:

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

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

F (A) = 3 * 2 + 4 * 3 = 18

Точка B одновременно принадлежит прямым (1) и (5). Составим систему уравнений:

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

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

F (B) = 3 * 26/7 + 4 * 12/7 = 18

F(A) = F(B), следовательно, предположение оказалось верным.

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

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

Ответ:

x1 = 2 * t + 26/7 * ( 1 - t )

x2 = 3 * t + 12/7 * ( 1 - t )

где   0 ≤ t ≤ 1

F min = 18

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










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


Ссылки