Лекции по линейному программированию
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Методы решения задач линейного программирования.

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

Графический метод основан на геометрической интерпретации задачи ЛП и эффективно может применяться для решения задач двумерного пространства. Задачи трехмерного пространства этим методом решаются очень редко, так как построение их решения неудобно и лишено наглядности.

Рассмотрим работу метода на примере двумерной задачи. Найдем решение удовлетворяющее системе неравенств

При котором значение целевой функции достигает максимума.

Построим на плоскости ОДР задачи. Границей ОДР будет объединение отрезков прямых, получаемых из системы ограничений путем замены знаков неравенств на равенства, рассмотренных в первом координатном углу. Внутренняя часть полученного многоугольника вместе с границей определяют ОДР. Крайние точки ОДР соответствуют допустимым базисным решениям задачи ЛП. Значение целевой функции можно определить в любой точке ОДР. Прямая линия, перпендикулярная вектору с координатами (3;2) будет геометрическим местом точек, в которых целевая функция принимает одинаковые фиксированные значения (в дальнейшем такие геометрические места точек будем называть Линиями уровня).

 
рис. i.2.2.
Заметим, что координаты указанного вектора являются соответственно коэффициентами целевой функции и равны ее частным производным по соответствующим переменным Такие векторы называют Градиентами функции[1]. В силу линейности целевой функции задачи ЛП, этот вектор имеет постоянные величину и направление.

 
рис. i.2.1.
Нетрудно проверить, что в точке (3; 2) Максимальное значение функция достигает в крайней точке ОДР. Это и будет оптимальное решение задачи. Координаты точки легко найти. Это решение системы

Таким образом а

[1] Будем обозначать их или кратко .

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство