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
)


 

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

28898. Взаимоотношения Руси с соседними государствами и народами 22.5 KB
  Взаимоотношения Руси с соседними государствами и народами. Важное место занимали отношения с Византией которая являлась источником ресурсов для Руси. После крещения Руси Византия стала восприниматься как духовный центр христианства. Хазары контролировали Волжский торговый путь и выступали в двойной роли: с одной стороны препятствовали свободным торговым отношениям Руси; с другой – выступали буфером между Русью и кочевниками.
28899. Удельный период в истории России (XII—XV вв.) 28.5 KB
  К середине XII века Русь раскололась на 15 княжеств которые были лишь в формальной зависимости от Киева. Феодальная раздробленность ослабляла Русь. В начальной стадии древнерусское государство распалось на 3 основные области: СевероЗападная Русь. Северовосточная Русь.
28900. Борьба за независимость русских земель против агрессии с Востока и Запада (XIII век) 27 KB
  Следствием этого явилось отставание России от Запада. Последствия нашествия: сократилось население страны; разделение городов подорвано городское ремесло; разрушены памятники духовенства и материальной культуры; особое последствие нашествия на истории России сказались в том что оно заложило азиатский способ власти в России.
28901. Культура Древнерусского государства 27.5 KB
  Достаточно продолжительное время на Руси сохранялось двоеверие что сыграло огромную роль в складывании культурного потенциала отражавшего в себе некую двойственность. Долгое время считалось что письмо на Руси появилось с принятием христианства. Но есть доказательства существования письменности задолго до этого: договоры Руси с Византией относящиеся к первой половине X века имели копии на славянском языке. Христианизация Руси просто дала толчок развитию письменности.
28902. Возвышение Москвы и завершение формирования Российского централизованного государства (XIV–XVI вв.) 29.5 KB
  Внешняя угроза ускоряла процесс объединения русских земель. Однако к середине XIV века складывается и другой центр объединения русских земель Великое ЛитовскоРусское княжество. На заключительном этапе объединения русских земель наиболее острой была борьба с Новгородской олигархической республикой. Этим в основном завершилось политическое объединение русских земель.
28903. Эпоха Ивана Грозного 28.5 KB
  Боярское правление привело к ослаблению центральной власти и вызвало большую волну недовольств и открытых выступлений. Страна нуждалась в реформах по укреплению государственности централизации власти. Во время царствования Ивана IV возник новый орган власти – Земский собор который занимался решением важнейших государственных дел вопросами внешней политики финансами. Это достигалось вопервых усилием роли центральных органов приказов вовторых редким ограничением власти наместников.
28904. Новое время в мировой истории 24.5 KB
  Эти понятия в исторической науке прочно закрепились до настоящего времени. Среди других событий которые принимаются в качестве исходного рубежа Нового времени называют события связанные с Реформацией 1517 открытие испанцами в 1492 году Нового Света[1] падение Константинополя 1453 или даже начало Великой Французской революции 1789. Ещё сложнее обстоят дела с определением времени окончания данного периода. Отстававшая до этого времени по ряду показателей от стран Востока европейская цивилизация в XVI в.
28905. Общественно-политические процессы в СССР в 1945—1985 гг. 44 KB
  Центр власти перемещался в секретариат ЦК КПСС т. ЦК КПСС стал превращаться в коллективный орган. они предприняли попытку сместить Хрущева с поста Первого секретаря ЦК КПСС. В дальнейшем власть все более концентрировалась в руках Первого секретаря ЦК КПСС.
28906. Социально-экономическое положение страны (1945—1984 гг.) 43 KB
  Социальноэкономическое положение страны 1945 1984 гг. Жилой фонд страны вырос за годы семилетки 19591965 на 40. политическое развитие страны было противоречивым.