Системное програмирование

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

  В столбце С_b этой таблицы записывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса.

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

В табл. 1. первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют. В этой строке, в столбце вектора Р₀ записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора P_j — значение .

  Значение  , находится как скалярное произведение вектора P_j  (j=1,m) на вектор С_b =(с₁; с₂; ...; с_m):

  Значение  , равно скалярному произведению вектора Р₀ на вектор С_b:

  После заполнения табл. 1 исходный опорный  план проверяют на оптимальность. Для  этого просматривают элементы (m + 1) -й строки таблицы. В результате может иметь место один из следующих трех случаев:

1) для j = m + 1, т + 2,…n (при j=1,m; ). Поэтому в данном случае числа для всех j от 1 до n;

2. для некоторого j, и все соответствующие этому индексу величины (i=l, m);
3. для некоторых индексов j, и для каждого такого j по крайней мере одно из чисел положительно.

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

   Для определения вектора, подлежащего  исключению из базиса, находят min ( ) для всех > 0. Пусть этот минимум достигается при i=r. Тогда из базиса исключают вектор Р_r, а число называют разрешающим элементом.

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

   После выделения направляющей строки и  направляющего столбца находят  новый опорный план и коэффициенты разложения векторов P_j через векторы нового базиса, соответствующего новому опорному плану. Это легко реализовать, если воспользоваться методом Жордана - Гаусса. При этом можно показать, что положительные компоненты нового опорного плана вычисляются по формулам:

таблица 1.

таблица 2.

а коэффициенты разложении векторов P_j через векторы нового базиса, соответствующего новому опорному плану,— по формулам

После вычисления и , согласно формулам (6) и (7) их значения заносят в табл. 2. Элементы (m+1)-й строки этой таблицы могут быть вычислены либо по формулам

либо на основании  их определения.

  Наличие двух способов нахождения элементов  (т+1)-й строки позволяет осуществлять контроль правильности проводимых вычислений.

   Из  формулы (8) следует, что при переходе от одного опорного плана к другому  наиболее целесообразно ввести в  базис вектор P_j, имеющий индекс j, при котором максимальным по абсолютной величине является число ( ) ( <0, >0). Однако с целью упрощения вычислительного процесса в дальнейшем будем вектор, вводимый в базис, определять, исходя из максимальной абсолютной величины отрицательных чисел . Если же таких чисел несколько, то в базис будем вводить вектор, имеющий такой же индекс, как и максимальное из чисел с_j,  определяемых данными числами ( <0).

  Итак, переход от одного опорного плана  к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы новой симплекс-таблицы  можно вычислить как с помощью  рекуррентных формул (6) - (9), так и  по правилам, непосредственно вытекающим из них. Эти правила состоят в  следующем.

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

2. Элементы векторов Р₀ и P_j  в строке новой симплекс-таблицы, в которой записан вектор, вводимый в базис, получают из элементов этой же строки исходной таблицы делением их на величину разрешающего элемента. В столбце С_b в строке вводимого вектора проставляют величину с_k , где k - индекс вводимого вектора.

3. Остальные элементы столбцов вектора Р₀ и P_j  новой симплекс-таблицы вычисляют по правилу треугольника. Для вычисления какого-нибудь из этих элементов находят три числа:

1) число, стоящее  в исходной симплекс-таблице на  месте искомого элемента новой  симплекс-таблицы;

2. число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего вектору, вводимому в базис;
3. число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и строки вновь вводимого в базис вектора (как отмечено выше, эта строка получается из строки исходной симплекс-таблицы делением се элементов на разрешающий элемент).

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

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

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

  Итак, нахождение оптимального плана симплексным  методом включает следующие этапы:

1. Находят опорный план.
2. Составляют симплекс-таблицу.
3. Выясняют, имеется ли хотя бы одно отрицательное число ;. Если нет, то найденный опорный план оптимален. Если же среди чисел имеются отрицательные, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.
4. Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом , а направляющая строка — минимальным из отношений компонент столбца вектора Р_о к положительным компонентам направляющего столбца.
5. По формулам (6) — (9) определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов P_j  по векторам нового базиса и числа , . Все эти числа записываются в новой симплекс-таблице.
6. Проверяют найденный опорный план на оптимальность. Если план не оптимален и необходимо перейти к новому опорному плану, то возвращаются к этапу 4, а в случае получения оптимального плана или установлении неразрешимости процесс решения задачи заканчивают.