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

И особенности ее решения

Читайте также:
  1. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  2. I. Рвота, причины рвоты. Особенности ухода при рвоте: пациент без сознания, в сознании, ослабленный. Возможные осложнения.
  3. II Съезд Советов, его основные решения. Первые шаги новой государственной власти в России (октябрь 1917 - первая половина 1918 гг.)
  4. III. Психические свойства личности – типичные для данного человека особенности его психики, особенности реализации его психических процессов.
  5. IV. Особенности правового регулирования труда беременных женщин
  6. V. Особенности развития предпринимательства
  7. V3: Основные черты и особенности политики военного коммунизма
  8. А. Основные особенности административной ответственности коллективных субъектов (организаций)
  9. Аграрная реформа 1861 г., ее механизм и особенности проведения в белорусских губерниях.
  10. Агрегатный индекс цен: особенности построения с учетом разных весов
  11. Административно-правовые отношения. Особенности административно-правовых отношений.
  12. Административное принуждение как один из административно – правовых методов. Понятие и особенности административного принуждения.

, i=1, 2, …, n. (6.1)

D: , j=1, 2, …, r. (6.2)

Целевая функция (6.1) линейна по Х, и все функциональные ограничения (6.2) линейны по Х. Так как в задачах линейного программирования , т.е. целевая функция не имеет точек максимума внутри области D, то решение задачи (6.1) и (6.2) может быть только на границах этой области. В силу линейности ограничений (6.2) множество D является многогранником (в двумерном случае n =2 - многоугольником), а решением задачи является либо одна из вершин многогранника, либо одна из его граней. Заметим, что n – количество переменных в условии задачи определяет размерность многогранника множества D, а r – количество функциональных ограничений определяет количество граней многогранника.

Эти особенности определяют методы решения задачи.

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

Задачи линейного программирования для целевой функции двух переменных f 0(X) = f 0 (X 1, X 2), удобно решать графически.

 

Рассмотрим пример:

 

Рис. 6.1

f 0 (X 1, X 2) =

Из условия задачи следует n = 2, r = 3, то есть область допустимых значений варьируемых переменных D представляет собой треугольник (рис. 6.1.), сторонами которого являются отрезки прямых -X 1 - 1 =0; - X 2 - 1 = 0;

X 1 + X2 – 2 = 0, а вершинами, точки пересечения этих прямых (точки А, В, С).

Строим вектор градиента , для чего определяем значения его проекций на оси X 1, X 2.

,

Строим линию равного уровня целевой функции, перпендикулярно к направлению градиента и переносим ее параллельно самой себе по направлению градиента, до тех пор, пока она не пройдет через крайнюю точку области D (точка С на рис 6.1).

Определяя координаты точки С, как точки пересечения двух прямых, находим решение задачи.

, откуда

Последовательность решения задачи линейного программирования графическим методом.

1.Построить многоугольник D на плоскости с осями X 1, X 2

2. Определить направление градиента , для чего рассчитать проекции вектора градиента , на оси X 1 и X 2.

Построить вектор градиента целевой функции , и перпендикулярную ему линию равного уровня.

3. Перенести линию равного уровня параллельно самой себе по

направлению градиента, так, чтобы она проходила через крайнюю точку области D.

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

Значения этих координат и являются решением задачи.

Если линия равного уровня параллельна стороне многоугольника D, ограничивающей его в направлении градиента, то решением служит любая точка этой стороны.

Задачу линейного программирования с размерностью больше двух (n>2) решают симплекс-методом в соответствии со следующей последовательностью:

1.Определяются координаты одной из вершин многогранника ограничений D.

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

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


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 | 47 | 48 | 49 | 50 |

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



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