Симплекс метод с искусственным базисом
В задачах, ограничения которых заданы неравенством типа (>=) дополнительные неизвестные вводятся с отрицательным единичным коэффициентом, поэтому они не могут образовывать естественный базис. Подобные задачи решаются при помощи искусственного базиса, который в литературе встречается также под названием М-метода. Методом искусственного базиса решаются также задачи с жесткими ограничениями, заданными равенствами. Алгоритм решения можно разобрать на примере конкретной задачи. Задача. В фирме производятся четыре вида продукции из двух видов сырья. Причем в условиях данной фирмы расход первого вида ресурса могут превышать 9,4 ед., а второго вида полностью нужно использовать. При этом количество первого вида продукции не может превышать более 2,5 ед., а четвертого вида более 5 ед. Расход ресурсов по видам продукции и себестоимость его характеризуется следующими данными таблицы 5. Таблица 5
Обозначим через х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х4 +у2 =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
Алгоритм решения задачи с искусственным базисом тот же, что и с естественным базисом. Только разрешающий столбец определяется по строке 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
Значение индексной строки m+2 таблицы 3 свидетельствует о том, что план можно улучшать дальше и что в базис надо ввести х4, а вывести х7. В симплексной таблице 8 разрешающий столбец - х2, а разрешающая строка - третья. Следовательно, из базиса должен быть выведен у1, а на его место введен х2. В связи с тем, что у1 выведен из базиса, столбец у1 в следующей таблице не рассчитывается. Таблица 8
В таблице 9 также не достигнут оптимальный план. За разрешающий столбец принимается столбец х5, а за разрешающую строку - у2. В результате из базиса необходимо вывести у2, а на его место ввести х5 . Столбец у2 также не рассчитывается. Таблица 9
В следующей таблице получен оптимальный план, так как все искусственные переменные из базиса выведены, по строке m+2 все значения равны нулю, а в строке m+1 все значения или отрицательны, или равны нулю. Таблица 10
Оптимальный план получен при следующих значениях переменных:
х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 Все права принадлежат авторам размещенных материалов.
|