Симплексный метод решения задач

 

Рассмотрим исходную таблицу 6 а) подробнее.

В столбцах, соответствующим обозначениям в первых трёх строках записана наша система уравнений в предпочтительном виде; над символами прописаны значения коэффициентов целевой функции при соответствующих переменных 9,10,16,0,0,0.

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

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

Последняя четвёртая строка заполняется в последнюю очередь. Это строка F или индексная строка. Её коэффициенты получают по формуле.

 для колонки b,

где пронумерованные коэффициенты целевой функции (в колонке ); – матрица коэффициентов системы уравнения, - значения коэффициентов целевой функции, прописанных над  ,  -значении в колонке .

Например:

в строке в колонке значение –9 получается как

в колонке :  

в колонке :

Полученное число в строке и колонке является значением целевой функции для данного базисного решения системы ограничения.

Таким образом, мы определили, как формируется первая симплексная таблица (в нашем случае табл. 6,а)).

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

1) Пусть исходное задание решается на максимум. Если для некоторого опорного плана все элементы индексной строки неотрицательны, то такой план оптимальный.

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

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

Найдём в индексной строке число, наиболее сильно отличающегося от условия неотрицательности. Это –16 в колонке . Значит, столбец будет разрешающим. В этом столбце среди положительных элементов матрицы система, т.е. среди  чисел 12,8,3 найдём разрешающий элемент. Для этого найдём симплексное отношение для этих чисел, т.е. отношение вида , т.е. и найдём среди них минимальное. Это . Значит, число 8 есть разрешающий элемент и вторая строка сверху будет разрешающей. По разрешающей строке определяем,  что из разряда базисных переходит в разряд свободных переменных, а по разрешающему столбцу находим, что х3 из свободных переходит в базисные. Проводим преобразование старой симплекс-таблицы 6,а) в новую  6,б). Преобразования проводится по методу Жордана – Гаусса. Это и есть симплексное преобразование.

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

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

 

 

 

 

 

 

Тогда в новой матрице:

Например: число 18 в колонке преобразуется как ;

Число 5 в колонке преобразуется как .

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

Например: -9 в индексной строке преобразуется по правилу прямоугольника как

         

Это же число можно получить как

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

Таким образом, получим вторую симплекс таблицу (табл.  6,б)).

Рассмотрим её индексную строку. В колонке х2 есть отрицательный элемент (-2). Это означает, что полученное решение не оптимально, и значения =384 не является максимальным. Необходимо новое преобразование. В индексной строке отрицательное число (-2) (оно единственно) указывает на разрешающий столбец и на переменную , которое переходит из свободной в базисную.

Для положительных элементов столбца определим симплексное отношение и выберем минимальное.

.

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

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

Новая таблица 6,в) в индексной строке содержит только неотрицательные элементы. Это означает, что полученное базисное решение оптимально, а целевая функция =400 –максимальна. Полученное решение Х=(0,8,20,0,0,96).

 

 

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

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