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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

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

Решение задачи при помощи симплекс-метода распадается на ряд шагов. В каждой вершине многогранника будет m ненулевых координат, которые образуют базис. Остальные (n-m) координат входят в набор небазисных (свободных) переменных. На каждом k-м шаге от данного базиса Бk переходят к другому, новому базису Бk+ 1 с таким расчетом, чтобы значение функции f(x) увеличивалось, т. е. fБk+1≥fБk. Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис Б k*, для которого fБ(k*) есть искомый максимум для линейной функции f, а соответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения.

 

 

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

Целевая функция вида:

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

,

Переобозначим свободные коэффициенты ограничений aj0=bj. Приведем матрицу ограничений к каноническому виду:

(4.1)

Используя метод Гаусса - Жордана, приведем записанную систему к виду, где выделены базисные переменные. Метод Гаусса — Жордана (метод полного исключения неизвестных) — метод, который используется для решения квадратных систем линейных алгебраических уравнений, нахождения обратной матрицы, нахождения координат вектора в заданном базисе или отыскания ранга матрицы. Метод является модификацией метода Гаусса. Назван в честь К. Ф. Гаусса и немецкого геодезиста и математика Вильгельма Йордана (Транскрипция фамилии Йордан как «Жордан» является ошибочной, но она общепринята и встречается в большинстве русскоязычных источников).

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

По последней системе ограничений и целевой функции в каноническом виде построим симплекс-таблицу.

 

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

 

  С С1 С2 С3 Сj Cn    
Bx A0 A1 A2 A3 Aj An An+1 An+m
xn+1 a10 a11 a12 a13 a1j a1n    
xn+2 a20 a21 a22 a23 a2j a2n    
 
xn+i ai0 ai1 ai2 ai3 aij ain    
 
xn+m am0 am1 am2 am3 amj amn    
L a00 a01 a02 a03 a0j a0n a0m+1 a0m+n

Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Нижняя строка элементов аок, к = 0,…, т+п называется индексной. Элементы индексной строки вычисляются следующим образом:

означает номер соответствующей строки.

Поскольку на первом шаге заполнения таблицы все элементы сn+i равны нулю, то элементам индексной строки присваиваются значения соответствующих элементов целевой функции данного столбца, взятые с обратным знаком, т.е. аok= к. Последняя строка таблицы служит для определения направляющего столбца.

Элемент а00 равен значению целевой функции, которое вычисляется по формуле - номер базисной переменной (индексация идет по строкам таблицы).

В столбце Вх записываются базисные переменные, на первом шаге в качестве базисных выбирают фиктивные переменные п+к }, к =1,…,т. В дальнейшем фиктивные переменные необходимо вывести из базиса.

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

Далее выполняются преобразования в соответствии с алгоритмом симплекс -метода.

Алгоритм симплекс-метода:

Этап 1. Находится начальное допустимое базисное решение

Этап 2. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, вычисления заканчиваются.

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

Этап 3. На основе условия допустимости выбирается исключаемая переменная.

3.1. Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплекс - отношений, оно соответствует разрешающей строке. То есть разрешающая строка соответствует той из базисных переменных, которая будет увеличиваться меньше других. Если таких переменных нет (все ai,вед. ≤0), то задача неразрешима.

3.2. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

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

Этап 4. Методом Гаусса - Жордана вычисляется новое базисное решение. Переход к этапу 1.

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

4.2. Вычисление элементов новой таблицы выполняется так.

Новая ведущая строка =текущая разрешающая строка / разрешающий элемент.

Для элементов остальных строк:

Новая строка = текущая строка – ее коэффициент в разрешающем столбце ×новая разрешающая строка.

 

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

 

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

Рассмотрим следующую задачу. Компания производит краску для внутренних и наружных работ из сырья двух типов: М1 и М2. Существуют ограничения на расход сырья (таблица 2) и ограничения по спросу на готовую продукцию. Первое ограничение указывает, что ежедневный объем производства краски для внутренних работ не должен превышать ежедневный объем производства краски для наружных работ более, чем на одну тонну. Второе ограничение таково: максимальный ежедневный объем производства краски для внутренних работ не должен превышать 2 т.

 

Таблица 2. Исходные данные по расходу сырья.

 

  Расход сырья (в тоннах) на тонну краски Максимально возможный ежедневный расход сырья
для наружных работ для наружных работ
Сырье М1      
Сырье М2      
Доход (в тыс. долл.) на тонну краски      

 

Сформулируем задачу линейного программирования в следующем виде: найти максимум линейной формы 5х1 + 4 х2 при ограничениях

6x1 + 4 х2 ≤ 24;

x1 + 2 х2 ≤ 6;

-x1 + х2 ≤ 1;

х2 ≤ 2;

х 1, х 2 > 0.

 

 

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

5 x 1 + 4 x 2 + 0 x 3 + 0 x 4 + 0 x 5 + 0 x 6max;

6 х 1 + 4 х 2 + 1 х 3 + 0 x 4 + 0 x 5 + 0 x 6= 24;

х 1 + 2 х 2 + 0 х 3 + 1 x 4 + 0 x 5 + 0 x 6= 6;

- х 1 + х 2 + 0 х 3 + 0 x 4 + 1 x 5 + 0 x 6= 1;

х 2+ 0 х 3 + 0 x 4 + 0 x 5 + 1 x 6=2;

xi ≥0, i =1,…,6

 

Составим исходную симплекс-таблицу (табл. 3).

 

Таблица 3

  С            
Bx A0 A1 A2 A3 A4 A5 A6
хз              
x4              
x5   -1          
x6              
    -5 -4        

 

Небазисные (нулевые) переменные х 1 и х 2; базисные переменные х 3, x 4, x 5, x 6

Поскольку -5 < -4 < 0, то в качестве направляющего выбираем столбец A 1. Составив отношение вида , определяем направляющую строку. Для этого находим минимальное отношение

min Следовательно, направляющая строка - первая, направляющий элемент — а11=1- Применив первый шаг симплексного преобразования, получим новую таблицу (табл. 4).

Таблица 4

  С            
Bx A0 A1 A2 A3 A4 A5 A6
x1          
x4          
x5          
x6              
      -      

 

На данном этапе в качестве направляющего столбца выбираем второй, направляющая строка - третья, т.к. из наименьший элемент равен 3/2. Применим следующий шаг симплексного преобразования. В результате получим табл. 5.

 

Табл. 5.

               
Bx A0 A1 A2 A3 A4 A5 A6
x1          
x2        
X2        
         
           

 

Поскольку в индексной строке все элементы положительны, это означает, что найдено оптимальное решение х1*= 3, х2 = , искомое значение целевой функции равно 5 х1 + 4х2= 21.



Поделиться:


Последнее изменение этой страницы: 2017-02-07; просмотров: 337; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.211.148.68 (0.033 с.)