Лекция 5: симплекс-таблицы для решения задач линейного программирования. Метод искусственного базиса.
1.Решение задач симплекс-методом в виде таблиц. 2. Метод искусственного базиса. Описанный в предыдущей Лекции 4 процесс решения ЗЛП симплекс-методом довольно трудоемкий и требует выполнения однообразных преобразований. Причем с возрастанием числа неизвестных растет и число шагов. Оказывается, эти преобразования можно записать в виде последовательности однотипно заполненных таблиц, называемых симплекс-таблицами. Изложим способ составления и преобразования таких таблиц на примерах первой и второй основных задач из Лекции 4. I. Первая основная задача. Для заполнения первой симплекс-таблицы необходимо переписать целевую функцию F и систему ограничений (4.4) в виде: Заполним таблицу
В выражении для F выясняем, имеются ли в последней строке таблицы, кроме столбца «свободные члены», отрицательные числа. Если таковых нет, то задача решена. Если же есть, то выполняем преобразование: в столбце имеем (из двух отрицательных чисел –25 и –34 выбирают меньшее по модулю), над этим элементом ищем положительные числа. Если таковых нет, то задача не имеет решения. В нашем случае над –25 есть три положительных числа: 1; 1 и 1. Найдем Элемент, стоящий на пересечении строки () и столбца (), называем разрешающим. В нашем случае он равен 1. (Если разрешающий элемент равен числу , то всю строку делят на разрешающий элемент m, чтобы получить 1). Неизвестная вводится в базис, а неизвестная выводится из него. Заполняем вторую симплекс-таблицу. Строка () из первой таблицы становится в ней строкой (). Далее преобразуем строки (), () и (F) первой таблицы так, чтобы их элементы, стоящие в столбце (), обратились в 0. С этой целью
1) вычтем элементы строки () из соответствующих элементов строки (), и запишем полученные результаты в строку () второй таблицы; 2) вычтем элементы строки () из соответствующих элементов строки (), и запишем полученные результаты в строку () второй таблицы; 3) умножим элементы строки () на 25, сложим с соответствующими элементами строки (F), и запишем полученные результаты в строку (F) второй таблицы. В результате получим следующую симплекс-таблицу
В строке (F) есть отрицательное число –9. Поэтому продолжим поиск оптимального решения. Над –9 есть три положительных числа: 1; 1 и 3. Найдем Элемент, стоящий на пересечении строки () и столбца () разрешающий и равен 1. Неизвестная вводится в базис, а неизвестная выводится из него. Заполняем третью симплекс-таблицу. Строка () из второй таблицы становится в ней строкой (). Далее преобразуем строки (), () и (F) второй таблицы так, чтобы их элементы, стоящие в столбце (), обратились в 0. С этой целью 1) вычтем элементы строки () из соответствующих элементов строки (), и запишем полученные результаты в строку () третьей таблицы; 2) умножим элементы строки () на 3, вычтем из соответствующих элементов строки (), и запишем полученные результаты в строку () третьей таблицы; 3) умножим элементы строки () на 9, сложим с соответствующими элементами строки (F), и запишем полученные результаты в строку (F) третьей таблицы. В результате получим следующую симплекс-таблицу
В строке (F) нет отрицательных чисел. Получили оптимальное решение: при , , , . Замечание. Симплекс-таблицы удобнее «пристыковывать» друг к другу по вертикали, что позволяет не писать многократно заглавную строку II. Вторая основная задача. Для заполнения первой симплекс-таблицы перепишем целевую функцию F и систему ограничений (4.14), имеющую допустимый вид, следующим образом: Заполним таблицу
В выражении для F выясняем, имеются ли в последней строке таблицы, кроме столбца «свободные члены», положительные числа. Если таковых нет, то задача решена. Если же есть, то выполняем преобразование: в столбце имеем . Над этим элементом ищем положительные числа. Если таковых нет, то задача не имеет решения. В нашем случае над 40 есть три положительных числа: 3; 8 и 23. Найдем Элемент, стоящий на пересечении строки () и столбца () разрешающий и равен 8. Неизвестная вводится в базис, а неизвестная выводится из него. Все элементы строки () разделим на разрешающий элемент. Полученные результаты запишем в новую симплекс-таблицу в строке (). Преобразуем строки (), () и (F) первой таблицы так, чтобы их элементы, стоящие в столбце (), обратились в 0. С этой целью 1) умножим элементы строки () на 3, вычтем из соответствующих элементов строки (), и запишем полученные результаты в строку () второй таблицы; 2) умножим элементы строки () на 23, вычтем из соответствующих элементов строки (), и запишем полученные результаты в строку () второй таблицы; 3) умножим элементы строки () на 40, вычтем из соответствующих элементов строки (F), и запишем полученные результаты в строку (F) второй таблицы. В строке (F) нет положительных чисел. Получили оптимальное решение: при , , , . Замечание. Первая симплекс-таблица второй основной задачи была заполнена с учетом того, что система ограничений (4.11) была предварительно сведена к допустимому виду (4.14), т.е. был найден допустимый базис. Зачастую поиск такого базиса довольно затруднителен. Рассмотрим следующий метод нахождения допустимого базиса, который называют методом искусственного базиса или М-методом.
Воспользуйтесь поиском по сайту: ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|