![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод искусственного базиса (М-задача)
До сих пор при изложении симплексного метода предполагалось, что система исследуемых уравнений решена относительно базисных переменных, т. е приведена к единичному базису, и все Bi≥ 0. Мы уже видели, что с помощью симплексных преобразований этого можно всегда добиться. Однако расчеты, с которыми сопряжены эти преобразования, порой оказываются даже более громоздкими, нежели последующие вычисления в симплексных таблицах. Поэтому рассмотрим другой метод, который связан с решением той же задачи определения исходного опорного решения и получивший название метода искусственного базиса Он особенно удобен, когда число переменных значительно превосходит число уравнений. Заметим, что в некоторых случаях получение исходного опорного решения не вызывает осложнений и не требует применения специальных приемов. Так, например, система исходных ограничений может оказаться сразу заданной в приведенном к единому базису виде с неотрицательными свободными членами. Иногда исходные ограничения могут выражаться неравенствами вида ai1 x1+ai2x2+…+ain xn≤ ai0 где аi0≥ 0. Тогда, вводя балансовые переменные, получим эквивалентную систему уравнений, разрешенную относительно этих балансовых переменных. Пусть задана каноническая форма задачи линейного программирования.
Максимизировать линейную функцию Z=c1 x1+с2 х2+…+сk хk +…cn xn
в области решений системы уравнений
a21x21+a22x22+…+a2nxn=b2 ………………………………………….. ai1xi1+ai2xi2+…+ainxn=bi ………………………………………….. am1xm1+am2xm2+…+amnxn=bm
x1 ≥ 0; x2 ≥ 0; …; xn ≥ 0
Среди уравнений системы могут оказаться некоторые линейно зависимые от остальных, т. е. ранг систем может быть меньше, чем m, однако в излагаемом методе нет необходимости в предварительном определении ранга системы и отбрасывании “лишних” уравнений. Будем полагать, что все aio ≥ 0. Очевидно, этого всегда можно добиться умножением соответствующего уравнения на множитель —1.
a21x1+a22x2+…+a2nxn+xn+2= b2 ……………………………… ai1x1+ai2x2+…+ainxn+xn+i= bi ………………………………………………. am1x1+am2x2+…+amnxn+xn+m= bm
получаемую из исходной системы введением m неотрицательных переменных хn+1 ≥ 0; хn+2 ≥ 0; …; хn+m ≥ 0, именуемых искусственными. Исходная система уравнений приведена к единичному базису {
Рассмотрим любое допустимое решение Если в этом решении все искусственные переменные равны нулю (аn+1= … аn+m=0), то первые n чисел определяют допустимое решение( Наоборот, если
По этой причине будем решения Составим новую целевую функцию: T=z – M * где М — произвольно большое число, и будем максимизировать ее в области допустимых решений исходной системы. Полученными соотношениями определяется новая задача, которую назовем М-задачей. Эта задача может решаться симплексным методом. При этом на основании вышеизложенного через конечное число итераций либо будет найдено ее оптимальное решение, либо установлено, что функция Т → ∞. Оказывается, что между оптимальными решениями М-задачи и исходной существует связь, устанавливаемая следующей теоремой. Теорема 1. Если в оптимальном решении М-задачи
Теорема 2. Если имеется оптимальное решение М-задачи, в котором хоть одна из искусственных переменных отлична от нуля, то система ограничений исходной задачи несовместна в области допустимых решений.
Теорема 3. Если М-задача оказалась неразрешимой (Т → ∞), то исходная задача также неразрешима либо по причин несовместности системы (23) в области допустимых решений, либо по причине неограниченности функции z (zmax → ∞).
Рассмотрим практическое применение метода искусственного базиса. Дана математическая модель задачи:
F (x) = 5x1 + 6x2 + 7x3 + 4x4 → min
x1 + x2 + 4x4 > = 26 2x1 + 3x3 + 5x4 > = 30 x1 + 2x2 + 4x3 + 6x4 > = 24 xj > =0 j = 1÷ 4
Приведем задачу к канонической форме:
F (x) = 5x1 + 6x2 + 7x3 + 4x4 → min F (x) = -5x1 -6x2 -7x3 - 4x4 → max
Введем балансовые переменные х5, х6, х7
2x1 + 3x3 + 5x4 – x6 = 30 x1 + 2x2 + 4x3 + 6x4 – x7 = 24
Т.к. введенные балансовые переменные имеют знак «-», то принять их за базисные нельзя.Поэтому введем искусственные переменные х8, х9, х10.
2x1 + 3x3 + 5x4 – x6 + x9 = 30 x1 + 2x2 + 4x3 + 6x4 – x7 + x10 = 24
xj > =0 j = 1÷ 10
Заполним симплексную таблицу и используя алгоритм модифицированного симплексного метода найдем оптимальное решение.
Так как среди элементов оценочной строки нет ни одного отрицательного, то решение считается оптимальным.
F (x)min = - F(x)max = - (-26) = 26 x = (0, 0, 0, 13/2, 0, 5/2, 15, 0, 0, 0)
Таблица 4. Симплексная таблица
Контрольные вопросы и упражнения
а) F(x)= -7x1+3x2 g max
-x1+x2 < _ 7 -2x1+x2 < _ 10 x1 > _ 0, x2 > _ 0 Ответ: F(x)=21; X=(0, 7, 5, 0, 3, 0) б) F=x1+x2 g max
x1+2x2 > _ 2 2x1+x2< _ 10 x1 > _ 0, x2 > _ 0 Ответ: F(x)=20/3; X=(10/3; 10/3; 8; 0; 0; 0) в) F=x1-x2 g max
-x1+2x2 > _ 8 x1+x2< _ 5 x1 > _ 0, x2 > _ 0 Ответ: нет решения г)F=2x1-6x2 g max
-x1+2x2 < _ 4 x1+2x2< _ 8 x1 > _ 0, x2 > _ 0 Ответ: F(x)=16; X=(8; 0, 6; 12; 0; 0)
|