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

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

Классификация систем | Описание системы в виде множества элементов | Структура как статистическая модель системы. Граф как математическая модель структуры. | Входные и выходные процессы | Управление системой. Задачи управления. Системы управления. | Информационные аспекты моделирования. | Модель динамических рядов | Показатели временного ряда и методы их исчисления. | Общая задача линейного программирования | Задача о рационе. |


Читайте также:
  1. I. ЗАДАЧИ ПАРТИИ В ОБЛАСТИ ЭКОНОМИЧЕСКОГО СТРОИТЕЛЬСТВА, СОЗДАНИЯ И РАЗВИТИЯ МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЙ БАЗЫ КОММУНИЗМА
  2. I. Составление математической модели задачи.
  3. I. Цели и задачи
  4. I. ЦЕЛИ И ЗАДАЧИ ОБУЧЕНИЯ ДИСЦИПЛИНЕ «НЕМЕЦКИЙ ЯЗЫК В СФЕРЕ ЮРИСПРУДЕНЦИИ» СТУДЕНТОВ-ЮРИСТОВ ЗАОЧНОЙ ФОРМЫ ОБУЧЕНИЯ
  5. II. ЗАДАЧИ ПАРТИИ В ОБЛАСТИ ПОДЪЕМА МАТЕРИАЛЬНОГО БЛАГОСОСТОЯНИЯ НАРОДА
  6. II. Основные задачи ФСБ России
  7. II. Основные цели и задачи Программы с указанием сроков и этапов ее реализации, а также целевые индикаторы и показатели, отражающие ход ее выполнения

Графический метод применяется при решении ЗЛП с 2-мя переменными, заданными в стандартном виде, и многими переменными в канонической форме, при условии, что n - r ≤ 2, где n – число неизвестной системы ограничений, r – ранг системы векторов условий.

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

Z=c₁x₁ + c₂x₂ max

Ограничения: a₁₁x₁ + a₁₂x₂≤b₁

a₂₁x₁ + a₂₂x₂≤b₂

- - - - - - - -

am₁x₁ + am₂x₂≤bm

x₁≥0, х₂≥0

Для построения ОДР вводится на плоскости прямоугольная система координат Х₁ и Х₂.

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

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

Для нахождения искомой точки используется теорема:

Значение целевой функции в точках линии уровня увеличивается, если линию уровня перемещать параллельно начальному положению в направлении нормали, и убывает при перемещении в противоположном направлении.

 

26. Алгоритм решения задачи ЛП с двумя переменными графическим мето­дом.

1) Строится область допустимых решений (ОДР).

2) Если ОДР является не пустым множеством, то строится вектор

n (с₁,с₂), выходящий из начала координат.

3) Перпендикулярно вектору n проводится одна из линий уровня, например: линия уровня, соответствующая уровню с₁х₁ + с₂х₂ = 0

4) Линия уровня перемещается параллельно самой себе в направлении вектора n.

5) Перемещения линии уровня происходит до тех пор, пока у неё не окажется только одна общая точка с ОДР. Эта точка определяет единственное решение задачи и является точкой экстремизма.

6) Находим координаты точки экстремизма и значение целевой функции в ней.


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


<== предыдущая страница | следующая страница ==>
Транспортная задача.| Особые случаи при решении задачи ЛП.

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