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

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

Читайте также:
  1. FAST (Методика быстрого анализа решения)
  2. I Психологические принципы, задачи и функции социальной работы
  3. I. 1.1. Пример разработки модели задачи технического контроля
  4. I. 1.2. Общая постановка задачи линейного программирования
  5. I. 2.1. Графический метод решения задачи ЛП
  6. I. 3.1. Двойственная задача линейного программирования
  7. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  8. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  9. I. Значение и задачи учета. Основные документы от реализации продукции, работ, услуг.
  10. I. ОСНОВНЫЕ СПОСОБЫ ПЕРЕДВИЖЕНИЯ И ПРЕОДОЛЕНИЯ ПРЕПЯТСТВИЙ
  11. I. Открытые способы определения поставщика.
  12. I. Решение логических задач средствами алгебры логики

Дана задача линейного программирования:

или в краткой форме:

Среди допустимых решений системы (1.2) найти то, которое обращает в максимум линейную форму (1.1).

Уравнение

на плоскости х1Ох2 определяет прямую, разбивающую всю плоскость на две полуплоскости, каждая из которых лежит по одну сторону от прямой. Прямая (1.4) называется граничной и принадлежит обеим полуплоскостям.

Координаты точек, лежащих в одной полуплоскости, удовлетворяют неравенству
,

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

Следовательно, системе неравенств (1.2) удовлетворяет множество точек Х (х1, х2 ), лежащих в пересечении полуплоскостей, заданных неравенствами системы.

Пересечение конечного числа полуплоскостей есть некоторая выпуклая многоугольная область Ω, которая называется областью решения системы (1.2). Если система (1.2) противоречива, область Ω пуста. Поставленную задачу (1.1) - (1.3) можно теперь сформулировать следующим образом: среди всех точек многоугольной области Ω найти ту, которая обращает в максимум линейную форму

Выбрав произвольное с 0, запишем уравнение прямой из семейства параллельных прямых, нормальных вектору

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

в положительном направлении вектора .

Очевидно, решением задачи на максимум линейной формы является наиболее удаленная крайняя точка, в которой прямая (1.8) встречается с областью Ω. Если же задача линейного программирования сформулирована на минимум линейной формы, то решением задачи будет первая точка, в которой прямая

встречается с областью Ω при параллельном перемещении в направлении вектора

Аналогично геометрически интерпретируется задача линейного программирования и в n -мерном пространстве

 

Каждое неравенство ai1x1+ai2x2+…+ainxn ≤ bi определяет в n-мерном пространстве полупространство, состоящее из точек X(x1, x2, …xn), расположенных по одну сторону от граничной гиперплоскости ai1x1+ai2x2+…+ainxn ≤ bi и на самой этой гиперплоскости. Пересечение конечного числа полупространств есть выпуклая многогранная область Ω, которая является множеством всех решений системы ограничений записанной задачи.

Значение линейной формы в точке Х' (x'1, x'2, …, x'n) можно рассматривать как уклонение точки Х'(x'1, x'2, …, x'n) от гиперплоскости

= 0,

где под уклонением данной точки от гиперплоскости следует понимать число, полученное в результате подстановки в левую часть уравнения (1.9) вместо x1, x2, …, xn координат точки Х'. Геометрическая интерпретация задачи линейного программирования заключается в отыскании на множестве решений Ω* такой крайней точки, которая наименее (наиболее) уклонена от гиперплоскости (1.9).

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)