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
)


 

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

3730. Штукатурные работы и материалы для штукатурки 93.5 KB
  Введение Общее назначение штукатурок – заполнение стыков, швов на поверхности основания, обеспечение защитного или декоративного защитного покрытия на нем. Штукатурки могут применяться в порядке исключения при отделке помещения в местах, где пр...
3731. Основы экологии 191.5 KB
  Основы экологии Что такое экология? Наука об условиях жизни организмов и их взаимных связях со средой. Экология - это наука об организмах , наука о взаимоотношениях между живыми организмами и их сообществами, с окружающей их живой и неживой средой о...
3732. Основные закономерности развития человеческого сознания и интеграция знаний 48 KB
  Человек владеет прекрасным даром - разумом с его пытливым полётом, как в отдаленное прошлое, так и в грядущее, миром мечты и фантазии, творческим решением практических и теоретических проблем, наконец, воплощением самых дерзновенных замысл...
3733. Состав и свойства целофана 75.5 KB
  Введение Целлофан - это прозрачная гидратцеллюлозная (вискозная) пленка, полученная из вискозы. Целлофан является наиболее дешевым и распространенным упаковочным пленочным материалом, производится во всем мире в очень больших количествах. Лакированн...
3734. Расчет многопластинчатого ротационного компрессора 399 KB
  Исходные данные Холодопроизводительность, Вид компрессора: многопластинчатый ротационный. Построим цикл холодильной машины в диаграмме i - Lg(P). Параметры основных точек сведем в таблицу
3735. Химическая термодинамика. Термохимия, термохимические уравнения. 30.5 KB
  Химическая термодинамика. Термохимия, термохимические уравнения. Экзотермические и эндотермические реакции. Приведите примеры. Химическая термодинамика – это раздел химии, изучающий энергетику химических реакций, а так же факторы и критерии, оп...
3736. Библия как памятник культуры. Структура Ветхого завета 51.5 KB
  Библия по праву считается Книгой Книг. Она неизменно занимает 1-е место в мире по чтимости и читаемости, общим тиражом, частоте издаваемости и переводам на другие языки. О значении ее для верующих христиан вообще говорить не приходится. Библия –...
3737. Фондовая Биржа 93.5 KB
  Введение Главной задачей, поставленной при написании работы стало изучение и освещение ключевых элементов, дающих общий обзор фондового рынка, как целого обособленного организационно-оформленного рынка, как посредника в организации хозяйственных свя...
3738. Суть фінансів, їх функції та роль 65.5 KB
  Виникнення та розвиток фінансів зумовлювалися зростанням продуктивних сил у суспільстві, насамперед товарно-грошових відносин як необхідної форми економічного життя для досягнення певного рівня суспільного добробуту. Своїй досконалості й завер...