9902

Линейное программирование

Реферат

Информатика, кибернетика и программирование

Линейное программирование Линейное программирование (ЛП) - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения 1930 г., А.Н. Толстой - составление оптим...

Русский

2013-03-18

383.5 KB

14 чел.

Линейное программирование

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

1930 г., А.Н. Толстой - составление оптимального плана перевозок, минимизирующего километраж

1931 г., Б. Эгервари - задача о назначениях ("венгерский метод")

1939 г., Л.В. Канторович - систематическое исследование задач ЛП, разработка общих методов (метод разрешающих множителей), применение к решению ряда практических задач

1941 г., Ф. Хичкок - постановка транспортной задачи ЛП, метод последовательного улучшения

1947 г., Дж. фон Нейман – теория двойственности

1947 г., Дж. Данциг – симплекс-метод решения общей задачи ЛП

1949 г., Л.В. Канторович, М.К. Гавурин - метод потенциалов для транспортной задачи ЛП


Общий вид задачи ЛП:

 Z = c1x1 + c2x2 + . . . + cnxn   min (max)

при условиях:

 x1  0, x2  0, . . . , xn  0,

 a11x1 + a12x2 + . . . + a1nxn   (=, ) b1,

a21x1 + a22x2 + . . . + a2nxn   (=, ) b2,

.    .    .    .   .    .    .   .    .    .    .   .

am1x1 + am2x2 + . . . + amnxn   (=, ) bm.

Значения bi, cj, aij - известны (выявлены на стадии анализа реальной ситуации)

В матричных обозначениях

.

Задача ЛП записывается в виде:

 z = CTX  min (max),

при условиях:

 X 0,  

 AX   (=, ) B.


Основные условия, позволяющие строить модели ЛП

1. Пропорциональность

2. Аддитивность

3. Неотрицательность

Пропорциональность означает, что затраты ресурсов на некоторый вид деятельности, а также вклад этого вида деятельности в целевую функцию прямо пропорциональны его уровню (объему)

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

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

Неотрицательность означает, что ни одному из видов деятельности не может быть приписан отрицательный уровень.

 

Каноническая и стандартная формы задач ЛП.     Переход от одной формы к другой

Каноническая форма задачи ЛП:

Z = c1x1 + c2x2 + . . . + cnxn   min (max)

при условиях:

 x1  0, x2  0, . . ., xn  0,

 a11x1 + a12x2 + . . . + a1nxn  = b1,

a21x1 + a22x2 + . . . + a2nxn  = b2,

.    .    .    .   .    .    .   .    .    .   

am1x1 + am2x2 + . . . + amnxn  = bm.

Стандартные формы задачи ЛП:

Z=CTX max,   Z=CTX  min,

AX B,           AX  B,

X  0.        X  0.

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

min Z = - max (-Z).

 Х=А: XA, XA

Дополнительные переменные


Графический метод решения задач ЛП

Графический метод основан на геометрической интерпретации задачи ЛП и применяется в основном при решении задач в двухмерном пространстве.

Рассмотрим задачу ЛП:

z = c1x1 + c2x2  min

при ограничениях

Каждое неравенство  ai2x1 + ai2x2  bi  определяет в плоскости X1ОX2 полуплоскость с граничной прямой  ai2x1 + ai2x2 = bi. Точки, лежащие в полуплоскости, удовлетворяют данному неравенству.

Неравенства  x10 и x20  определяют первый квадрант в системе координат.

Множество точек пересечения всех этих полуплоскостей образует многоугольник решений (область допустимых решений). Каждая точка этого многоугольника есть решение системы ограничений или допустимый план задачи ЛП.


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

Если область допустимых решений пустая, то система ограничений несовместна.

 

   

Характерные черты задач ЛП:

1. Допустимая область всегда является выпуклым многогранником даже в случае, когда она не ограничена

2. Оптимальное решение всегда достигается в вершинах допустимой области

3. Если оптимальное решение не одно, то значение функции совпадает во всех точках-решениях

Задача использования сырья

 Z=50x1+40x2 max

 x10, x20.


Теория линейного программирования

Даны линейная функция:

Z=C1x1+C2x2+…+Cnxn                (1)

и система линейных ограничений:

xj0, (j=1, 2, …, n),       (3)

где аij, bi и Cj – заданные постоянные величины.

Найти такие неотрицательные значения x1, x2,…, xn, которые удовлетворяют системе ограничений (2) и доставляют целевой функции (1) минимальное значение.

В системе ограничений (2) все bi, i=1, 2, …, m, без потери общности можно считать неотрицательными.

В векторной форме:

Z=CX  min 

при ограничениях:

A1x1+A2x2+…+Anxn=A0, X0,       (4)

A1=,  A2=, …, An=,  A0= ,

Определение1. Планом или допустимым решением задачи линейного программирования называется вектор X=(x1, x2, …, xn), удовлетворяющий условиям (2) и (3).

Определение2. План X=(x1, x2, …, xn) называется опорным, если векторы Ai (i=1, 2, …, m), входящие в разложение (4) с положительными коэффициентами xi, являются линейно независимыми.

Замечание. Так как векторы Ai являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не превышает m.

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

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

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


Пусть на плоскости x1Ox2 заданы две точки: A1 (x1(1); x2(1)) и A2 (x1(2); x2(2)), определяющие прямолинейный направленный отрезок .

Координаты произвольной внутренней точки A (x1; x2):

, 10, 20, 1+2=1.       (5)

или:

А=1А1+2А2, 10, 20, 1+2=1.

Точка А, для которой выполняются эти условия, называется выпуклой линейной комбинацией точек А1 и А2.

При 1=1 и 2=0 точка А совпадает с А1, при 1=0 и 2=1 – с А2.

Точки А1 и А2 называются угловыми или крайними точками отрезка .

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

Определение5. Пусть имеется n точек А1, А2, …, Аn. Точка А является их выпуклой линейной комбинацией, если выполняются условия:

А=1А1+2А2+…+nАn, j0 (j=1, 2, …, n), =1.


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

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

Определение7. Точка множества называется граничной, если любой шар с центром в этой точке содержит как точки, принадлежащие множеству, так и точки, не принадлежащие ему. Граничные точки множества образуют его границу.

Определение8. Замкнутым называется множество, содержащие все свои граничные точки.

Замечание. Замкнутое множество может быть ограниченным и неограниченным.

Определение9. Множество называется ограниченным, если существует шар радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество; в противном случае множество называется неограниченным.

Теорема 1. Пересечение выпуклых множеств является выпуклым множеством.

Доказательство. Пусть F = F1F2, F1 и F2 - выпуклые множества. А1, А2 - две произвольные точки в F. А1,А2 F1 и F2 отрезок   F1 и F2, т.к. они – выпуклые множества     F1F2     F  F – выпуклое множество.

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

Выпуклое множество может иметь конечное и бесконечное число угловых точек.

Определение11. Выпуклым многоугольником называется выпуклое замкнутое ограниченное множество на плоскости, имеющее конечное число угловых точек. Угловые точки многоугольника называются его вершинами, а отрезки, соединяющие две вершины и образующие его границу, - сторонами многоугольника.

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

Определение13. Выпуклым многогранником называется замкнутое ограниченное выпуклое множество трехмерного пространства, имеющее конечное число угловых точек. Угловые точки многогранника называются его вершинами; многоугольники, ограничивающие многогранник, - гранями, отрезки, по которым они пересекаются, - ребрами. 

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

Теорема 2. Замкнутый, ограниченный, выпуклый многогранник является выпуклой линейной комбинацией своих угловых точек.

Доказательство. Докажем теорему для многоугольника, имеющего n вершин.

Сначала докажем, что любая точка треугольника удовлетворяет теореме. А - произвольная точка треугольника А1А2А3.

        А1

    

         А    А2

        А4

    А3

    

А   

А=t1А1+t4А4,   t10, t40, t1+t4=1   (*)

А4   

А4=t2А2+t3А3,   t20, t30, t2+t3=1.   (**)

Подставляя (**) в (*):

A=t1A1+t4(t2A2+t3A3)=t1A1+t2t4A2+t3t4A3.

Полагая t1=1, t2t4=2, t3t4=3:

А=1А1+2А2+3А3,

причем

10, 20, 30, 1+2+3=1,

т. е. точка А является выпуклой линейной комбинацией А1, А2, А3.

Выпуклый многоугольник, имеющий n вершин (n>3) разобьем на n–2 треугольника, произвольная точка А попадет в один из них. Без ограничения общности можно положить, что она попала в треугольник А1А2А3. Тогда, как уже доказано, точка А является выпуклой линейной комбинацией трех вершин: А=1А1+2А2+3А3. Поэтому

А=1А1+2А2+3А3+0А4+…+0Аn,

j0 (j=1, 2, …, n), =1,

т. е. точка А является выпуклой линейной комбинацией угловых точек многоугольника.

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

Теорема 3. Множество всех планов задачи линейного программирования выпукло.

Доказательство. Пусть Х1 и Х2 – планы задачи ЛП, т.е.

AX1=A0, X10; AX2=A0, X20,

 

Х=1Х1+2Х2, 10, 20, 1+2=1,

- их произвольная выпуклая линейная комбинация.

Тогда

АХ = А(1Х1+2Х2) = 1АХ1+2АХ2 = 1А0+2А0 =

= (1+20 = А0,

т.е. Х удовлетворяет системе (2).

Т.к. X10, X20, 10, 20, то и Х0, т. е. удовлетворяет и условию (3)  Х тоже является планом задачи ЛП.

Теорема 4. Целевая функция задачи линейного программирования достигает своего минимального значения в угловой точке многогранника решений.

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

Доказательство. Предположим, что многогранник решений К является ограниченным, имеющим конечное число угловых точек.

Пусть X1, Х2, ..., Хр,- угловые точки К, Х0 - оптимальный план задачи ЛП.

Тогда Z(Х0)  Z(X) ХК. Если Х0 – угловая точка, то первая часть теоремы доказана.

Предположим, что Х0 не является угловой точкой; тогда по теореме 2

Х0=1Х1+2Х2+...+pХp, i0 (i=1, 2, …, p), =1.

Так как Z(X) – линейная функция

Z(Х0) = Z(1Х1+2Х2+...+pХp) =

= 1Z(X1)+2Z(X2)+...+pZ(Xp)   (*)

Пусть т = Z(Хk) – наименьшее из Z(Хi) (i=1,2, ..., р) в разложении (*), Xk  – одна из угловых точек.

Заменим в (*) каждое Z(Хi) на m.

Тогда  Z(X0)  1m + 2m +...+ pm = т= m,

так как i0, =1.

Т.е. Z(X0)  т, но по предположению Х0 – оптимальный план, т.е. Z(X0)  т, следовательно Z(X0) = т = Z(Xk), где Xk – угловая точка.

Для доказательства второй части теоремы допустим, что Z(X) принимает минимальное значение более чем в одной угловой точке, например в X1, Х2, ..., Хq, 1<qр; тогда Z(X1)=Z(Х2)=...=Z(Xq)=т.

Пусть

Х = 1Х1+2Х2+...+qХq, i0 (i=1,2,…,q), =1,

тогда

Z(Х0) = Z(1Х1+2Х2+...+qХq) =

= 1Z(X1) + 2Z(X2) +...+ qZ(Xq) =

= 1m + 2m +...+ qm = т = m,

т. е. целевая функция Z принимает минимальное значение в произвольной точке X, являющейся выпуклой линейной комбинацией угловых точек X1, Х2, ..., Хq.

Замечание. Если многогранник решений является неограниченной областью, то не каждую точку области можно представить выпуклой линейной комбинацией угловых точек области. Задачу ЛП с многогранником решений, представляющим собой неограниченную область, можно привести к задаче с ограниченной областью, вводя дополнительное ограничение x1+x2+...+xпQ, где Q – достаточно большое число.

Теорема 5. Если известно, что система векторов A1,А2,..., Ak (kп) в разложении (4) линейно независима и такова, что

A1x1 + А2x2 + ... + Akxk = А0,

где все xj0, то точка Х=(x1, x2, ..., xk, 0, …, 0) является угловой точкой многогранника решений.

Здесь Хn-мерный вектор, последние п-k компонент которого равны нулю.

Доказательство. Предположим, что точка Х не является угловой. Тогда

Х=1Х1+2Х2, 10, 20, 1+2=1,

где X1 и Х2 – некоторые точки многогранника решений.

Очевидно, что

Х1=(x1(1), x2(1), …, xk(1), 0, …, 0),

Х2=(x1(2), x2(2), …, xk(2), 0, …, 0).

Поскольку X1 и Х2 – планы, то

A1x1(1) + A2x2(1) +…+ Akxk(1)=A0,   

A1x1(2) + A2x2(2) +…+ Akxk(2) =A0

Вычитая из первого соотношения второе:

(x1(1)-x1(2))A1 + (x2(1)-x2(2))A2 + … + (xk(1)–xk(2))Ak = 0.

По предположению, векторы A1, А2, ..., Ak линейно независимы, поэтому последнее соотношение выполняется, если

x1(1)-x1(2) = 0;  x2(1)x2(2) = 0; … ;  xk(1)xk(2) = 0.

Отсюда x1(1)=x1(2); x2(1)=x2(2); …; xk(1)=xk(2).

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

Теорема 6. Если Х=(x1, x2, ..., xn) - угловая точка многогранника решений, то векторы в разложении (4), соответствующие положительным xi являются линейно независимыми.

Доказательство. Без ограничения общности можно положить не равными нулю первые k компонент вектора X, так что

= A0.

Допустим, что система векторов A1, А2, ..., Ak линейно зависима. Тогда существуют такие числа l1, l2, ..., lk, не все равные нулю, при которых выполняется соотношение

l1A1 + l2А2 + ... + lkAk = 0.         (*)

По условию,

x1A1 + x2А2 + ... + xkAk = A0.        (**)

Зададим некоторое число >0, умножим на него равенство (*); прибавляя и вычитая результат из (**), получим:

(x1+l1)A1 + (x2+l2)A2 + … + (xk+lk)Ak = A0,

(x1 - l1)A1 + (x2 - l2)A2 + … + (xk - lk)Ak = A0.

Т.е. система уравнений (4) имеет два решения, которые могут и не быть планами:

Х1=(x1+l1; x2+l2; …; xk+lk; 0; …; 0),

Х2=(x1 - l1; x2 - l2; …; xk - lk; 0; …; 0).

Так как все xi>0, то число можно выбрать настолько малым, что все первые k компонент Х1 и Х2 примут положительные значения, тогда Х1 и Х2 - планы.

При этом 0.5Х1 + 0.5Х2 = X,

т. е. Х - выпуклая линейная комбинация точек Х1 и Х2, что противоречит условию теоремы о том, что Х - угловая точка.

Итак, допущение, что система векторов A1, А2, ..., Ak линейно зависима, привело к противоречию. Следовательно, сделанное допущение неверно и система векторов линейно независимая.

Следствие1. Так как векторы A1, А2, ..., An имеют размерность т, то угловая точка многогранника решений имеет не более чем т положительных компонент.

Следствие2. Каждой угловой точке многогранника решений соответствует kт линейно независимых векторов системы A1, А2, ..., An.

Не теряя общности, можно предположить, что система векторов A1, А2, ..., An задачи линейного программирования (1) - (3) всегда содержит т линейно независимых векторов. Если при решении частной задачи это свойство не очевидно, то первоначальную систему векторов дополняют т линейно независимыми векторами, затем находят решение расширенной задачи.


Итак, если целевая функция задачи линейного программирования ограничена на многограннике решений, то:

1) существует такая угловая точка многогранника решений, в которой целевая функция задачи линейного программирования достигает своего оптимума;

2) каждый опорный план соответствует угловой точке многогранника решений.

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


(2
)


 

А также другие работы, которые могут Вас заинтересовать

35150. Виртуальные частные сети. Архитектура и протоколы 42.5 KB
  VPN англ. В зависимости от применяемых протоколов и назначения VPN может обеспечивать соединения трёх видов: узелузел узелсеть и сетьсеть. Уровни реализации Обычно VPN развёртывают на уровнях не выше сетевого так как применение криптографии на этих уровнях позволяет использовать в неизменном виде транспортные протоколы такие как TCP UDP. Пользователи Microsoft Windows обозначают термином VPN одну из реализаций виртуальной сети PPTP причём используемую зачастую не для создания частных сетей.
35151. Методы повышения надёжности хранения данных. Технология RAID 50.5 KB
  Технология RID Одна из причин ведущих к утрате информации аппаратные сбои и поломки. RID это акроним от Redundnt rry of Independent Disks. Этим набором устройств управляет специальный RIDконтроллер контроллер массива который инкапсулирует в себе функции размещения данных по массиву; а для всей остальной системы позволяет представлять весь массив как одно логическое устройство ввода вывода. В зависимости от уровня RID проводится или зеркалирование или распределение данных по дискам.
35152. Цели и задачи администрирования 25 KB
  чтобы предоставить пользователям ИС наилучшее возможности по эффективному использованию ресурсов ИС при объективных ограничениях. 3 квалифицируемая помощь пользователям. Здесь задача состоит в том чтобы реализовать в ИС выбранную стратегию ИБ на базе 1 или нескольких политик безопасности обеспечить использование ИС только санкционированным пользователям предусмотреть резервное копирование и восстановления отдельных ресурсов или всей ИС.
35153. Сетевое администрирование. Основные понятия. Сетевые ОС 26.5 KB
  Компьютерные сети – это совокупность компьютеров связанных коммуникационной системой необходимым программным обеспечением позволяющей пользователям и приложениям получить доступ к ресурсам компьютеров сети. клиентская часть средство запроса на доступ к удаленным серверам транспортные средства сетевой ОС обеспечивающие передачу доступных между компьютерами Среди компонентов сети выделяют сетевые службы – это программные модули работающие в установленном режиме которые предоставляют доступ к конкретным ресурсам компа через сеть....
35154. Модели управления доступом к ресурсам 27 KB
  Основными компонентами ролевой модели разрешения права пользователя Разрешение – определяет тип доступа к объекту или его свойству дается пользователям или группам . разрешения применяются к защищенным объектам Рекомендуется назначать разрешения группам. Существуют группы разрешений которые являются основными или обязательными чтение разрешения смена разрешения смена владельца удаление разрешения Существует специальный вид разрешения – владения которое назначается при создании объектов. Какие бы разрешения не были установлены для...
35155. Администрирование сетей Microsoft. Средства анализа состояния сети в Windows 29 KB
  Средства анализа состояния сети в Windows. Базовые принципы: 1 необходимо иметь точную схему и документацию сети: текущая топологическая схема подробная информация обо всем его сетевом оборудовании его конфигурации и использующихся протоколах IPадресах каналах связи WU сервера и сегментах пользовательских локальных сетей. 2 перед изменениями в сети а так же после этих изменений необходимо оценивать работу в сети для того чтобы делать выводы об отрицательном или положительном влиянии внешних изменений . В Windows отдается приоритет...
35156. Службы каталогов. Пространство имен X.500 и протокол LDAP 30 KB
  Службы каталогов. Основная цель объединения компов в вычислительную сеть это обеспечение совместного использования ресурсов при администрировании вычислительной сети 1 из основных задач это реализация оптимального метода организации общих ресурсов одним из методов эффективного управления множеством ресурсов и множеством потребителей вычислительной сети является разветвленная служба каталогов Служба каталогов – это сетевая служба позволяющая получать доступ без знания точного местоположения ресурса При использовании службы каталогов вся...
35157. Active Directory. Доменная модель службы каталогов. Контроллеры домена. Возможные типы серверов в домене 33.5 KB
  Возможные типы серверов в домене. D помогает управлять как принтерами так и крупными специализированными серверами работающими одновременно в нескольких сетях С помощью D осуществляют манипулирование многими компонентами службы каталогов. В D каждый сервер содержит не менее 3 КИ: 1 КИ – это логическая структура 2 КИ – конфигурация 3 КИ – 1 или несколько пользовательских контейнеров Это поддеревья объединенные в катало объектов Доменная модель служб каталогов В D 1 из важных вещей домен – это совокупность компонентов характеризующихся...
35158. Active Directory. Схема каталога. Репликация данных. Управление службой Active Directory 34 KB
  Схема каталога. Управление службой ctive Directory Любой объект каталога принадлежит к некоторому классу объектов со своей структурой атрибутов. Определения всех классов объектов и совокупности правил позволяющих управлять структурой каталога хранится в специальной иерархической структуре – схеме каталога. Схема каталога хранится в отдельном разделе и допускает возможность расширения.