Здавалка
Главная | Обратная связь

Симплекс метод с искусственным базисом



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

Алгоритм решения можно разобрать на примере конкретной задачи.

Задача. В фирме производятся четыре вида продукции из двух видов сырья. Причем в условиях данной фирмы расход первого вида ресурса могут превышать 9,4 ед., а второго вида полностью нужно использовать. При этом количество первого вида продукции не может превышать более 2,5 ед., а четвертого вида более 5 ед. Расход ресурсов по видам продукции и себестоимость его характеризуется следующими данными таблицы 5.

Таблица 5

 

Продукция сырье 1 сырье 2 Себестоимость ед. продукции
№1 №2 №3 №4 0,2 0,12 0,5 0,5 1,4 2,0

 

Обозначим через х1, х2, х3, х4 виды продукции. Тогда условия задачи запишутся следующей системой уравнений и неравенств:

 

х1+0,2х2+0,12х3+ 0,5х4>= 9.4

100х1+14х2 + 9х3+ 79х4 = 987

х1 <= 2.5

х4 <= 5

Все неизвестные должны быть неотрицательными: и минимизировать линейную функцию

Fmin = 3х1+0,5х2+1,4х3+2х4.

Задача приводится к каноническому виду с помощью дополнительных переменных х5, х6, х7 :

х1+0,2х2+0,12х3+ 0,5х4 - х5 = 9.4

100х1+14х2 + 9х3+ 79х4 = 987

х1 + х6 = 2.5

х4 + х7 = 5

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

Для получения исходного базисного решения в эти уравнения вводят искусственные неизвестныеy1 и y2 с положительным единичным коэффициентом, а в целевую функцию - с очень большой оценкой М. При решении задач на максимум она вводится с отрицательным знаком, при решении задач на минимум - с положительным. Такая оценка делает невыгодным наличие искусственных неизвестных в плане и способствует их выводу из базиса. С введением искусственных неизвестных задача примет вид.

х1+0,2х2+0,12х3+ 0,5х4 - х5 + у1 =9.4

100х1+14х2 + 9х3+ 79х42 =987

х1 + х6 = 2.5

х4 7 = 5

Все неизвестные должны быть неотрицательными, а линейная форма записи будет иметь вид

 

Fmin = 3х1+0,5х2+1,4х3+2х4 +0х5 + 0х6 + 0х7 + Му1 +Му2 .

Составим первую симплексную таблицу. В первой таблице по строкам, ограничения которых заданы типом (>=) в базис вводятся искусственные переменные, а по строкам с ограничениями (<=) - дополнительные переменные.

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

 

Таблица 6

Базис вi х1 х2 х3 х4 х5 х6 х7 у1 у2 Q
у1 9.4 0.2 0.12 0.5 -1 9.4
у2 9.87
3 х6 2.5 2.5
х7 5.0  
m+1 F -3 -0.5 -1.4 -2  
m+2   996.4М 101М 14.2М 9.12М 79.5М М М

Алгоритм решения задачи с искусственным базисом тот же, что и с естественным базисом. Только разрешающий столбец определяется по строке m+2, т.е. по нижнему ряду индексной строки. При решении задачи на максимум разрешающий столбец также определяется по наибольшему абсолютному значению среди отрицательных величин, а при решении на минимум - по наибольшему положительному значению. Разрешающая строка, как и при естественном базисе, выбирается по наименьшему частному от построчного деления свободных членов на соответствующие положительные коэффициенты разрешающего столбца. Весь пересчет ведется по тем же правилам, что и при алгоритме решения с естественным базисом. Строки m+1 и m+2 рассчитываются отдельно. Проверка правильности их расчета определяется по строке m+1 по общему правилу как Fj -Cj, а по строке m+2 - как сумма коэффициентов столбца по строкам, имеющим М- оценки.

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

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

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

В том случае, когда все искусственные переменные выведены из базиса, по строке m+2 получены нули, в строке m +1 при решении на минимум получены нули и отрицательные величины, а при решении на максимум - нули и положительные величины, план оптимален.

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

Таблица 7

базис вi х1 х2 х3 х4 х5 х6 х7 у1 у2 Q
х1 2.5 -
х7
у1 6.9 0.2 0.12 0.5 -1 -1 13,8
у2 -100 9,3
m+1 F 7.5 -0.5 -1.4 -2  
m+2   743,9М 14.2М 9.12М 79.5М -101М  

 

Значение индексной строки m+2 таблицы 3 свидетельствует о том, что план можно улучшать дальше и что в базис надо ввести х4, а вывести х7.

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

Таблица 8

базис вi х1 х2 х3 х4 х5 х6 х7 у1 у2 Q
х4 -
х1 2.5 -
3 у1 4.4 0.2 0.12 -1 -1 -0.5 0.5
у2 -100 -79 24.4
m+1 F 17.5 -0.5 -1.4  
m+2   346.4M 14.2M 9.12M -M -101M -79.5M  

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

Таблица 9

базис вi х1 х2 х3 х4 х5 х6 х7 у2 Q
х2 0.6 -5 -5 -2.5  
х1  
х4 2.5  
у2 0.6 -30 -44 0.5
m+1 F 28.5 -1.1 -2.5 0.5 0.75  
m+2   0.6M 70M -30M -44M  

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

Таблица 10

базис вi x1 x2 x3 x4 x5 x6 x7 Q
x5 0.48 0.0085 -0.43 -0.63  
x1 2.5  
x2 24.4 0.6425 -7.15 -5.65  
x4  
m+1 F 29.7 -1.078 -0.57 -0.82  
m+2    

Оптимальный план получен при следующих значениях переменных:

 

х1=2.5; х2=24.4; х3=0; х4= 5; x5=0.48; х6=0; х7=0; у1=0; у2=0;

Fmin =29.7

Следовательно, в оптимальный план вошли продукции вида №1, №2, №4. При этом минимальная себестоимость продукции 29,7 ден. ед.

З А Д А Н И Я







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.