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