Студопедия

КАТЕГОРИИ:

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



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




Читайте также:
  1. I. Задачи настоящей работы
  2. I. Цели и задачи проекта
  3. II. Основные цели и задачи Программы, срок и этапы ее реализации, целевые индикаторы и показатели
  4. II. Упражнения и задачи
  5. II. Упражнения и задачи
  6. II. Упражнения и задачи
  7. II. Цели и задачи проекта
  8. III. Для обеспечения проверки исходного уровня Ваших знаний-умений необходимому, предлагаем решить 2 задачи.
  9. III. Для обеспечения проверки исходного уровня Ваших знаний-умений необходимому, предлагаем решить 2 задачи.
  10. IV. Задачи для самостоятельной работы.

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

На рис. 4.1 представлено множество допустимых точек, удовлетворяющих всем ограничениям задачи и представляющее собой пересечение полуплоскостей, отражающих ограничения задачи линейного программирования.

Рис. 4.1. Геометрическая интерпретация решения задачи

Геометрическую интерпретацию имеют ЗЛП с двумя переменными.

Исследуем целевую функцию 30х1 + 40х2. Данной целевой функции соответствует семейство прямых 30х1 + 40х2 = L, представляющих собой множество параллельных прямых, каждая из которых соответствует определенному значению параметра L. Тогда задачу линейного программирования можно сформулировать следующим образом. Найти такое максимальное значение L, при котором прямая 30х1 + 40х2 = L пересекает допустимое множество.

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

Для нахождения экстремального значения целевой функции при графическом решении ЗЛП используют вектор-градиент целевой функции Ñf(`X) на плоскости Х1ОХ2. Этот вектор показывает направление наискорейшего изменения целевой функции, он равен

,

где и - единичные векторы по осям ОХ1 и ОХ2 соответственно. Таким образом, Ñf(`X) = (f/x1, (f/x2). Координатами вектора-градиента целевой функции Ñf(`X) являются коэффициенты целевой функции f(`X).

В рассматриваемом примере, если двигать прямую 30х1 + 40х2 = L из начала координат по направлению вектора-градиента целевой функции, то точкой, в которой достигается самая верхняя линия уровня является точка М пересечения прямых 5x1 + 2x2 = 10000 и x1 + 2x2 = 4000 с координатами x1 = 1500 и x2 = 1250. Таким образом, оптимальное решение достигается в точке М (1500; 1250). При этом значение целевой функции составит f(`X*) =30 * 1500 + 40 * 1250 = 95000.

На этом примере можно увидеть основные свойства задач линейного программирования: допустимое множество точек представляет собой выпуклый многоугольник, получившийся в результате пересечения полуплоскостей и наибольшее значение целевой функции достигается в его вершине – крайней точке.



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

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

 


Дата добавления: 2014-12-03; просмотров: 36; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты