Вредоносное ПО (malware) - это назойливые или опасные программы,...
Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач симплекс-методом. Первая задача содержит знаки неравенства только " ≤ " (задача с начальным базисом), вторая может содержить знаки " ≥ ", " ≤ " или " = " (задача с искусственным базисом), они решаются по разному.
Симплекс-метод, решение задачи с начальным базисом
1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ≤ ").
Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:
Эта система является системой с базисом (базис s 1 , s 2 , s 3 , каждая из них входит только в одно уравнение системы с коэффициентом 1), x 1 и x 2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами: -система ограничений должна быть системой уравнений с базисом; -свободные члены всех уравнений в системе должны быть неотрицательны.
Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод . Составим первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод , т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.
симплекс-метод итерация 0
Отношение |
|||||||
Для улучшения решения перейдем к следующей итерации симплекс-метода , получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец , т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации симплекс-метода это столбец x 2 (коэффициент -6).
Затем выбирается разрешающая строка , т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s 3 (коэффициент 20).
Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации симплекс-метода переменная x 2 заменит в базисе s 1 . Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.
Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х 2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).
1)Вычисление строки х 2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s 3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x 2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s 3 таблицы "Итерация 0" будет совпадать со строкой х 2 таблицы "Итерация 1". Строку x 2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:
2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x 2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом.
3) Вычисление строки s 1 таблицы "Итерация 1". На месте 1 в s 1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х 2 получен необходимый 0.
4) Вычисление строки s 2 таблицы "Итерация 1". На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х 2 получен нужный 0. Столбец х 2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0.
Строки таблицы «Итерация 1» получаем по следующему правилу:
Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).
Например для z-строки имеем:
Старая z-строка (-4 -6 0 0 0 0) -(-6)*Новая разрешающая строка -(0 -6 0 0 -6 -120) =Новая z-строка (-4 0 0 0 6 120).
Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем.
симплекс-метод итерация 1
Отношение |
|||||||
Разрешающий столбец х 1 , разрешающая строка s 2 , s 2 выходит из базиса, х 1 входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.
симплекс-метод итерация 2
Отношение |
|||||||
Разрешающий столбец s 3 , разрешающая строка s 1 , s 1 выходит из базиса, s 3 входит в базис.
симплекс-метод итерация 3
Отношение |
|||||||
В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x 1 = 24, x 2 = 16, z max = 192.
Шаг 0. Подготовительный этап.
Приводим задачу ЛП к специальной форме (15).
Шаг 1. Составляем симплекс-таблицу , соответствующую специальной форме:
Заметим,
что этой таблице соответствует допустимое
базисное решение
задачи (15). Значение целевой функции на
этом решении
Шаг 2. Проверка на оптимальность
Если
среди элементов индексной строки
симплекс – таблицы
нет ни одного положительного элемента
то
,
оптимальное решение задачи ЛП найдено:.
Алгоритм завершает работу.
Шаг 3. Проверка на неразрешимость
Если
среди
есть положительный элемент
,
а в соответствующем столбце
нет ни одного положительного элемента
,
то целевая функцияL
является неограниченной снизу на
допустимом множестве. В этом случае
оптимального решения не существует.
Алгоритм завершает работу.
Шаг 4. Выбор ведущего столбца q
Среди
элементов
выбираем максимальный положительный
элемент
.Этот
столбец объявляем ведущим (разрешающим).
Шаг 5. Выбор ведущей строки p
Среди
положительных элементов столбца
находим элемент
,
для которого выполняется равенство
.
Строку
p
объявляем ведущей (разрешающей). Элемент
объявляем ведущим (разрешающим).
Шаг 6. Преобразование симплексной таблицы
Составляем новую симплекс-таблицу, в которой:
а) вместо базисной переменной записываем, вместо небазисной пере меннойзаписываем;
б)
ведущий элемент заменяем обратной
величиной
;
в)
все элементы ведущего столбца (кроме
)
умножаем на
;
г)
все элементы ведущей строки (кроме
)
умножаем на;
д) оставшиеся элементы симплексной таблицы преобразуются по следующей схеме «прямоугольника».
Из элемента вычитается произведение трех сомножителей:
первый – соответствующий элемент ведущего столбца;
второй – соответствующий элемент ведущей строки;
третий
– обратная величина ведущего элемента
.
Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».
Шаг 7. Переход к следующей итерации осуществляется возвратом к шагу 2.
2.3. Алгоритм симплекс-метода для задачи на максимум
Алгоритм
симплекс-метода для задачи на максимум
отличается от алгоритма для задачи на
минимум только знаками индексной строки
коэффициентов в целевой функции
,
а именно:
На
шаге 2:
:
На
шаге 3
.
Целевая функция является неограниченной
сверху на допустимом множестве.
На
шаге 4
:
.
2.4. Пример решения задачи симплекс-методом
Решить задачу, записанную в виде (15).
Составим симплексную таблицу:
Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение не является оптимальным. Значение целевой функции для этого базисаL=0.
Выбираем ведущий столбец – это столбец, соответствующий переменной .
Выбираем
ведущую строку. Для этого находим
.
Следовательно, ведущая строка соответствует
переменной.
Проводим преобразование симплексной таблицы, вводя переменную в базис и выводя переменнуюиз базиса. Получим таблицу:
Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальная. Базисное решение, соответствующее таблице, имеет вид . Значение целевой функции на этом базисеL= -2 .
Ведущий столбец здесь – столбец, соответствующий переменной . Ведущая строка – строка, соответствующая переменной. После проведения преобразований получим симплексную таблицу:
Еще одна итерация завершена. Переходим к новой итерации.
Строка целевой функции не содержит положительных значений, значит, соответствующее базисное решение является оптимальным, и алгоритм завершает работу.
Если вам понадобится решить задачу линейного программирования с помощью симплекс-таблиц, то наш онлайн сервис вам окажет большую помощь. Симплекс-метод подразумевает последовательный перебор всех вершин области допустимых значений с целью нахождения той вершины, где функция принимает экстремальное значение. На первом этапе находится какое-нибудь решение, которое улучшается на каждом последующем шаге. Такое решение называется базисным. Приведем последовательность действий при решении задачи линейного программирования симплекс-методом:
Первый шаг. В составленной таблице перво-наперво необходимо просмотреть столбец со свободными членами. Если в нем имеются отрицательные элементы, то необходимо осуществить переход ко второму шагу, есле же нет, то к пятому.
Второй шаг. На втором шаге необходимо определиться, какую переменную изключить из базиса, а какую включить, для того, что бы произвести перерасчет симплекс-таблицы. Для этого просматриваем столбец со свободными членами и находим в нем отрицательный элемент. Строка с отрицательным элементом будет называться ведущей. В ней находим максимальный по модулю отрицательный элемент, соответсвующий ему столбец - ведомый. Если же среди свободных членов есть отрицательные значения, а в соответсвующей строке нет, то такая таблица не будет иметь решений. Переменая в ведущей строке, находящаяся в столбце свободных членов исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис.
Таблица 1.
базисные переменные | Свободные члены в ограничениях | Небазисные переменные | |||||
x 1 | x 2 | ... | x l | ... | x n | ||
x n+1 | b 1 | a 11 | a 12 | ... | a 1l | ... | a 1n |
x n+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
x n+r | b2 | a r1 | a r2 | ... | a rl | ... | a rn |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
x n+m | b m | a m1 | a m2 | ... | a ml | ... | a mn |
F(x) max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Третий шаг. На третьем шаге пересчитываем всю симплекс-таблицу по специальным формулам, эти формулы можно увидеть, воспользовавшись .
Четвертый шаг. Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то к пятому.
Пятый шаг. Если Вы дошли до пятого шага, значит нашли решение, которое допустимо. Однако, это не значит, что оно оптимально. Оптимальным оно будет только в том случае, если положительны все элементы в F-строке. Если же это не так, то необходимо улучшить решение, для чего находим для следующего перерасчета ведущие строку и столбец по следующему алгоритму. Первоначально, находим минимальное отрицательное число в строке F, исключая значение функции. Столбец с этим числом и будем ведущим. Для того, что бы найти ведущую строку, находим отношение соответсвующего свободного члена и элемента из ведущего столбца, при условии, что они положительны. Минимальное отношение позволит определить ведущую строку. Вновь пересчитываем таблицу по формулам, т.е. переходим к шагу 3.
Необходимо решить задачу линейного программирования.
Целевая функция:
2x 1 +5x 2 +3x 3 +8x 4 →min
Ограничивающие условия:
3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1
Приведем систему ограничений к каноническому виду, для этого необходимо перейти от неравенств к равенствам, с добавлением дополнительных переменных.
Так как наша задача - задача минимизации, то нам необходимо преобразовать ее к задаче на поиск максимума. Для этого изменим знаки коэффициентов целевой функции на противоположные. Элементы первого неравенства записываем без изменений, добавив в него дополнительную переменную x 5 и изменив знак "≤" на "=". Т. к. второе и третье неравенства имеют знаки "≥" необходимо поменять знаки их коэффициентов на противоположные и внести в них дополнительные переменные x 6 и x 7 соответственно. В результате получем эквивалентную задачу:
3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1
Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции с противоположным знаком.
Своб член |
|||||
F | |||||
X5 | |||||
X6 | |||||
X7 |
В составленой нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю - это элемент: -6, он задает ведущую строку - X6. В этой строке так же находим максимальный по модулю отрицательный элемент: -10 он находится в столбце X3 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис. Пересчитаем симплекс-таблицу:
X1 | X2 | X6 | X4 | Своб член | |
F | 0.8 | 8.9 | 0.3 | 6.5 | -1.8 |
X5 | 4.6 | 0.8 | -0.4 | 3 | 14.4 |
X3 | 0.4 | -1.3 | -0.1 | 0.5 | 0.6 |
X7 | -2.6 | -8.3 | -0.1 | 0.5 | -0.4 |
В составленой нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю - это элемент: -0.4, он задает ведущую строку - X7. В этой строке так же находим максимальный по модулю отрицательный элемент: -8.3 он находится в столбце X2 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис. Пересчитаем симплекс-таблицу:
X1 | X7 | X6 | X4 | Своб член | |
F | -1.988 | 1.072 | 0.193 | 7.036 | -2.229 |
X5 | 4.349 | 0.096 | -0.41 | 3.048 | 14.361 |
X3 | 0.807 | -0.157 | -0.084 | 0.422 | 0.663 |
X2 | 0.313 | -0.12 | 0.012 | -0.06 | 0.048 |
Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке F имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -1.988 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X2, а ведущий элемент: 0.313.
X2 | X7 | X6 | X4 | Своб член | |
F | 6.351 | 0.31 | 0.269 | 6.655 | -1.924 |
X5 | -13.895 | 1.763 | -0.577 | 3.882 | 13.694 |
X3 | -2.578 | 0.152 | -0.115 | 0.577 | 0.539 |
X1 | 3.195 | -0.383 | 0.038 | -0.192 | 0.153 |
Так как в строке F нет отрицательных элементов, то
найдено оптимальное решение. Так как исходной задачей был поиск минимума, то оптимальным решением будет свободный член строки F, взятый с противоположным знаком. F=1.924
при значениях переменных равных: x 3 =0.539, x 1 =0.153. Переменные x 2 и x 4 не входят в базис, поэтому x 2 =0 x 4 =0.
Один из методов решения оптимизационных задач (как правило связанных с нахождением минимума или максимума ) линейного программирования называется . Симплекс-метод включает в себя целую группу алгоритмов и способов решения задач линейного программирования. Один из таких способов, предусматривающий запись исходных данных и их пересчет в специальной таблице, носит наименование табличного симплекс-метода .
Рассмотрим алгоритм табличного симплекс-метода на примере решения производственной задачи , которая сводится к нахождению производственного плана обеспечивающего максимальную прибыль.
Исходные данные задачи на симплекс-метод
Предприятие выпускает 4 вида изделий, обрабатывая их на 3-х станках.
Нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:
Фонд времени работы станков (мин.) задан в матрице B:
Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:
Цель производственной задачи
Составить такой план производства, при котором прибыль предприятия будет максимальной.
Решение задачи табличным симплекс-методом
(1) Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4 )
(2) Запишем ограничения плана в виде системы уравнений:
(3) Тогда целевая прибыль:
То есть прибыль от выполнения производственного плана должна быть максимальной.
(4) Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7 ).
(5) Примем следующий опорный план :
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Занесем данные в симплекс-таблицу :
В последнюю строку заносим коэффициенты при целевой функции и само ее значение с обратным знаком;
(7) Выбираем в последней строке наибольшее (по модулю ) отрицательное число.
Вычислим b = Н / Элементы_выбранного_столбца
Среди вычисленных значений b выбираем наименьшее .
Пересечение выбранных столбца и строки даст нам разрешающий элемент. Меняем базис на переменную соответствующую разрешающему элементу (X5 на X1 ).
- Сам разрешающий элемент обращается в 1.
- Для элементов разрешающей строки – a ij (*) = a ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные ).
- Для элементов разрешающего столбца – они просто обнуляются.
- Остальные элементы таблицы пересчитываем по правилу прямоугольника.
a ij (*) = a ij – (A * B / РЭ)
Как видите, мы берем текущую пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A * B ) делим на разрешающий элемент (РЭ ). И вычитаем из текущей пересчитываемой ячейки (a ij ) то, что получилось. Получаем новое значение - a ij (*) .
(9) Вновь проверяем последнюю строку (c ) на наличие отрицательных чисел . Если их нет – оптимальный план найден, переходим к последнему этапу решения задачи. Если есть – план еще не оптимален, и симплекс-таблицу вновь нужно пересчитать.
Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию вычислений.
(10) Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C ). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную! ) прибыль при данном плане производства.
ОТВЕТ:
X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.
P = 48 * 32 + 33 * 20 = 2 196 руб.
Галяутдинов Р.Р.
© Копирование материала допустимо только при указании прямой гиперссылки на