Киберфак – бесплатно скачать презентации PowerPoint, лекции, рефераты, шпоры, курсовые cyberfac logo
cyberfac.ru
На главную | Регистрация | Вход
  Статьи  
Главная » Статьи » Математика » Математические методы в экономике

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

Полезная статья? Пожалуйста, поставьте "+"
Математические методы в экономике - Содержание

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

  1. Для решения задач с двумя переменными, когда ограничения выражены неравенствами;
  2. Решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных.

Запишем задачу линейного программирования с двумя переменными:

целевая функция:

Zmax = c1x1 + c2x2 (1)

ограничения:

a11x1+a12x2+...+a1nxn=b1

a21x1+a22x2+...+a2nxn=b2 (2)

............................

a11x1+a12x2+...+amnxn=bm


x1>=0, x2>=0,...,xn>=0 (3)

Каждое из неравенств (2) – (3) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми ai1xi1 + ai2xi2 = bi, i=1, 2, ..., m; х1 = 0; х2 = 0. В том случае, если система неравенств (2) – (3) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств.

Поскольку x1 и x2 должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси x1и правее оси x2 , т.е. в I-м квадранте.

Областью допустимых решений системы неравенств (2) – (3) может быть:

  • выпуклый многоугольник;
  • выпуклая многоугольная неограниченная область;
  • пустая область;
  • луч;
  • отрезок;
  • единственная точка.

Целевая функция (1) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение Z.

Вектор C=(c1;c2) с координатами из коэффициентов ЦФ при x1 и x2 перпендикулярен к каждой из линий уровня. Направление вектора C=(c1;c2) совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора C=(c1;c2).

Суть графического метода заключается в следующем. По направлению (против направления) вектора C=(c1;c2) в ОДР производится поиск оптимальной точки X* = (x1*;x2*). Оптимальной считается точка, через которую проходит линия уровня Lmax ( Lmin ), соответствующая наибольшему (наименьшему) значению функции L(X). Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач ЛП возможны следующие ситуации:

  • существует единственное решение задачи;
  • существует бесконечное множество решений (альтернативный оптимум);
  • ЦФ не ограничена;
  • область допустимых решений – единственная точка;
  • задача не имеет решений.

Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (2) – (3) и семейство параллельных прямых (1), то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z.

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

Для определения данной вершины построим линию уровня Z = c1x1 + c2x2 = 0, проходящую через начало координат и перпендикулярную вектору C=(c1;c2), и будем передвигать ее в направлении вектора C=(c1;c2) до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений.

Координаты указанной точки определяют оптимальный план данной задачи.


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

Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора C=(c1;c2), а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения.

Для практического решения задачи линейного программирования (1) – (3) на основе ее геометрической интерпретации необходимо следующее:

  1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (2) – (3) знаков неравенств на знаки равенств.
  2. Найти полуплоскости, определяемые каждым из ограничений.
  3. Определить многоугольник решений.
  4. Построить вектор C=(c1;c2).
  5. Построить прямую Z = c1x1 + c2x2 = 0, проходящую через начало координат и перпендикулярную вектору C=(c1;c2).
  6. Передвигать прямую Z в направлении вектора C=(c1;c2), в результате чего либо находят точку (точки), в которой функция принимает максимальное значение, либо устанавливают неограниченность функции сверху на множестве планов.
  7. Определить точки координаты максимума функции и вычислить значение целевой функции в этой точке.

Категория: Математические методы в экономике | Добавил: Ni-Cd (12 Декабрь 2011)
Просмотров: 6089 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

В нашем каталоге файлов можно найти много полезной информации. Также советуем заглянуть в каталог статей: в нем есть полезные статьи по темам: Экономика предприятия, Общая экономика, Финансы и Кредит, также Словарь терминов по экономике, Маркетинг, Бухучет и Мировая экономика
Также есть полезная страница Факультеты МИФИ, которая расскажет о том, какие есть в МИФИ факультеты.
Меню
 

Навигация
Теория вероятностей и математическая статистика (ТерВер и МатСтат) [17]
Математический анализ (МатАн) [67]
Математические методы в экономике [24]
 

Поиск
 

Онлайн
Онлайн всего: 1
Гостей: 1
Пользователей: 0
 

Статистика


Рейтинг@Mail.ru

 


2007 - 2017 © Ni-Cd. All Rights Reserved