Симплекс метод 1 страница

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

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

Пусть требуется найти максимальное значение функции

при условиях

Здесь и — заданные постоянные числа

Векторная форма данной задачи имеет следующий вид: найти максимум функции

(22)

при условиях

(23)

(24)

где

Так как

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

Положим Так как векторы — единичные, то и а

Теорема 1.5 (признак оптимальности опорного плана). Опорный план задачи (22)-(24) является оптимальным, если для любого j

Теорема 1.6. Если для некоторого j=k и среди чисел нет положительных , то целевая функция (22) задачи (22)-(24) не ограничена на множестве ее планов.

Теорема 1.7. Если опорный план Х задачи (22)-(24) не вырожден и , но среди чисел а_ik есть положительные (не все ), то существует опорный план X' такой, что

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

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

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

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

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

Значение находится как скалярное произведение вектора на вектор

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

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

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

2) для некоторого j, и все соответствующие этому индексу величины

3) для некоторых индексов j, и для каждого такого j, по крайней мере, одно из чисел положительно.

Таблица 3

i

Базис

P 0

...

...

...

...

...

...

...

...

...

...

...

...

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

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

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

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

(25)

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

(26)

После вычисления и согласно формулам (25) и (26) их значения заносят в табл. 4.

Таблица 4

i

Базис

P 0

...

...

...

...

...

...

...

...

...

...

...

...

Элементы -й строки этой таблицы могут быть вычислены либо по формулам

(27)

(28)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.8. Для изготовления различных изделий А, В и С предприятие использует три различных вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А, В и С, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в таблице 5.

Таблица 5

Вид сырья	Нормы затрат сырья (кг) на одно изделие	Общее количество сырья (кг)
А	В	С
I II III
Цена одного изделия (руб.)

Изделия А, В и С могут производиться в любых соотношениях (сбыт обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида.

Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной.

Решение. Составим математическую модель задачи. Искомый выпуск изделий А обозначим через , изделий В — через , изделий С — через . Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные должны удовлетворять следующей системе неравенств:

(29)

Общая стоимость произведенной предприятием продукции при условии выпуска изделий А, изделий В и изделий С составляет

(30)

По своему экономическому содержанию переменные могут принимать только лишь неотрицательные значения:

(31)

Таким образом, приходим к следующей математической задаче: среди всех неотрицательных решений системы неравенств (29) требуется найти такое, при котором функция (30) принимает максимальное значение.

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений

Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, — это неиспользуемое количество сырья I вида.

Преобразованную систему уравнений запишем в векторной форме:

где

Поскольку среди векторов имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план Х =(0; 0; 0; 360; 192; 180), определяемый системой трехмерных единичных векторов которые образуют базис трехмерного векторного пространства.

Составляем симплексную таблицу для I итерации (таблица 6), подсчитываем значения и проверяем исходный опорный план на оптимальность:

Для векторов базиса

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

Дата добавления: 2014-12-27