Геометрическая интерпретация двумерной задачи линейного программирования и ее решение

Линейное программирование

Примеры задач линейного программирования

1.1.1 Задача планирования выпуска продукции (планирование производства)

Машиностроительное предприятие для изготовления четырех видов продукции использует токарное, фрезерное, сверлильное, расточное и шлифовальное оборудование, а также комплектующие изделия. Кроме того, сборка изделий требует выполнения сборочно-наладочных работ. Нормы затрат всех видов ресурсов на изготовление каждого из изделий приведены в таблице (см. табл. 1.1). В этой же таблице указан имеющийся фонд каждого из ресурсов и прибыль от реализации одного изделия каждого вида.

Таблица 1.1−Нормы затрат на изготовление одного изделия

Продолжение таблицы 1.1

Надо составить такой план выпуска продукции, чтобы получить максимальную прибыль. Построим математическую модель данной задачи. Пусть x₁ – планируемое количество изделий 1-го типа, x₂, x₃, x₄ – планируемое количество изделий 2-го, 3-го, 4-го типов соответственно.

Тогда

     f=315x₁+278x₂+573x₃+370x₄          (1.1)

прибыль предприятия. Так как нам надо получить как можно большую прибыль, то будем искать наибольшее (максимальное) значение функции f. Общие объемы ресурсов накладывают на нашу задачу ограничения

550x₁ + 620x₂ £ 64270

40x₁ + 30x₂+ 20x₃ + 20x₄ £ 4800

86x₁ + 110x₂ +150x₃ + 52x₄ £ 22360

               160x₁+ 92x₂ + 158x₃ + 128x₄ £ 26240   (1.2)

158x₂ + 30x₃ + 50x₄ £ 7900

3x₁ + 4x₂ + 3x₃ + 3x₄ £ 520

4.5x₁ + 4.5x₂ + 4.5x₃ + 4.5x₄ £ 720.

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

   1.1.2 Задача планирования капитальных вложений

Для электроснабжения трех стройплощадок используются две трансформаторные подстанции. Первая стройплощадка потребляет 130 кВт, а вторая и третья по 140 кВт. Мощность первой ТП – 250 кВт, а второй 160 кВт. Расстояние от первой ТП – 600, 400, 200 м, до первой, второй и третьей площадки соответственно. От второй ТП: − 500, 300 и 200 м соответственно. Требуется составить схему электроснабжения с минимальными капитальными вложениями.

Капитальные вложения для устройства линий рассчитываются по следующей формуле:

      ,            (1.3)

где: S_ij – мощность, потребляемая j-ой площадкой от i-ой ТП, кВт;

l_ij – расстояние от j-ой площадки до i-ой ТП, м.;

α  – постоянный множитель.

Итак, нам надо минимизировать функцию

                f=α(6S₁₁+4S₁₂+2S₁₃+5S₂₁+3S₂₂+2S₂₃),       (1.4)

при ограничениях:

S₁₁ + S₂₁ =130;

S₁₂ + S₂₂ =140;

                               S₁₃ + S₂₃=140;                     (1.5)

                            S₁₁ + S₁₂ + S₁₃ =250;

                            S₂₁ + S₂₂ + S₂₃ =160 .

Как и в предыдущем примере имеем задачу линейного программирования.

Основные определения

ОПРЕДЕЛЕНИЕ 1.1.Задача, состоящая в нахождении наибольшего (наименьшего) значения функции

                 f(x)=с₁x₁+c₂x₂ + … + c_nх_n                  (1.6)

на множестве точек =(x₁,…,x_n), удовлетворяющих системе ограничений вида:

                  a₁₁x₁ + a₁₂x₂ +…+ a_1nx_n < R₁ > b₁

                  a₂₁x₁ + a₂₂x₂ +…+ a_2nx_n < R₂ > b₂

                  . . . . . . . . . .                  (1.7)

                  a_m1x₁ + a_m2x₂ +…+ a_mnx_n < R_m > b_m

называется задачей линейного программирования общего вида.

Здесь:

f( )=с₁ x₁ + c₂ x₂ + … + c_n x_n – целевая функция;

R_i, i =  – операции отношения =, ≥,≤;

c_i, i =  ; a_ij, i =  j = ; b_i, i =  – заданные константы.

    ОПРЕДЕЛЕНИЕ 1.2.Всякую точку =(x₁,…,x_n), компоненты которой удовлетворяют всем ограничениям системы (1.7), будем называть допустимой точкой или допустимым решением задачи, или допустимым планом задачи.

Задача линейного программирования состоит, таким образом, в нахождении такой допустимой точки  (такого допустимого плана) среди множества допустимых точек, при которой целевая функция принимает max (min) значение. Допустимое решение = (x₁⁽⁰⁾,…,x_n⁽⁰⁾)^T, доставляющее целевой функции оптимальное значение (оптимум), будет называться оптимальным решением или оптимальным планом задачи. В дальнейшем будем говорить, к примеру, только о нахождении max целевой функции.

   Задачу линейного программирования, представленную в виде:

f = с₁x₁ + c₂x₂ + … + c_nx_n → max (min)

                   a₁₁x₁ + … + a_1nx_n= b₁

                   a₂₁x₁ + … + a_2nx_n= b₂

                   . . . . . . .                             (1.8)

                   a_m1x₁ + … + a_mnx_n= b_m

                   x_i ≥ 0, i = ;

будем считать канонической задачей линейного программирования.

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

   Пример 1.1. Привести к каноническому виду задачу:

                 f = x₁ –2x₁ +x₃  max

                    x₁ + 2x₂ + 3x₃ ≤ 5

                    2x₁ +3x₂ – 4x₃ = 3                           (1.9)

                    –x₁+ x₂– x₃ ≥ 2

                    x₁  0, x₂  0.

Введем две дополнительные неотрицательные переменные x₄ и x₅ в первом и третьем ограничениях, так, чтобы получить ограничения – равенства. Кроме того, переменную x₃ представим в виде:

                             x₃ = x₃^׳ – x₃^״,                        (1.10)

где: x₃^׳  0, x₃^״  0.

   Получим:

f = x₁ – 2x₁ + x₃^׳ – x₃^״  max,

                    x₁ + 2x₂ + 3(x₃^׳ – x₃^״) + x₄  = 5

                   2x₁ + 3x₂ – 4(x₃^׳ – x₃^״) = 3              (1.11)

                   – x₁ – x₂ – (x₃^׳ – x₃^״) – x₅  = 2

                   x₁ ³ 0, x₂ ³ 0, x₃^׳ ³0, x₃^״ ³0, x₄ 0, x₅ 0,

а это уже задача в канонической форме.

Введя в рассмотрение векторы

                                                                                           a₁₁ … a_1n

=(c_1, c_2, … c_n),  = (x₁, … , x_n)^T,  = (b₁,…, b_m)^T, A= a₂₁ … a_2n

                                                                                           . . . . . . .

                                                                                           a_m1 … a_mn

можем переписать задачу (1.6),(1.7) линейного программирования в форме:

                          f = ·  max(min)                (1.12)

                                                                 (1.13)

Геометрическая интерпретация двумерной задачи линейного программирования и ее решение

Рассмотрим двумерную задачу:

               f = c₁x₁ + c₂x₂    max(min),              (1.14)

      a₁₁x₁ + a₁₂ x₂ < R₁ > b₁

      a₂₁x₁ + a₂₂ x₂ < R₂ > b₂

      . . . . .                                    (1.15)

                   a_m1 x₁ + a_m2 x₂ < R_m > b_m .

Каждое из ограничений a_i1x₁+a_i2 x₂ < R_i > b_i определяет в плоскости, с системой координат x₁ o x₂ множество точек, лежащих по одну сторону от прямой a_i1x₁+a_i2x₂=b_i (т.е. полуплоскость). Множество всех точек плоскости, координаты которых удовлетворяют всем ограничениям, т.е. принадлежат сразу всем полуплоскостям, определяемым отдельными ограничениями, будет представлять собой допустимое множество. Очевидно, что, если множество не пусто, то это будет некоторый многоугольник (возможно и неограниченный, возможно вырождающийся в отрезок, точку). Многоугольник будет выпуклым, что легко показать, т.е. любые две его точки можно соединить отрезком, точки которого принадлежат допустимому множеству.

 ОПРЕДЕЛЕНИЕ 1.3. Множество D-точек n-мерного евклидова пространства будем называть выпуклым, если для любых x⁽¹⁾=(x₁⁽¹⁾,…,x_n⁽¹⁾)^T и x⁽²⁾=(x₁⁽²⁾,…,x_n⁽²⁾)^T из множества D и любых α ≥0, β≥0 таких, что α+β=1, точка x=αx⁽¹⁾+βx⁽²⁾ также принадлежит D.

ОПРЕДЕЛЕНИЕ 1.4. Вершиной выпуклого множества в R_n назовем такую точку, которую нельзя представить в виде x=αx⁽¹⁾+βx⁽²⁾, α>0, β>0, α+β=1, ни при каких x⁽¹⁾,x⁽²⁾.

Проиллюстрируем вышесказанное примерами.

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

1) 2x₁ – 3x₂£ 2                    2) –x₁ + x₂£ 1

          3x₁ – x₂£ 1                            x₁ – 2x₂£ 1

                                            x₁ ³ 0

          x₁ ³ 0                                      x₂ ³ 0

          x₂ ³ 0

  3)                          4)

          x₁ + x₂ £ 1                          x₁ + x₂ ³1             x₂ £1                                      x₁ + x₂ £1

                                                             x₂ – x₁ ³–1

Построив допустимые множества, убедимся в вышесказанном.

Рассмотрим теперь геометрическую интерпретацию решения задачи линейного программирования. Пусть допустимая область задачи (1.14)−(1.15) оказалась непустой (в соответствии с рисунком 1.1).

                x₂                                f =a_min

                                                                                                                   (x₁⁽⁰⁾ , x₂⁽⁰⁾ ) – точка максимума

                                                                                                                                                             f=a_mах 

                                          Точка

                      минимума

                                          n= grad f                         f = c₁x₁ + c₂x₂ = a

                                                                                                          х₁

Рисунок 1.1 - Геометрическая интерпретация задачи

линейного программирования

Мы хотим найти те точки допустимой области, координаты которых доставляют целевой функции наибольшее значение. Построим линию уровня целевой функции f=c₁x₁+c₂x₂=a . Получим множество точек, в точках которого f принимает одно и тоже значение a . Перемещая линию уровня в направлении вектора grad f=(c_1,c₂)=n, нормального к линии уровня, будем получать в пересечении этой линии с допустимой областью точки, в которых целевая функция принимает новое значение, большее чем значение на предшествующих линиях уровня.

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

Пример 1.2.

                            f = x₂ – 2x₁  max

                                                      –x₁ + x₂ £ 1

                                                        x₁ – 2x₂ £ 1                                       

                                                        x₁ ³ 0, x₂ ³ 0   

                                               x₂    f = –2x₁ + x₂ = 0

                                                         f =1

                              n (–2,1)

                                               1

                                                                                                                         x₁  

                              –2 –1      0.5   1                                                                     

Рисунок 1.2 - Геометрическая интерпретация задачи

     линейного программирования

Точка максимума:

               x=(0, 1)^T;

                f_max=f(0, 1)=1.

Легко представить, что задача имеет бесчисленное множество оптимальных решений, а может их не иметь вовсе, как например:

                               f = x₁ + x₂  min(max);

        x₁ + x₂ ³ 1

                                                      –x₁ + x₂ £ 1                                                        

                                                       x₁ – 2x₂ £ 2                                                                       

                                x₁ ³ 0, x₂ ³ 0.

Целевая функция достигает минимального значения в точках отрезка x₁+x₂=1, между точками (0, 1) и (1, 0), а максимального значения функция не достигает (не ограничена в допустимой области).

                           x₂

                             K

                                                                 f=K

                            1             n(1,1)    

                     –1         1     2                                     x₁    

                                   –1

                                      f =1          

Рисунок 1.3 − Геометрическая интерпретация задачи линейного программирования

1.3.1 Свойства задачи линейного программирования

Рассмотренные примеры позволяют сформулировать основные свойства задачи линейного программирования.

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

Свойство 2. Если допустимая область имеет вершины и задача линейного программирования имеет решение, то оно достигается по крайней мере в одной из вершин.

Свойство 3. Множество решений задачи линейного программирования выпукло.

Свойство 4. Если допустимая область ограничена, то любая задача линейного программирования имеет оптимальное решение.

Свойство 5. Необходимым и достаточным условием существования решения задачи линейного программирования на максимум (минимум) является ограниченность целевой функции сверху (соответственно снизу) в допустимой области.

Все перечисленные свойства справедливы и в общем случае (n≥2).

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

Тогда:

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

Если нет, то

2) используя определенные правила проверяем, нельзя ли утверждать, что задача не имеет оптимального решения (целевая функция не ограничена сверху или, соответственно, снизу на допустимом множестве). Если утверждать это можно, то задача неразрешима.

Если нельзя, то

3) по определенному правилу ищем новую, лучшую вершину и переходим к пункту 1).

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

1.3.2 Обоснование симплекс метода

Пусть имеется задача линейного программирования в канонической форме:

                            f = c₁x₁ + c₂x₂  c_nx_n  max                          (1.16)

                            a₁₁x₁ + … + a_1n x_n = b₁

                         . . . . . . . . .                                               (1.17)

                     a_m1 x₁ + … +a_mn x_n = b_m

                x₁³0, …, x_m³0 .

Вводя в рассмотрение векторы

                             Aj=(a_1j , a_2j ,…, a_mj )^T , j= ;                             (1.18)

мы можем переписать задачу в форме

                            f = ( , x)  max;

                         A₁x₁ + A₂x₂ +…+ A_nx_n =b;                                   (1.19)

                  x  0;

и трактовать ее следующим образом: из всех разложений вектора b по векторам A₁,…,A_n , с неотрицательными коэффициентами требуется выбрать хотя бы одно такое, коэффициенты x_i, i=1,n, которого доставляют целевой функции f оптимальное значение. Не ограничивая общности считаем ранг матрицы А равным m и n>m (случай n=m тривиален). Дадим ряд определений.

ОПРЕДЕЛЕНИЕ 1.5. Ненулевое допустимое решение x=(x₁,…,x_n)^T называется опорным, если векторы , соответствующие отличным от нуля координатам вектора x, линейно-независимы.

ОПРЕДЕЛЕНИЕ 1.6. Ненулевое опорное решение назовем невырожденным, если оно имеет точно «m» положительных координат.

ОПРЕДЕЛЕНИЕ 1.7. Если число положительных координат опорного решения меньше m, то оно называется вырожденным.

ОПРЕДЕЛЕНИЕ 1.7. Упорядоченный набор из «m» линейно − независимых векторов A_i, соответствующих положительным координатам опорного решения назовем базисом.

Пример 1.3.

Дана система ограничений задачи:

              2x₁ + x₂ + 3x₃ = 2

                  x₁ − 2x₃ + x₄ = 1                                                            (1.20)       

                  x₁ ³0, x₂ ³0, x₃³0, x₄ ³0.

Здесь

   m=2; A₁=  , A₂ =  , A₃ =  , A₄=  ,  =   .

Очевидно, что x⁽¹⁾=(0, 2, 0, 1)^T , x⁽²⁾ =(1, 0, 0, 0)^T,

x⁽³⁾=( , 1, 0, )^T, являются допустимыми решениями задачи. Очевидно, что x⁽¹⁾, x⁽²⁾– являются опорными решениями, поскольку системы векторов { A₂, A₄} и { A₃}, линейно независимы, а x⁽³⁾ не является опорным решением, так как { A₁, A₂, A₄ } – линейно зависимы. Опорное решение x⁽¹⁾− невырожденное, а x⁽²⁾– вырожденное. Базис невырожденного опорного решения определяется естественным образом. Для x⁽¹⁾ − это { A₂, A₄}.

Приведем теорему, увязывающую понятие опорного решения и вершины допустимого множества.

ТЕОРЕМА 1.1. Вектор = (x₁,…,x_n)  тогда и только тогда является опорным решением задачи, когда точка x является вершиной допустимого множества.

Доказательство. Необходимость. Пусть x – опорное решение задачи (1.19). Если x = 0, то невозможность ее представления в виде , где α >0, β >0 и  – допустимые решения, очевидна.

Пусть x ≠ 0 и

          ,

где x₁>0, x₂ >0,…, x_k>0.

Предположим, в противоречие с теоремой, что точка x не является вершиной допустимого многогранника:

 и ,

Так как последние n-k координат точки x равны нулю, то и последние n-k координат, как точки x⁽¹⁾, так и точки x⁽²⁾ должны быть равны 0.Таким образом, можно записать:

Ввиду допустимости точек  и  имеем:

                          (1.21)

            .           (1.22)

Вычитая почленно (1.22) из (1.21), получим:

.  (1.23)

Точки x⁽¹⁾ и x⁽²⁾ различны, следовательно, среди коэффициентов при A_i (i=1,2,…,k) в (1.23) есть отличные от нуля. А это означает, что векторы A₁, A₂,…, A_k  линейно зависимы, что противоречит тому, что x=(x₁,x₂,…,x_k,0,…,0)– опорное решение задачи. Следовательно, наше предположение неверно и x вершина допустимого многогранника.

Достаточность. Пусть наоборот, точка x– вершина допустимого многогранника. Если x = 0, то x по условию опорное решение. Пусть, x≠0 и для определенности x=(x₁,x₂,…,x_k,0,…,0), где  x₁>0, x₂ >0,…,x_k>0.

Предположим снова от противного, что при этом вектор x=(x₁,x₂,…,x_k,0,…,0) являясь, конечно, допустимым для нашей задачи, не является опорным решением. Тогда векторы A₁, A₂,…, A_k – линейно зависимы, т.е. существуют такие действительные числа α₁, α₂,…, α_k не все равные нулю, что справедливо равенство:

          .                  (1.24)

Являясь допустимым, вектор x удовлетворяет условию:

           .                      (1.25)

Умножим обе части равенства (1.24) на некоторый параметр θ и сначала вычтем почленно (1.24) из (1.25), а затем сложим (1.24) и (1.25).Получим:

Так как x_i >0 (i=1,2,…,k), то, очевидно, можно найти такое достаточно малое значение θ₀ > 0  множителя θ, что и в первом и во втором из полученных равенств, все коэффициенты будут неотрицательными. Тогда эти равенства (при θ = θ₀) означают, что n- мерные векторы

и

являются допустимыми (причем различными) решениями задачи.

При этом, очевидно, имеем:

а это противоречит тому, что x– вершина допустимого многогранника. Следовательно, x не может не быть опорным решением. Теорема доказана.

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

Дан базис

             , ,…, .

Тогда:

b= + +…+ =[ ,…, ]*( ,…, )^T,

( ,…, )^T =[ ,…, ]^–1 * (b₁,…,b_m)^T,

дополнив найденный вектор нулевыми значениями переменных ( ,…, ), получаем опорное решение. Исследуем его на оптимальность, для этого исследуем целевую функцию.

Предварительно введем обозначения:

    x_B= ( ,…, )^T – вектор базисных переменных;

  B =[ ,…, ]– матрица базисных векторов;

  x_D=( ,…, )– вектор свободных переменных;

  c_B=( ,…, )^T – вектор из коэффициентов целевой функции при базисных неизвестных;

     с_D= ( ,…, )^T – вектор из коэффициентов целевой функции при свободных переменных;

D=[ ,…, ] – матрица свободных векторов (векторов, не вошедших в базис).

С учетом введенных обозначений ограничения (1.19) можно переписать в виде:

                       Bx_B+Dx_D=b.                       (1.26)

Выразим базисные переменные через свободные

      x_B=B ( –Dx_D)= – Dx_D,          (1.27)

(при x_D=0 получаем базисные компоненты опорного решения).

Подставим x_B в целевую функцию:

f= x_B+ x_D= –( D– )x_D.   (1.28)

Обозначим:

        a=(a₁,…,a_n-m)=( D– )            (1.29)

и назовем его вектором оценок.

Очевидно, что

                         a x_c= .                  (1.30)

Отметим, что произведение A_j представляет разложение вектора A_j по базису, следовательно, в столбцах матрицы D  стоят разложения векторов, не попавших в базис (свободных) по базису. Проанализируем выражение для целевой функции (1.28):

а) если все компоненты вектора оценок неотрицательные, то максимальное значение целевой функции достигается при x_B=  и x_D=0, то есть построенное опорное решение – оптимальный план (решение) исходной задачи;

б) если среди компонент вектора оценокα есть отрицательные, то опорное решение не оптимально, поскольку, как видно из (1.28)−(1.30), возможно увеличить значение f за счет некоторых компонент вектора x_D; при этом возможны две ситуации:

1) отрицательны компоненты вектора оценок, к примеру, α_k1, α_k2,…,α_ks и при этом, по крайней мере у одного из свободных векторов , ,…,  все компоненты разложения по базису не положительны, тогда из (1.27) видно, что можно неограниченно увеличить компоненты вектора x_B за счет увеличения компоненты вектора x_D, а, следовательно, целевая функция не ограничена;

2) в случае положительных компонент разложения по базису свободных векторов существует лучшее опорное решение, которое можно получить, введя в базис свободный вектор _S, соответствующий наименьшей из отрицательных компонент вектора оценок (с целью максимально прирастить f ) и, выведя из базиса тот вектор , исходного базиса, для которого:

                                        (1.31)

где:  – компоненты x_B; – компоненты вектора _S, вводимого в базис, k= .

Заменив базис, мы можем вновь перейти к построению опорного решения и его исследования.

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

                   (1.32)

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

1.3.3 Нахождение начального базиса.

В заключении обратимся к вопросу построения начального базиса. Здесь отметим, что, если в исходной задаче все ограничения имели вид “ ”, то в качестве начального базиса (как легко показать) можно брать базис из векторов при дополнительных переменных. В общем случае для построения начального базиса используется специальный прием, известный как метод искусственного базиса, изложенный ниже. Итак, пусть дана задача линейного программирования в канонической форме:

                              f = ·  max;    

                                                                 (1.33)

Рисунок 1.4 – Схема алгоритма решения задачи линейного программирования

Рассмотрим вспомогательную задачу:

                                                          G = –y₁ – y₂ – … – y_m  max;

                                                          a₁₁x₁ + … + a_1nx_n + y₁ = b₁                                                        (3.                                                      a₂₁x₁ + … + a_2nx_n + 0·y₁ + y₂ = b₂              (1.34)

                                                          . . . . . . . . . . . . .

                                                           a_m1x₁ + … + a_mnx_n + 0_*y₁ + …+y_m = b_m

                    x_i 0, i = ,

                    y_i  0, i = .

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

Переменные y₁, y₂, ….,y_m называются искусственными переменными.

Очевидно, что векторы

_n+1=(1,0,…,0)^T, _n+2=(0,1,0,…,0)^T,…, _n+m=(0,0,…,1)^Т

образуют базис для опорного решения

,

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

1.3.4 Решение в форме симплекс − таблиц.

В случае небольшого числа ограничений и переменных, приведенный в предыдущем разделе алгоритм можно легко реализовать без помощи ЭВМ, оформляя решение в виде симплекс-таблиц. Итак, дана задача:

                                       f = ( , )  max

                                       x₁ + x₂ +…+A_nx_n=b,                  (1.35)

                                   ≥0

и найден исходный базис , ,…, . Находим разложения всех векторов ,…,A_n и b по базису. Полученные результаты заносим в таблицу 1.2.

Таблица 1.2 - Симплекс таблица

№ п/п	Базис	cB.	b (опорное решение)	c1	c2	…	cn
						…
1			x10	x11	x12	…	x1n
2			x20	x21	x22	…	x2n
3			x30	x31	x32	…	x3n
.	.	.	.	.	.	.	.
m			xm0	xm1	xm2	…	xmn
Оценки				1	2	…	n

Здесь в столбце «Базис» указываются вектора попавшие в базис; в столбце c_B. записываются коэффициенты  при соответствующих неизвестных из целевой функции; в столбце b (опорное решение) записываются координаты разложения вектора b по базису, то есть опорный план; в столбцах , ,…,A_n  записывают координаты разложения этих векторов по базису, то есть столбцы матрицы D. После этого заполняют строку «Оценки»: