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

Рассмотрим следующую задачу линейного программирования:

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

f=х+2у (1)

при ограничениях

х (3)

Найдем, прежде всего, множество М точек, удовлетворяющих условиям (2). Каждое из неравенств определяет полуплоскость, а пересечением всех этих полуплоскостей и будет множество М.

5х-у+1=0

у-х+1=0

у
f=х+2у
	М
х+у-1=0
1
Рис.1
	1									х

-2х-у+8=0

Решением нашей задачи будет точка (х⁰, у⁰), удовлетворяющая условиям

1. (х⁰, у⁰)

2. f(х⁰, у⁰)= х⁰ +2у⁰=C, где С наибольшее возможное число.

Поэтому для нахождения (х⁰, у⁰) нужно найти линию уровня с наибольшим С, пересекающую М.

f=C²

у
f=C0
	В
f=C1
	М
1
Рис.2
	1									х

Такой точкой (х⁰, у⁰) будет точка В, так как для линий уровня, лежащих ниже прямой х+2у=C⁰ , C¹<C⁰, а линии уровня, лежащие выше х+2у=C⁰ не имеют с М общих точек. Поэтому решение задачи

х=1, у=6, f(х,у)=х+2у=13.