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



Формулировка и различные формы записи задачи линейного программирования. Найти вектор X=(x1,x2,…,xn), который удовлетворяет системе линейных ограничений и обеспечивает экстремальное (минимальное или максимальное) значение целевой функции. Ограничения могут быть сформулированы в виде равенств или неравенств. В зависимости от этого различают различные формы записи задач линейного программирования. 1. Общая форма записи ЗЛП. Дано: система линейных ограничений, в которой S равенств и (m-S) неравенств (2) (3) Требуется найти такое решение системы (1) X=(x1,x2,…,xn), которое удовлетворяет условию (2), и на котором целевая функция достигает экстремума (максимума или минимума). 2. Симметричная форма. В ней ограничение (1) содержит только неравенства (3) (1)     i=1,2,…,m (2)   (3) (1)     i=1,2,…,m (2) 3. Каноническая форма. Ограничение (1) содержит только равенства (3)    (1)     i=1,2,…,m (2)     Определение. Вектор X=(x1,x2,…,xn), координаты которого являются решением ограничений (1) и (2), называется допустимым решением ЗЛП. Множество всех допустимых решений задачи называется областью допустимых решений (ОДР). Допустимое решение X, на котором целевая функция достигает максимума или минимума, называется оптимальным решением задачи.   2) Переход от одной формы записи задачи к другой. Теорема. Пусть дано линейное неравенство с n переменными  (4) И переменная                  такая, что ,                       (6) тогда . Доказательство: (достаточность)→: Пусть X=(α1, α 2,…, α n) – решение (4), т.е.                                  (4’) Введём αn+1 =bi- ,                                                                      (5’) при этом .                                                                           (6’) Пусть выполняется (5’) и (6’). Отбросив в левой части уравнения (6’) , получим неравенство (4’). Теорема позволяет от неравенств в системе ограничений перейти к уравнениям и, наоборот, от уравнения перейти к неравенству.   3) Графический метод решения задачи линейного программирования. Этот метод имеет ограниченную область применения. Этим методом можно решать следующие задачи: 1) Задачи с двумя переменными, имеющими симметричную форму записи. 2) Задачи с n переменными, имеющие каноническую форму записи, если выполняется условие n-r≤2, где n – число неизвестных, r – ранг системы линейных уравнений (1). Задача типа 2 сводится к задаче типа 1, для чего нужно перейти от канонической к симметричной форме записи. Рассмотрим решение задач типа 1. Найти X=(x1,x2), который является решением (1), удовл. (2),   (2) x1≥0, x2≥ 0 и на котором целевая функция f(X)=c1x1+c2x2        (3) достигает экстремума (максимума или минимума). Решение задачи содержит два этапа:         I. Построим ОДР (7)  Решением такого неравенства является любая пара чисел (x1;x2), которая при подстановке в (7) обращает его в верное числовое равенство.     ***На координатной плоскости (x1;x2) – точка . Множество решений (7) – некоторое множество точек на x1Ox2. Выясним, какую область на плоскости x1Ox2 образуют точки, которые являются решением ограничений (1) и (2).            Заменим неравенство (7) соответствующим ему равенством. -   (8)  это уравнение определяет на плоскости x1Ox2 прямую линию. Эта линия делит плоскость x1Ox2 на 2 полуплоскости π1 и π2. Утверждение. Точки одной из этих полуплоскостей являются решением ,                              а точки другой полуплоскости являются решением неравенства . (**) Нахождение ОДР оптимального решения задачи. Рассмотрим уравнение                (3) При конкретном значении f это уравнение определяет на плоскости прямую линию. При изменении f мы получим семейство параллельных прямых (прямые ||, т.к. они все имеют один угловой коэффициент ). Каждую из этих прямых называют линией уравнения, т.к. согласно равенству (3) на каждой такой прямой функция f сохраняет постоянное значение. Определение. Линия уровня, имеющая общие точки с ОДР и расположенная так, что ОДР целиком находится в одной из полуплоскостей, на которые данная линия уровня делит координатную плоскость, называется опорной прямой. Чтобы найти ОДР оптимального решения, выполним: 1- Строим  в начале координат. 2- Перпендикулярно  проводим одну из линий уровня, имеющую общие точки с ОДР. 3- Перемещая эту линию уровня в направлении  в задаче на max или в противоположном направлении в задаче на min, находим опорную прямую. 4- Совместно решив уравнения прямых, ограничивающих ОДР и имеющих общие точки с опорной прямой, найдем оптимальное решение. В зависимости от вида ОДР и целевой функции задача может иметь единственное решение, бесконечное множество решений, или не иметь решений ввиду несовместности системы ограничений или неограниченности целевой функции ОДР. 4) Преобразование однократного замещения.    Пусть дана система линейных уравнений (1) r<n (ранг системы) Приведём эту систему к разрешённому виду методом Жордано-Гаусса и выпишем общее решение системы (общее решение системы – это формулы, выражающие базисные неизвестные через свободные). Общее решение(1’) Положив в этих формулах значение всех свободных неизвестных, равных нулю, мы найдём базисное решение системы. Исходная система (1) будет иметь не одно базисное решение, т.к. из n неизвестных можно составить разные наборы из r неизвестных, но не каждый такой набор из r неизвестных можно взять за базисные неизвестные, т.к. среди r векторов коэффициентов при этих неизвестных могут быть линейно зависимые и, следовательно, базиса из них составить нельзя. Если мы знаем какое-либо одно базисное решение, то, преобразовав систему от одного единичного базиса к другому, можем найти любое другое базисное решение системы. Пример. Дана система линейных уравнений, приведённая к единичному базису. Требуется преобразовать её к какому-либо другому единичному базису.  Для того чтобы найти какой-либо другой единичный базис, возьмём за разрешающий элемент любой неравный нулю коэффициент при каком-либо свободном неизвестном и выполним одну итерацию методом Жордано-Гаусса. Свободное неизвестное x3 стало базисным, а базисное неизвестно x1 стало свободным. Такое преобразование называется преобразованием однократного замещения, т.к. произошло замещение базисного неизвестного x1 свободным неизвестным x3. Т.о. данная система уравнений преобразована к новому единичному базису, в котором вектор-коэффициенты при x3,x4,x5. Последовательно выполняя преобразования однократного замещения, можно найти все базисы векторов коэффициентов и все базисы решений данной системы. Замечание. Для данной системы уравнений нельзя в качестве базисных неизвестных взять набор x1,x2,x4, т.к. им соответствуют вектор-коэффициенты , которые линейно зависимы, т.к. А1-А2-3А4=θ.   5) Опорные решения. Отыскание исходного опорного решения. Определение.  Опорным решением системы линейных уравнений называется базисное допустимое решение (для которого векторы условий, соответствующие положительным координатам, линейно независимы). Отыскание исходного опорного решения рассмотрим на примере. Теорема: если в системе линейных уравнений выполнить однократное замещение с разрешающим элементом ak4, то все свободные члены уравнений системы останутся неотрицательными. Замечание. Для того чтобы найти исходное опорное решение системы линейных уравнений, надо привести систему к разрешённому виду. Если при этом все свободные члены уравнений системы будут «≥0», то базисное решение будет опорным. Если среди свободных членов уравнений разрешённой системы есть отрицательные, то следует выполнить преобразования 1) и 2). Пусть после выполнения этих преобразований все свободные члены уравнений стали неотрицательными, но i-е уравнение системы стало неразрешённым; выберем s-й столбец в таблице по положительному элементу ais>0 в i-й строке. Найдём разрешающий элемент, согласно (*), при этом может оказаться: 1. Разрешающий элемент aks оказался в i-й строке, т.е. k=i. Выполним однократное замещение с разрешающим элементом ais, тогда i-е уравнение системы станет разрешающим относительно xs, и все свободные члены уравнений системы будут неотрицательными, и мы сможем выписать исходное опорное решение. 2. Разрешающий элемент i-й строке, , при этом bk>0. Выполним однократное замещение с разрешающим элементом aks. При этом свободный член i-го уравнения уменьшится, но i-е уравнение останется неразрешённым, но свободный член уменьшится. После конечного числа шагов придём к случаю 1., либо в i-м не останется положительных коэффициентов при неизвестных, что означает несовместность системы в ОДР, либо придём к случаю 3. 3.  Поэтому, прежде чем выполнять преобразование однократного замещения с разрешающим элементом aks, нужно попробовать выбрать другой разрешающий столбец по другому положительному элементу в i-й строке. Если это сделать нельзя, то нужно выполнить однократное замещение с разрешающим элементом aks, тогда изменится состав базисных неизвестных, и выбор разрешающего элемента нужно будет начинать сначала. Через конечное число шагов придём к случаям 2. или 1., либо установим несовместность системы уравнений в ОДР.   6) Область допустимых решений n-мерной задачи линейного программирования. Гиперплоскость. Полупространство. Выпуклые множества. При анализе систем линейных уравнений с n неизвестными широко используется понятие n-мерных векторов или точек n-мерного пространства. Введём n-мерное векторное (линейное) пространство Rn. Элементами этого пространства являются возможные наборы из n действительных чисел, взятых в определённом порядке.  - вектор или точка пространства Rn. x1,x2,…,xn – координаты вектора или точки.      В Rn определяются операции сложения элементов и умножения элементов на число. I. X+Y=(x1+y1,x2+y2,…,xn+yn)       II. 1) Вводится вектор-нуль θ=(0,0,…,0) 2) вектор, противоположный X (-X): X+(-X)=θ. 1) ***Операции I и II обладают следующими свойствами: Коммутативность X+Y=Y+X. 2) Ассоциативность сложения X+(Y+Z)=(X+Y)+Z. 3) Ассоциативность умножения , с1,c2 – действительные числа. 4) Дистрибутивность А) векторная    Б) скалярная По аналогии с двух- и трёхмерными векторами в Rn можно ввести понятие скалярного произведения           Наличие скалярного произведения в Rn позволяет ввести понятие длины вектора и расстояния между элементами Rn. Длиной вектора (его модулем) наз. « » из скалярного квадрата.    A(x1,x2,…,xn) – каждый из которых является решением линейного уравнения относительно n переменных, называется гиперплоскостью.                  A(x1,x2,…,xn) – называется полупространством, расположенным по одну сторону от граничной гиперплоскости. - коллинеарные             Параметрическое уравнение прямой m -                               (*) Если , то (*) определяет прямую линию  - радиус-вектор точки А из Rn  - радиус-вектор точки B из Rn . Определение. Отрезком , соединяющим точки A и B, называется множество точек этого пространства, радиус-векторы которых определяются уравнением (*). Определение. Множество M называется выпуклым, если вместе с любыми своими двумя точками A и B она содержит и все точки отрезка AB, их соединяющего. Пример: 1. На плоскости 2. Невыпуклые множества   7) Теорема: пересечение выпуклых множеств есть выпуклое множество.        Пусть M1 и M2 – выпуклые множества и их пересечение – непустое множество , тогда  - выпуклое множество. Доказательство:  Возьмём Доказать: Т.к. множества M1 и M2 – выпуклые, то Следствие: Пересечение конечного числа выпуклых множеств – выпуклое множество.  - выпуклое множество. M1, M2,..., Mn.       - выпукло е 8) Теорема: область решений системы линейных уравнений и область решений системы линейных неравенств есть выпуклое множество.           Область решений системы линейных уравнений и неравенств есть выпуклое множество.      Докажем, что ОР одного уравнения с n неизвестными, которое определяет гиперплоскость в Rn – есть выпуклое множество.        (1) . Где  - вектор из неизвестных. . Пусть  и  - решение (1).  Т.е. т. А и т. В – точки, принадлежащие ОР уравнения (1). Возьмём любую точку С внутри [AB]. Её координаты определяются из равенства  Проверим, что эта т. С также является решением уравнения (*).        Т. С является решением уравнения (1). Вместе с двумя точками А и В ОР уравнения (1) содержит все точки отрезка [AB]. ОР уравнения (1) – выпуклое множество. Докажем, что ОР одного линейного неравенства с n переменными, т.е. полупространство n-мерного пространства также есть выпуклое множество. 1)                   (2) - решение (2)  внутри [AB] и проверяем, что эта точка также является решением (2) т. С является решением (2) и все точки отрезка [AB] принадлежат полупространству, которое определяется неравенством (2).   9) Угловые точки выпуклого множества. Выпуклые многогранники.   Область решений системы из линейных уравнений и неравенств есть выпуклое множество. Эта область есть пересечение конечного числа гиперплоскостей и полупространств, и по теореме 2 – есть также выпуклое множество.        Следствие. ОДР ЗЛП – есть выпуклое множество.    Во всяком выпуклом множестве можно выделить внутренние, граничные и угловые точки.    Т. А называется внутренней точкой множества М, если существует окрестность этой точки, которая принадлежит множеству М.       Т. А – внутренняя точка множества М, если         А – граничная точка множества М, если  имеются как точки множества М, так и точки, не принадлежащие этому множеству М. Т. А – угловая точка выпуклого множества М, если она не является внутренней ни для какого отрезка, соединяющего две другие точки множества. Множество, содержащее все свои граничные точки, называется замкнутым. Множество М, называется ограниченным, если , что для каждой       точки     Множество может быть замкнутым, но неограниченным и наоборот. Например: гиперплоскость - замкнутое неограниченное множество. Определение. Выпуклое множество, являющееся пересечением конечного числа полупространств, называется выпуклым многогранником.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Т.к. полупространство определяется линейными неравенствами, то можно сказать, что выпуклый многогранник – это множество, которое определяет конечная система линейных равенств. Т.о При решении n-мерной ЗЛП удобно использовать каноническую форму записи. Т.к. систему линейных неравенств (1) можно заменить эквивалентной ей системой линейных уравнений, то мы приходим к выводу, что областью допустимых решений n-мерной ЗЛП является n-мерный выпуклый многогранник, поэтому геометрически ЗЛП – есть задача отыскания максимума (минимума) линейной функции на выпуклом многограннике.   10) Теорема о существовании опорного решения. (без доказательства)       Опор. (базис.) реш-ем нзв такое допуст.реш-е Х=(х1, х2,…,хм, 0,…,0), для кот.в-ра условий, соотв.положит.коорд-там А1, А2, … , Ам, явл.лин.независ.системой в-ров («допуст.базисное реш-е») *Базисом опор.реш-я нзв базис системы в-ров-условий (А1-Ам), влюч.в свой состав в-ра, соотв.отличным от 0 коорд-там опор.реш-я.            ***Теорема: любое опор.реш-е есть угловая точка ОДР. И наоборот: любая угловая точка ОДР есть опор.реш-е.                  Каждое опорное решение явл базисным, но не каждое базисное явл опорным. Если система линейных уравнений имеет хотя бы одно допустимое решение, то среди этих решений есть хотя бы одно опорное.                                   Доказательство: Систему линейных уравнений (1) запишем в векторной форме Где А1 – вектор-столбец из коэффициентов при неизвестных . Пусть ранг векторов системы . Для определённости будем считать, что первые n векторов этой системы образуют базис. Это означает, что существует общее решение системы (1), где  - базисные,  - свободные; сущ. базисн. реш.  .          (2)         Последние n-r координат вектора  равны нулю. Если первые координаты вектора  неотрицательны, то это базисное решение является ещё и опорным решением системы (1). По условию теоремы 1 существует хотя бы одно допустимое решение системы (1). 1) Возможны следующие два случая: ,  - опорное. Т.к. n-r последних координат X1 равны нулю  X1 – базисное решение. Кроме того, первые r координат неотрицательны 2) . В этом случае X1 – допустимое решение, но не базисное, т.к. число последних нулевых координат меньше, чем k-r. Т.к. X1 – решение, поэтому                  (а) Отметим, что система векторов  линейно зависима, т.к. в этой системе число векторов k>r - ранг системы векторов , значит, существует нетривиальная линейная комбинация. 11) Теорема о связи между угловыми точками области допустимых решений задачи линейного программирования и опорными решениями (без доказательства)     Допустимое решение ЗЛП является угловой точкой ОДР тогда и только тогда, когда это решение – опорное. Пусть дана ЗЛП и пусть системы ограничений (1) и (2) определяют выпуклый многогранник М.  Пусть  - угловая точка М все        1.  тогда из теоремы 1 мы получаем, что это решение является опорным. 2.                             (а)  - лин. завис.                                                              (б) Уравнение (а) ± уравнение (б)  t, t – число, большее нуля. Подберём число t так, чтобы все координаты векторов X1 и X2 были неотрицательными.            1. с1>0 Из первого неравенства системы получаем, что . Из второго неравенства системы получаем, что . 2. с1<0     Если  то первые координаты будут неотрицательными. Решив систему  , (*) найдём отрезок [-t2,t2], для каждой точки которого выполняется неравенство (*). Выполним этот процесс для всех ненулевых координат векторов X1 и X2. Найдём k чисел t1,t2,…,tk. Среди этих чисел возьмём наим. тогда на [-ti,ti] все координаты X1 и X2 будут неотрицательными, это означает, что X1 и X2 принадлежат ОДР, т.е. это две точки многогранника М. это означает, что точка X – середина отрезка, концами которого являются т. X1 и т. X2, т.е. т. X не является угловой точкой по определению угловой точки. Получим противоречие, т.к. т. X – угловая по определению. 12) Выпуклая линейная комбинация системы векторов. Теорема о совпадении множества точек ограниченного n-мерного многогранника с множеством выпуклых линейных комбинаций его угловых точек (формулировка).   Определение. Пусть X1,X2,…,Xs – система n-мерных векторов . - числа: 1) 2)  - выпуклая линейная комбинация системы векторов Х1,…,Xs. Примеры: 1-)  - выпуклая линейная комбинация. 2)  - не выпуклая линейная комбинация. 3)  - не выпуклая линейная комбинация. Теорема 3. Множество точек ограниченного выпуклого n-мерного многогранника совпадает с множеством выпуклых линейных комбинаций его угловых точек. Без доказательства. Теорема содержит два утверждения: Если х1,х2,…,хs – угловые точки многогранника М, то любая точка х из многогранника М. 1. . 2. Любая точка х, определяемая равенством (1) при условии, что х1,х2,…,хs – угловые точки многоугольника М Например, отрезок – многогранник, порождённый двумя точками (своими концами) и т.д. Существенно то, что многогранник – ограниченный, для неогран. теорема не выполняется.     13) Основная теорема об экстремумах линейной функции задачи линейного программирования.   Теорема 1. Если ОДР ЗЛП – ограниченная, то оптимальное решение ЗЛП существует и совпадает хотя бы с одним из опорных решений системы линейных уравнений (1) – ограничений. Доказательство: Доказать, что Х – опорное решение. Пусть х1,х2,…,xs – угловые точки (опорные решения) ОДР, тогда                     Поскольку Х – допустимое решение, то для любой точки х   Теорема 2. Если ОДР ЗЛП – ограниченная, а функция не ограничена сверху (снизу), то задача отыскания максимума f (минимума f) не имеет решений. Min f (max f) существует и достигается по крайней мере в одном из опорных решений.                                            Теорема 3. Если max (min) достигается в нескольких опорных решениях х1,х2,…,хl, то любая выпуклая линейная комбинация оптимальн. опорн. реш. есть также оптимальное решение. Теоремы 1,2,3 можно обобщить в основную теорему линейного программирования. Основная теорема: если ЗЛП имеет оптим. реш., то оно совпадает, по крайней мере, с одним из опорных решений системы ограничительных уравнений. Основная теорема указывает схему, которая может быть использована при решении ЗЛП. Схема решения ЗЛП. 1. Найти все опорные решения. 2. Подсчитать значения линейной функции на каждом опорном решении. 3. Сравнивая найденные значения, установить опорн. реш. Недостаток схемы: нужно исследовать каждое опорное решение.            Эта схема предполагает беспорядочный перебор опорных решений.                               ***Симплексный метод предполагает упорядоченный перебор опорных решений так, что на каждом следующем опорном решении значение функции ближе к оптимальному решению, чем предыдущее (идея последовательного улучшения решения). Три элемента симплексного метода: 1. Нахождение исходного опорного решения. 2. Правило перехода к следующему, лучшему опорному решению. 3. Критерий, который позволяет установить оптимальность опорного решения или необходимость его дальнейшего улучшения, или отсутствия решения.     14) Симплексный метод решения задачи линейного программирования: Теорема о возможности «улучшить» решение.      Схема решения ЗЛП. 1 Найти все опорные решения. 2 Подсчитать значения линейной функции на каждом опорном решении. 3 Сравнивая найденные значения, установить опорн. реш. Недостаток схемы: нужно исследовать каждое опорное решение.   Эта схема предполагает беспорядочный перебор опорных решений. Симплексный метод предполагает упорядоченный перебор опорных решений так, что на каждом следующем опорном решении значение функции ближе к оптимальному решению, чем предыдущее (идея последовательного улучшения решения). Три элемента симплексного метода: *Нахождение исходного опорного решения. *Правило перехода к следующему, лучшему опорному решению. *Критерий, который позволяет установить оптимальность опорного решения или необходимость его дальнейшего улучшения, или отсутствия решения.  Определение. Говорят, что ЗЛП приведена к симплексной форме, если сис. ограничительных уравнений разрешена относительно базисных неизвестных, свободные члены уравнений «≥0», а линейная функция выражена через свободные неизвестные. ← Отыскав исходн. опорн. реш., и получив приведённое выражение лин. функции, мы привели ЗЛП к симплексной форме. Теорема.Пусть ЗЛП записана в симплексной форме, тогда: 10.  и в каждом столбце с такой оценкой имеем хотя бы один положительный элемент, тогда решение можно улучшить, т.е. перейти к опорному решению Х1, в котором значение линейной функции будет больше 20. Существует отрицательная оценка свободных переменных такая, что столбец которой не содержит положительных элементов, то ЗЛП  не имеет решения ввиду неограниченности целевой функции в ОДР. 30. Все оценки свободных переменных «≥0». В этом случае соответствующее опорное решение будет оптимальным. Все               15) Симплексный метод решения задачи линейного программирования: Критерий оптимальности опорного решения.   Схема решения ЗЛП. 4 Найти все опорные решения. 5 Подсчитать значения линейной функции на каждом опорном решении. 6 Сравнивая найденные значения, установить опорн. реш. Недостаток схемы: нужно исследовать каждое опорное решение.   Эта схема предполагает беспорядочный перебор опорных решений.        *Симплексный метод предполагает упорядоченный перебор опорных решений так, что на каждом следующем опорном решении значение функции ближе к оптимальному решению, чем предыдущее (идея последовательного улучшения решения).                                                         ****** Три элемента симплексного метода: *Нахождение исходного опорного решения. *Правило перехода к следующему, лучшему опорному решению. *Критерий, который позволяет установить оптимальность опорного решения или необходимость его дальнейшего улучшения, или отсутствия решения.  Определение. Говорят, что ЗЛП приведена к симплексной форме, если сис. ограничительных уравнений разрешена относительно базисных неизвестных, свободные члены уравнений «≥0», а линейная функция выражена через свободные неизвестные. ← Отыскав исходн. опорн. реш., и получив приведённое выражение лин. функции, мы привели ЗЛП к симплексной форме. Теорема.       Пусть ЗЛП записана в симплексной форме, тогда: 10.  и в каждом столбце с такой оценкой имеем хотя бы один положительный элемент, тогда решение можно улучшить, т.е. перейти к опорному решению Х1, в котором значение линейной функции будет больше 20. Существует отрицательная оценка свободных переменных такая, что столбец которой не содержит положительных элементов, то ЗЛП  не имеет решения ввиду неограниченности целевой функции в ОДР. 30. Все оценки свободных переменных «≥0». В этом случае соответствующее опорное решение будет оптимальным. Все           Доказательство: П.3. Все оценки   Пусть Х0 – соответствующее опорное решение. Требуется доказать, что для любого другого опорного решения Х1   Признак существования множества оптимальный решений. Если все оценки свободн. перем. , то введение любой переменной в базис приведёт к уменьшению функции f, т.к.  и, следовательно, существует только одно оптимальное решение. Если же какая-то оценка свободной переменной окажется равной нулю , то введение переменной хs в базис не изменит значение линейной функции f, т.к.  будет «=0», и поэтому можно перейти к новому опорному решению, для которого , т.о. признаком существования множества решений является наличие хотя бы одной нулевой оценки свободных переменных при неотрицательности всех остальных оценок. Если нулевых оценок окажется несколько, то введением в базис кажд. из соотв. своб. перем. можно найти несколько оптимальных решений.     16) Симплексный метод решения задачи линейного программирования: Теорема об условии, при котором задача не имеет решения.     Определение. Говорят, что ЗЛП приведена к симплексной форме, если сис. ограничительных уравнений разрешена относительно базисных неизвестных, свободные члены уравнений «≥0», а линейная функция выражена через свободные неизвестные. ← Отыскав исходн. опорн. реш., и получив приведённое выражение лин. функции, мы привели ЗЛП к симплексной форме.                                     Теорема.  Пусть ЗЛП записана в симплексной форме, тогда: 10.  и в каждом столбце с такой оценкой имеем хотя бы один положительный элемент, тогда решение можно улучшить, т.е. перейти к опорному решению Х1, в котором значение линейной функции будет больше            20. Существует отрицательная оценка свободных переменных такая, что столбец которой не содержит положительных элементов, то ЗЛП  не имеет решения ввиду неограниченности целевой функции в ОДР. 30. Все оценки свободных переменных «≥0». В этом случае соответствующее опорное решение будет оптимальным. Все              Доказательство:       П.2. Пусть ЗЛП приведена к симплексной форме, и система ограничительных уравнений разрешена относительно базисн. неизв., и все свободные члены неотрицательны. Построим какое-либо неотрицательное решение Х системы .Возьмём для своб. перем. следующие неотрицательные значения.      Из системы  найдём значения базисн. неизв. Получим неотриц. реш. системы . Теперь, используя приведённое выражение для линейной функции, мы получим значение линейной функции на построенном решении. Из этого равенства видно, что если переменной xs придать сколь угодно большие значения, то значение лин. функции можно сделать сколь угодно большим положительным числом, т.о. линейная функция не ограничена сверху в ОДР.   18. В m пунктах сосредоточен однородный груз в количествах  Этот груз нужно перевезти n потребителям в количествах  Известны числа  - стоимость перевозки единицы груза от i-го поставщика j-му потребителю (тариф перевозки). Обозначим  - объём груза, перевозимого от i-го поставщика j-му потребителю. Условия транспортной задачи будем записывать в виде транспортной таблицы.         bj   ai        b1 b2 … bn a1 c11 c12 … c1n a2 c21 c22 … c2n … am cm1 cm2 … cmn   Введём вектор Х – план перевозок.План перевозок должен удовлетворять следующим условиям: грузы от каждого поставщика должны быть вывезены полностью, запросы каждого потребителя-полностью удовлетворены. (1)                                               (2) Матем. формулировка ТЗ: Найти такой план Х, удовлетворяющий системам ограничений (1) и (2), условиям неотрицательности (3) и обеспечивающий минимум целевой функции f.   19.Теорема о ранге системы векторов-условий транспортной задачи Ранг равен (m+n-1).Док-во: Надо доказать, что max число линейно независимых векторов системы (*) равно (m+n-1). Рассмотрим систему из (m+n-1) вектора:                          (**) Докажем:Система (**) линейно независима. Составим лин комб-ю векторов системы (**). Выясним,при каких знач. коэф-в вектор Y нулевой. 2 вектора равны тогда и только тогда, когда равны их соотв координаты Система имеет единственное решение .Это означает, что только тривиальная лин комб системы векторов (**) равна θ  сист векторов (**) л.н. Добавим в систему (**) вектор В рез-те получим следующую сист векторов           (+)  - нетривиальная линейная комбинация векторов  - линейно зависимые  вся система векторов (+) линейно зависима. Следствие:ранг(число базисных неизв в любом общем реш)= m+n-1   20. Отыскание исходного опорного решения транспортной задачи. Метод «северо-западного» угла. Метод минимальной стоимости.  Рассмотрим построение исходного опорного решения системы методом северо-западного угла.                 bj ai b1 b2 … bn a1 x11 a2 … am   Будем заполнять таблицу, начиная с клетки 11. Запишем в клетку 11 1му потребителю нужно ещё (b1-a1) единиц груза. Будем удовлетворять оставшиеся потребности 1 потребителя за счет запасов 2 поставщика. От 2 поставщика перевезём к 1 потребителю (a1-b1) – у первого поставщика останется такое количество груза. Этими запасами 1 поставщика будет максимально удовлетворён 2 потребитель. В клетку 12 запишем . Заполнив клетку 12 или клетку 21, двигаемся из неё в соседнюю клетку либо вправо по строке, если окажется закрыт соотв столбец, либо вниз по столбцу, если окажется закрытой соотв строка.И закрываем либо 1 столбец, либо 1 строчку для дальнейшего заполнения. Процесс продолжается до тех пор, пока не будут удовлетворены все запросы bj и не исчерпаются все запасы ai.Последняя заполняется клетка mn. Может оказаться, что закроется одновременно i-я строка и k-й столбец, тогда занесём в соседнюю строчке или столбцу клетку, ту из них, которой соответствует наименьший тариф перевозки, запишем в ней 0. Такие 0, в отличие от 0 своб клеток, будем называть базисными 0.Метод минимальной стоимостиСуть метода заключается в том, что из таблицы тарифов выбирают min, и в клетку, которая ей соответствует, помещают меньшее из чисел ai и bj . Затем из рассмотрения исключают либо строку, соотв поставщику, запасы которого полностью израсходованы, либо столбец, соотв потребителю, потребности которого полностью удовлетворены, либо и строку и столбец. Процесс продолжают, пока все запасы не будут распред, а потребности удовл. 21Теорема: реш, построенное по методу СЗУ явл опорным. Док-во: достаточно доказать, что совокуп-ть заполн. клеток образует совокуп-ть базисных клеток. 1.Доказать: заполн-х клеток m+n-1. 2.Доказать:вектор-столбцы коэфф-в при неизв-х с номерами заполн-х клеток линейно незав. 1.На каждом этапе, кроме последнего, занесением очередного зн-я xik в табл закрывается только 1 столбец или 1 строка. И только в последней кл. одноврем. закрываются n-я строка и m-й столбец. Значит всего будет занесено в табл чисел xik на 1 меньше, чем имеется строк и столбцов. 2.Методом матем индукции по числу: k=2, (m=1, n=1)   b а b1 a1 x11   Будет заполнена только 1 кл. x11, и вектор b11 образует линейно независимую сист . Предположение индукции: Пусть утверждение (2) выполн. при k=m+n-1. Докажем, что будет выполняться и при k=m+n. Будем заполнять таблицу методом СЗУ, и пусть для опред-сти x11=a11. 1я строчка закрыта, пусть будут заполнены (1,1), (2,1),…,(i,j),…,(m,n).Выпишем вектор-столбцы, соотв. клеткам с этими номерами.   bj       ai b1 b2 … bj … bn a1 x11           a2 x21           … ai … am             (*)    Докажем, что эти векторы лин. незав. Линейная комбинация: (1) У всех векторов системы (*), кроме вектора А11 первые координаты равны нулю, т.к. у них первый индекс больше единицы. С1=0      (2) Из исх. табл. вычеркнем 1 строчку и изменим потребности 1 потребителя на b1-a1. Получим новую ТЗ, у кот. число поставщиков равняется m-1, число потребителей n.Тогда k=m+n-1.Выпишем вектор-столбцы при неизв. с номерами заполненных кл. По предположению индукции эти векторы л.н. Тогда в (1) получаем      

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

Т:Пусть Х0 – опорное решение сист.огр-й (1),(2), - потенциалы.Если для каждой своб кл выпол усл-е: , то реш явл оптимальным.

Док-во: , пусть для допуст. реш.

[  - для любого решения выполняется условие (1) и(2)]

Для базисных клеток транспортной таблицы , а если клетка – свободная, то =0.Если имеется хотя бы одна свободная клетка, для которой не выполняется условие , то опорное решение не является оптим-м.


23. Переход от одного опорного решения к лучшему опорному решению. Сдвиг по циклу.

 


Дата добавления: 2018-02-18; просмотров: 504; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!