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

Графический метод

Общая и основная задачи ЛП | Алгоритм симплекс-метода | Методы искусственного базиса | Двойственная задача ЛП. Экономическая интерпретация двойственной задачи ЛП | Экономическая интерпретация двойственной задачи | Постановка транспортной задачи | Метод потенциалов-метод решения транспортной задачи |


Читайте также:
  1. B. Неклассическая методология
  2. C. Постнеклассическая методология
  3. D) сохранения точных записей, определения установленных методов (способов) и сохранения безопасности на складе
  4. D.2. Методы оценки технических уязвимостей
  5. I 7 D I РЕЛИГИЯ И НАУЧНЫЕ МЕТОДЫ
  6. I РЕЛИГИЯ И НАУЧНЫЕ МЕТОДЫ
  7. I РЕЛИГИЯ И НАУЧНЫЕ МЕТОДЫ

Графическим методом в основном решаются задачи с малым числом переменных. Он включает следующие этапы:

1. Строится многогранник решений.

Геометрический смысл системы ограничений состоит в следующем: уравнение представляет собой гиперплоскость в n-мерном пространстве, неравенство же есть точки подпространства, лежащие по одну сторону от гиперплоскости и образующие выпуклое множество. Следовательно, система ограничений (1.2) задачи ЛП есть множество точек n-мерного пространства, причем это множество выпуклое и каждая точка является решением системы неравенств.

2. Находятся вектор и вершина многоугольника решений, на которой достигаетсяmax z.

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

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

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

 
 

На первом рисунке изображен случай, когда целевая функция принимает максимальное значение в единственной точке M. Из второго рисунка видно, что максимальное значение целевая функция принимает в любой точке отрезка AB. На третьем рисунке изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений.

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

 


Дата добавления: 2015-11-14; просмотров: 47 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Свойства задач линейного программирования. Графический метод решения задач линейного программирования| Алгоритм симплекс-метода решения общей задачи линейного программирования

mybiblioteka.su - 2015-2024 год. (0.008 сек.)