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
)


 

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

45581. Должностные обязанности специалиста по рекламе коммерческой компании. Формы и способы взаимодействия с рекламными агентствами 27.5 KB
  Задача агентства со своей стороны заключить договора со всеми партнерами собрать все отчеты фотоотчеты эфирные справки экземпляры газет и т. Агентство несет ответственность перед заказчиком за все выходы рекламы заказчика и за своевременность этих выходов. Агентство сохраняет все объемные скидки заказчика а иногда и увеличивает. Для принятия правильных решений или при разработке рекламной стратегии всегда необходим взгляд со стороны.
45582. Рекламные агентства: задачи, структура, специализация. Бизнес рекламного агентства 68 KB
  Рекламные агентства: задачи структура специализация. Бизнес рекламного агентства. Рекламные агентства можно классифицировать по многим признакам. По характеру выполняемой работы: Агентства полного цикла; Дизайнстудии творческие мастерские; Медийные агентства.
45583. Общая характеристика рекламного рынка России 50.5 KB
  Скопировано же самое что и в билете про агентства т. Рекламные агентства можно классифицировать по многим признакам. По характеру выполняемой работы: Агентства полного цикла; Дизайнстудии творческие мастерские; Медийные агентства.По географическому признаку: Региональные агентства; Общенациональные агентства; Международные агентства; Глобальные агентства.
45584. Формирование системы периодических изданий в России XVIII в 29.5 KB
  2 блока: Государственная Частная Первые полвека монополизирована правительством: Ведомости Журналистика Академии Наук СПб Ведомости –первая русская регулярная газета: 2 раза в неделю Первый русский журнал Примечания к СПбВедомостям: научнопопулярный.– Трудолюбивая пчела Сумарокова драматург первый директор русского театра– выходит меньше года правительство закрывает за критику Екатерины; Праздноевремя с пользой употребленное сухопутный шляхетный корпус – два года: первый– литература; второй – критический Екатерина...
45585. Русская газета второй половины XIX в 42.5 KB
  60е годы Резкое политические размежевание Типологический рост колич и кач – много газеткуча специализированных 7090е Консерваторы: Катков Гражданин Мещерского Новое время Суворина: крупнейшее.11 В связи с этим большинство изданий особенно газеты приобрели более или менее определенную политическую направленность выражали убеждения и интересы той или иной социальной группы. С ростом городов и грамотности их населения расширялся контингент читателей газет за счет мелких служащих купцов ремесленников прислуги.
45586. СМИ Советской России 1920-1940-х гг 33.5 KB
  Гражд война нэп-национализация Гражданска явойна: Декрет о печати Ленина:закрытие контрреволюционных изданий Новое время Русское богатство Государственная монополия на бумагу на объявления Гражд война –противостояние красной Красны кавалерист Бабель белой печати С 1917 года – первые советские издания:Беднота для крестьян Жизнь национальностей сталин в редколлегии Гудок жд Создание однопартийной системы НЭП: vРазрешили частную инициативу: Дом искусств Экономический журнал 1922 год обвал тиражей кризис Дотации...
45587. Эволюция системы СМИ СССР в 1950-1990-х гг 46.5 KB
  В ней регул печ обзорыпечати они были одной из форм парт руква прессой. Критич статьи и обзорыпечати обязательно перепеч изданиями кот критиковались с признаниемправильности высказанных замечаний. Причины: необх усиления идейного содержания печати и повышенияее роли в полит.импульсдля развития печати.
45588. Общее понимание коммуникации. Фундаментальные вопросы о сущности коммуникации 33.5 KB
  Коммуникация: Коммуникация – взаимодействие между людьми посредством знаков размещённых в презентационных репрезантационных технических средствах распространяемых по определённым каналам в соответствии с выбранным кодом. Коммуникация для нас – взаимодейсвие субъект-субъектного типа. Коммуникация будет таковой при условии что информации имеет смысл для обоих субъектов=субстанция информационной природы.
45589. Виды и типы социальных коммуникаций: методологические подходы и основные классификации 42 KB
  Социальная коммуникация – это процесс в котором участвуют как минимум 2 социальных субъекта причём наличествует как факт передачи так и факт приёма информации причём со стороны источника передача осуществляется интенционно намеренно вербально невербально а со стороны получателя происходит приём этой информации как в осозновании так и вне осозновании.Неполноценная вырожденная ком.Мин колво участников – 2 – полноценная социальная комм.