Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Графический метод решения задач

Графический метод используется для решения задач с двумя переменными следующего вида:

Z(X) =c₁x₁+c₂x₂ → max (min)

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

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

Областью решений линейного неравенства a_i1x₁+a_i2x₂≤b_i является одна из двух полуплоскостей, на которые прямая a_i1x₁+a_i2x₂=0, соответствующая данному неравенству, делит всю координатную плоскость. Для того, чтобы определить, какая из полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство: если оно удовлетворяется, то областью решений является полуплоскость, содержащая эту точку, если не удовлетворяется – то полуплоскость, не содержащая данную точку.

Для нахождения среди допустимых решений оптимального используют линии уровня и опорные прямые. Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение линии уровня имеет вид c₁x₁+c₂x₂=L, где L = const. Все линии уровня параллельны между собой. Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с областью допустимых решений и по отношению к которой эта область находиться в одной из полуплоскостей. Важное свойство линии уровня: при параллельном смещении линии в одну сторону уровень возрастает, а в другую сторону – убывает.

Задание 1: Решить графическим методом задачу с двумя переменными.

Z(x)=2х₁+3х₂ → max

-6х₁+х₂ ≥ 3

-5х₁+9х₂ ≤ 45

x₁-3х₂ ≤ 3

х₁ ≥ 0, х₂ ≥ 0

Найдем точки пересечения прямых с осями координат:

I. -6х₁+х₂=3

1) х₁=0 2) х₂=0

x₂=3 х₁= -1/2

II. -5х₁+9х₂=45

1) х₂=0 2) х₂=0

x₂=5 х₁= -9

III. х₁-3х₂=3

1) х₁=0 2) х₂=0

x₂= -1 х₁=3

Построим область решения данной системы:

Найдем вектор направленности целевой функции

Z(х)=2х₁+3х₂=0

1) х₁=0 2) х₁=3

x₂=0 х₂= -2

Z(х)=2х₁+3х₂=6

1) х₁=0 2) х₂=0

x₂=2 х₁=3

Ответ: Целевая функция принимает максимальное значение в точке (0;0), при х₁=0 и х₂=0.