Симплекс метод при решении экономических задач

Для определения вектора, подлежащего исключению из базиса, находят для всех

Пусть этот минимум достигается  при i=r. Тогда из базиса исключают вектор , а число называют разрешающим элементом.

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

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

                                                (4)

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

                                                   (5)

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

                                               (6)

                                              (7)

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

Таблица 1

 

Таблица 2

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

1. Находят опорный план.

2. Составляют симплекс-таблицу.

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

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

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

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

 

4. Решение задачи линейной оптимизации симплекс – методом.

4.1 Физическая (техническая)  постановка задачи

 

Нефтеперерабатывающий завод получает четыре полуфабриката:

• 400 тыс. л. алкилата;
• 250 тыс. л. крекинг-бензина;
• 350 тыс. л. бензина прямой перегонки;
• 250 тыс. л. изопентона;

В результате смешивания этих четырёх компонентов в разных пропорциях образуются три сорта авиационного бензина:

• Бензин А – 2 : 3 : 5 : 2 ;
• Бензин В – 3 : 1 : 2 : 1 ;
• Бензин С – 2 : 2 : 1 : 3 ;

Стоимость 1 тыс.л. указанных  сортов бензина:

• Бензин А – 120 руб.
• Бензин Б – 100 руб.
• Бензин С – 150 руб.

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

При следующих условиях:

• Бензина каждого сорта должно быть произведено не менее 300 тыс.л.
• Неиспользованного крекинг бензина должно остаться не более 50 тыс.л.

Сводная таблица условий задачи:

Таблица 3

Компоненты, используемые для производства трёх видов бензина.	Сорта производимого  бензина			Объем ресурсов (тыс. л)
	А	В	С
Алкилат				400
Крекинг-бензин				250
Бензин прямой перегонки				300
Изопентат				250
Цена бензина (рублей за 1 тыс.л.)	120	100	150

 

 

4.2. Математическая постановка задачи

Исходя из условий задачи, необходимо максимизировать следующую целевую  функцию:       (1.1)

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

                 (1.2)

,   где  

В этих выражениях:

- объемы бензина А-го, В-го  и С-го сорта соответственно.

Тогда

объёмная доля первой компоненты (алкилата) в бензине А.

объёмная доля первой компоненты (алкилата) в бензине В.

объёмная доля первой компоненты (алкилата) в бензине С.

 и т.д.

Целевая функция  выражает стоимость всей продукции в зависимости от объема производимого бензина каждого сорта. Таким образом, для получения максимальной стоимости продукции необходимо максимизировать целевую функцию (1.1) с соблюдением всех условий задачи, которые накладывают ограничения (1.2) на .

 

4.3. Приведение задачи к канонической форме

 

Задача линейного программирования записана в канонической форме, если она формулируется следующим образом.

Требуется найти вектор , доставляющий максимум линейной форме

        (2.1)

при условиях

        (2.2)

         (2.3)

где

Перепишем исходную задачу (1.1) - (1.2):

      (2.4)

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

                 (2.5)

          ,   где                                                                            (2.6)

В канонической форме  задачи линейного программирования необходимо, чтобы все компоненты искомого вектора Х были неотрицательными, а все остальные ограничения записывались в виде уравнений. Т.е. в задаче обязательно будут присутствовать условия вида (2.3) и 8 уравнений вида (2.2), обусловленных неравенствами (2.5), (2.6).

Число ограничений задачи, приводящих к уравнениям (2.2) можно  уменьшить, если перед приведением  исходной задачи (2.4) - (2.6) к канонической форме мы преобразуем неравенства (2.6) к виду (2.3). Для этого перенесем свободные члены правых частей неравенств (2.6) в левые части. Таким образом, от старых переменных перейдем к новым переменным , где :

, .

Выразим теперь старые переменные через  новые

,                   (2.7)

и подставим их в линейную форму (2.4) и в неравенства (2.5), (2.6). Получим

 

 

    

  , где .

 

Раскрывая скобки и учитывая, что 

                                                   (2.8)

можем окончательно записать:

                                     (2.9)

                                        (2.10)

  ,   где                                                                          (2.11)

 

Путем несложных преобразований задачу (1.1), (1.2) свели к задаче (2.9) - (2.11) с меньшим числом ограничений. Для записи неравенств (2.10) в виде уравнений введем неотрицательные дополнительные переменные , и задача (2.9) - (2.11) запишется в следующей эквивалентной форме:

               (2.12)

                      (2.13)

          ,   где        

Задача (2.12), (2.13) имеет  каноническую форму.

 

4.4. Постановка L-задачи

 

Вспомогательная задача для нахождения начального опорного плана задачи (2.12) - (2.13) в канонической форме состоит в следующем.

Требуется обратить в  максимум

при условиях

,   где   .

Здесь добавление только одной дополнительной переменной (вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий А_4, А_5, А_6, А_7.

 

4.5. Решение L-задачи

 

Решение L-задачи будем проводить в соответствии с первым алгоритмом симплекс-метода. Составим таблицу, соответствующую исходному опорному плану (0-й итерации).

Т.к. Б₀ =  - базис, соответствующий известному опорному плану , является единичной матрицей, то коэффициенты разложения векторов А_j по базису Б₀

.

Значение линейной формы  и оценки для заполнения (m+1)-й строки таблицы определяются следующими соотношениями:

,

.

Отсюда получим:

;

;

;

…

.

Весь процесс решения  задачи приведен в таблице, которая состоит из 2 частей, отвечающих 0-й (исходная таблица) и 1-й итерациям.

Заполняем таблицу 0-й  итерации.

Среди оценок имеются отрицательные. Значит, исходный опорный план не является оптимальным. Перейдем к новому базису. В базис будет введен вектор А₁ с наименьшей оценкой . Значения t вычисляются для всех позиций столбца t (т.к. все элементы разрешающего столбца положительны). Наименьший элемент достигается на пятой позиции базиса. Значит, пятая строка является разрешающей строкой, и вектор А₉ подлежит исключению из базиса.