Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Симплексные таблицы


⇐ ПредыдущаяСтр 7 из 21Следующая ⇒




В табл. 2 занесена исходная расширенная система (8). Рабочая часть таблицы (начиная с 3-го столбца и с 3-й строки) содержит элементы расширенной матрицы системы, над которыми будут производиться преобразования, согласно формулам (11) и {12).

Последний столбец предназначен для выбора разрешающей строки, В последней строке таблицы записано «нулевое» уравнение (для функции z). Эта строка называется индексной, или оценочной, строкой.

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

Рядом в третьем столбце помещены свободные члены уравнений. Такое расположение позволяет легче прочесть соответствующее данной таблице опорное решение.

Сверху над рабочей частью таблицы, как обычно, указаны все переменные. Первые строка и столбец таблицы предназначены для расчетов по формуле (7) элементов индексной строки. При этом в исходной таблице они используются для получения приведенного выражения (б), а в последующих таблицах, так как элементы индексной строки подчиняются той же формуле преобразования (12), расчет по формуле (7) используется для контроля вычислений. Этот расчет производится так: для вычисления элемента индексной строки а0k, находится сумма попарных произведений чисел 1-го столбца на соответствующие числа 1-го столбца (т. е. ) и вычитается число, стоящее в 1-м столбце сверху (т е. ck). После того как исходная таблица заполнена, приступаем к выполнению первой (а в дальнейшем к очередной) итерации согласно указанному в предыдущем параграфе алгоритму.

 

Этот исходный пункт будет выглядеть так:

Следует лишь 1-му пункту алгоритма предпослать пункт, содержащий анализ элементов индексной строки (оценок) согласно ключевой теореме.

 

Таблица 2. Симплексная таблица

ci xi -c0 c1 c2 … cq … cr cr+1 … ck … cp … cn
bi x1 x2 … xq … xr xr+1 … xk … xp … xn
c1 x1 b1             a1r+1 … a1k … a1p … a1n  
c2 x2 b2             a2r+1 … a2k … a2p … a2n  
… … …             …   …   …   …  
ci xi bi             air+1 … aik … aip … ain  
… … …             …   …   …   …  
cq xq bq             aqr+1 … aqk … aqp …. aqn aq0: aqp
… … …             …   …   …   ...  
cr xr br     …   …   arr+1 … ark … ark …. arn  
  z b00             a0r+1   a0k   a0k   a0n  

 

Анализируются оценки а0k индексной строки. Если имеет место 1-й случай, указанный в теореме, то переходим к следующему пункту алгоритма, если имеет место 2-й случай или 3-й, то расчет прекращается. При этом во втором случае заключаем, что Zmax → ∞, а в 3-м случае выписываем из таблицы достигнутое оптимальное решение.

Выполнив 1-й и 2-й пункты алгоритма, переходим к заполнению новой таблицы согласно пунктам 3-му и 4-му.

На этом заканчивается одна итерация, после чего расчет повторяется в той же последовательности.

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

1. При заполнении очередной симплексной таблицы целесообразно придерживаться следующего порядка:

а) заполняется столбец 2-й, содержащий базисные переменные, и первый столбец с коэффициентами сi при этих переменных;

б) заполняются единичные столбцы занесением единиц на пересечении строки и столбца, соответствующих одной и той же переменной;

в) рассчитываются элементы разрешающей строки по формуле (11);

г) рассчитываются остальные элементы таблицы по формуле. (12), при этом расчет целесообразно Вести по столбцам;

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

2. Вычисления по формуле (12) можно производить по указанному выше “правилу прямоугольника”, а можно использовать уже вычисленную новую разрешающую строку. Для этого формулу (12) удобно записать в виде

 

(12)

3, Если в разрешающем столбце (или строке) имеется нулевой элемент, то соответствующая строка (столбец) переписываются в новую таблицу без изменения.

 

Рассмотрим задачу (пример 1)

Решение. Приведем к канонической форме модель задачи из примера 1, введя в каждое неравенство балансовую переменную.

 

F (x) = 30x1 + 40x2 + 0(x3 + x4 + x5) → max

 

 
 


12x1 + 4x2 + x3 = 300

4x1 + 4x2 + x4 = 120

3x1 + 12x2 + x5 =252

xj > =0 j = 1÷ 5

 

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

На основе канонической формы заполним симплексную таблицу(табл. 3) и используя алгоритм симплексного метода решим задачу.

Первый столбец содержит коэффициенты сj из целевой функции F (x) = 30x1 + 40x2 + 0(x3 + x4 + x5)

Второй столбец содержит балансовые переменные из системы ограничений на ресурсы.

Третий столбец содержит свободные члены из системы ограничений на ресурсы.

Первая строка содержит коэффициенты сj из целевой функции F (x) = 30x1 + 40x2 + 0(x3 + x4 + x5)

Вторая строка содержит переменные хj из системы ограничений на ресурсы.

Далее таблица заполняется по системе ограничений на ресурсы.

Используя алгоритм симплексного метода, решим задачу.

Вычисляем элементы оценочной строки:

0*300+0*120+0*252=0

(0*12+0*4+0*3)-30=-30 и т. д.

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

Определяем ведущий столбец как max по модулю отрицательный элемент оценочной строки (0.-30, -40, 0, 0, 0) - 40.

Вычисляем последний столбец:

300/4=75

120/4=30

252/12=21

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

В новую итерацию записываем ведущий столбец.

Все элементы ведущей строки делим на ведущий элемент и переписываем на тоже место, но уже в новую итерацию.

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

Остальные элементы пересчитываем по правилу прямоугольника.

 

В1= 300-((4*252)/12)=216

В2= 120-((4*252)/12=36 и т.д.

А11= 12-((4*3)/12=11

А21= 4-((4*3)/12=3 и т.д.

 

Далее алгоритм симплексного метода повторяют с вычисления оценочной строки (см. таблицу 3).

 

Так как среди элементов оценочной строки нет отрицательных, то полученное решение считают оптимальным.

F (x) = 1080

X = (12, 18, 84, 0, 0)

 

Таблица 3. Симплексная таблица

Cj Xj Bi           Bi/Aip
x1 x2 x3 x4 x5
  x3              
  x4              
  x5              
  Z   -30 -40        
  x3           -1/3 19, 7
  x4           -1/3  
  x2   1/4       1/12  
  Z   -20       10/3  
  x3         -11/3 8/9  
  x1         1/3 -1/9  
  x2         -1/12 1/9  
  Z         20/3 10/9  

 

Экономическая интерпретация:

Для получения максимальной прибыли от реализации продукции в размере 1080 у. е. предприятие должно выпускать продукции вида А – 12 ед., вида В – 18 ед. При этом сырье первого вида останется в избытке в количестве 84 ед., а сырье второго и третьего вида будут исчерпаны полностью.

 

Контрольные вопросы и упражнения

  1. Дайте определение линейного программирования.
  2. Какие условия являются необходимыми для постановки задачи линейного программирования?
  3. Что называется критерием оптимальности?
  4. Какие требования предъявляются к критерию оптимальности?
  5. В чем состоит общая задача линейного программирования?
  6. Как выглядит задача линейного программирования в матричной форме?
  7. Какая задача называется «Стандартной задачей линейного программирования»?
  8. Как перейти от задачи на MIN к задаче на MAX?
  9. Какая задача называется стандартной задачей линейного программирования?
  10. Что называется оптимальным планом?
  1. Как привести задачу линейного программирования к канонической форме?
  1. Какие правила нужно знать, чтобы заполнить симплексную таблицу?
  2. Для чего подсчитывают оценочную строку?
  3. Как выбрать ведущий столбец?
  4. Как выбрать ведущую строку?
  5. Перечислите основные шаги алгоритма симплексного метода?
  6. В каком случае говорят, что задача не имеет решения?
  7. Решить симплексным методом следующие задачи линейного программирования:

а) F=27x1 + 10x2 + 15x3 + 28x4 → max

3x1 + 2x2 + x3 + 2x4 ≤ 2,

3x1 + x2 + 3x3 + 4x4 ≤ 5

xj ≥ 0, j = 1, 2, 3, 4

Ответ: F(x) =29; X=(0, 0, 1, 1/2, 0, 0)

б) F=2x1 + 3x2 → max

x1 + 3x2 ≤ 18,

2x1 + x2 ≤ 16,

3x1 ≤ 21

xj ≥ 0, j=1, 2

Ответ: F(x) =24; X=(6, 4, 0, 0, 3)

в) F=10x1 + 14x2 + 12x3 → max

4x1 + 2x2 + x3 ≤ 180,

3x1 + x2 + 3x3 ≤ 210,

x1 + 2x2 + 5x3 ≤ 244

xj ≥ 0, j=1, 2, 3

Ответ: F(x) =1340; X=(0, 82, 16, 0, 80, 0)

 

г) F=4x1 + 3x2 + 6x3 + 7x4 → max

2x1 + x2 + x3 + x4 ≤ 280,

x1 + x3 + x4 ≤ 80,

x1 + 2x2 + x3 ≤ 250.

xj ≥ 0, j = 1, 2, 3, 4

 

Ответ: F(x) =935; X=(0, 125, 0, 80, 75, 0, 0)

 

18. Тест к теме «Линейное программирование. Симплексный метод»


⇐ Предыдущая234567891011Следующая ⇒
Поделиться с друзьями:
mylektsii.su - Мои Лекции - 2015-2025 год. (0.014 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал