Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Симплекс-метод, решение задачи с начальным базисом1) Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ≤ "). Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные: Эта система является системой с базисом (базис s1, s2, s3, каждая из них входит только в одно уравнение системы с коэффициентом 1), x1 и x2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами: Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод, т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты. симплекс-метод итерация 0
Для улучшения решения перейдем к следующей итерации симплекс-метода, получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец, т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации симплекс-метода это столбец x2 (коэффициент -6). Затем выбирается разрешающая строка, т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s3 (коэффициент 20). Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации симплекс-метода переменная x2 заменит в базисе s3. Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно. Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов). 1)Вычисление строки х2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s3 таблицы "Итерация 0" будет совпадать со строкой х2 таблицы "Итерация 1". Строку x2 таблицы "Итерации 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. В столбце x2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х2 выделены красным цветом. 3) Вычисление строки s1 таблицы "Итерация 1". На месте 1 в s1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х2 получен необходимый 0. 4) Вычисление строки s2 таблицы "Итерация 1". На месте 3 в s2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s2 - строкой таблицы "Итерация 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) Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем. симплекс-метод итерация 1
Разрешающий столбец х1, разрешающая строка s2, s2 выходит из базиса, х1 входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы. симплекс-метод итерация 2
Разрешающий столбец s3, разрешающая строка s1, s1 выходит из базиса, s3 входит в базис. симплекс-метод итерация 3
В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x1 = 24, x2 = 16, zmax = 192.
|