Симплекс метод в линейном программировании

    х₁-3х₂=0

    Эта прямая, проходящая через начало координат, строится следующим образом. Легко  заметить, что в левой части  уравнения стоит скалярное произведение двух векторов С=(с₁,с₂)=(1,-3) и Х=(х₁,х₂). Если скалярное произведение векторов равно нулю, то векторы неперпендикулярные.

    Построим  вектор С [он проходит через начало координат и точку (1, -3)] и проведем прямую. Это и будет прямая.

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

    Передвижение  на графике прямой равносильно изменению  значения b в уравнении х₁-3х₂=b. Каждому значению b соответствует прямая. Получаемые прямые параллельны между собой и называются линиями уровня. Особенность линии уровня состоит в том, что целевая функция принимает на ней одинаковые значения, т.е. подставив координаты любой точки линии уровня в целевую функцию, ее значения изменятся не будут.

    Целевая функция f в задаче  достигает, своего минимального значения в точке B многоугольника, а максимального – в точке D.

    Оптимальному  решению задачи  соответствует  в точке B, которая лежит на пересечении прямых  

 

     -х₁+х₂=3 (II)                                        

    х₁+х₂=10 (IV)  

    Для определения координат точки B решим систему .  

     -х₁+х₂=3                                       

    х₁+х₂=10   

      В результате получим:  

    Х₁=3 ½, х₂=6 ½;   f_min=7/2 – 3 ^13/2= –16.   
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3.Симплексный  метод линейного  программирования.

      

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

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

     Симплекс- метод состоит в отыскании  крайних точек выпуклого многогранника и для понимания его сути очень важна одна из теорем матричной алгебры: линейный функционал, определенный на выпуклом многограннике, принимает максимум или минимум в крайней точке выпуклого многогранника

     Симплексный метод линейного программирования основан на ряде теорем линейной алгебры. «Симплекс» означает выпуклый многогранник в пространстве с числом измерений, равным n.

     Симплексный метод решения задач линейного  программирования был разработан в  конце 40 – х годов американским математиком Дангинцом. Этот метод может быть использован для решения большого комплекса задач внутризаводского планирования: формирование специфицированной годовой производственной программы выпуска предприятия, плана загрузки различных групп оборудования, календарное распределение производственной программы выпуска, распределение годовой программы выпуска по кварталам, квартальной – по месяцам, месячной – по декадам и пятидневкам и т.п.

     В реальном n – мерном пространстве величина х представляет собой точку или вектор – строку: Х=(Х₁, Х₂…, Х_n). Числа Х_i(I=1,2,…,n)называются координатами точки. Если n=2, то ему на плоскости соответствует многоугольник. Если n=3, то ему в трёхмерном

     пространстве  соответствует выпуклый многогранник. Точка х в n – мерном пространстве может быть представлена вектором столбцом.

      Если Х=(Х₁, Х₂), то вектор – столбец Х=

Если Х=(Х₁, Х₂, Х₃), то вектор – столбец Х=  

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

     Умножение вектора на действительную скалярную величину производится умножением каждой координаты вектора на это число.

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

     

       В n – мерном пространстве все отрицательные решения системы уравнений образуют выпуклый многогранник, который называется многогранником решений. И если линейная функция, выражающая критерий оптимальности, принимает своё экстремальное значение, то эти значения обязательно достигаются в какой – либо точке или нескольких точках (вершинах) многогранника. При этом оказывается, что вершин у многогранников может очень много и их число всегда конечно. Последнее обстоятельство и используется при решении задач симплексным методом линейного программирования. В поисках наилучшего решения рассматривается только вершины многогранника решений. Причём при выборе оптимального решения рассматривается относительно небольшое число конкурирующих вариантов. Это происходит от того, что сфера определения оптимального решения ограничена требованием не отрицательности переменных.

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

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

     Решение экономических задач симплексным  методом линейного программирования состоит в отыскании какой  – либо из вершин многогранника  решений или в определении основного возможного варианта. Он даёт точку или вектор, у которого отличными от нуля составляющими являются свободные векторы или векторы свободных переменных. Это значит, что в начальный базис или в основное решение не входит ни один из векторов тех переменных, значения которых надлежит определить. Затем устанавливается, достигает ли в этой вершине линейная функция, выражающая критерий оптимальности, наилучшего значения. В симплексном методе линейного программирования первоначальный план распределения ресурсов никогда не соответствует оптимальному варианту, так как он выражается через свободные векторы.

     

     

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

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

   

3.1 Общий вид задачи, решаемой симплекс  – методом

     Общий вид задачи, решаемой симплекс –  методом, следующий: найти максимальное значение функции:

      F(x)=C₁X₁+C₂X₂+…+C_nX_n         max

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

     A₁₁X₁+A₁₂X₂+A₁₃X₃+…+A_1nX_n=B₁

     A₂₁X₁+A₂₂X₂+A₂₃X₃+…+A_2nX_n=B₂

     …

     A_m1X₁+A_m2X₂+A_m3X₃+…+A_mnX_n=B_m

     и неравенств:

     Х₁ 0;  Х₂ 0;  Х₃ 0;

     где Х₁, Х₂… Х_n – переменные;

С₁, С₂…С_n, А₁₁…А_mn, В₁, В₂…В_m – коэффициенты переменных.

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

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

     Х_j 0,

     где j=1,2,3…,n

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

   

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

     Эти свободные векторы образуют так называемую единичную матрицу, т.е. такую, у которой элементы по главной диагонали равны единице, а все остальные элементы равны нулю.

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