Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
В рассмотренном нами примере (п. 1.7.) с самого начала каноническая задача линейного программирования имела симплексную форму. Рассмотрим теперь на примере, как для произвольной задачи ЛП получить первую симплекс-таблицу.
Пример №1. Найти решение задачи:
(1)
I-ый способ решения.
Запишем задачу (1) в виде таблицы, подобной симплексной.
- 6 | - 1 | - 2 | - 28 | |||
(2) | ||||||
Первые две строки фактически содержат матрицу ограничений, а последняя, индексная, строка определение функции . Конечно, таблица (2) не является симплексной. Во-первых, столбец свободных членов содержит отрицательный элемент (–28) в первой строке. Чтобы этого не было, умножим первую строку на (–1):
- 1 | ||||||
(3) | ||||||
Во-вторых, система ограничений не имеет разрешенного вида, то есть матрица ограничений в (3) не содержит единичной матрицы размера
Приведем систему в таблице (3) методом Гаусса к разрешенному виду, не нарушая при этом условие неотрицательности столбца свободных членов . Выберем, например, в качестве ведущего столбца столбец . Ведущую строку определим с помощью минимального допустимого отношения . Как обычно рамкой выделим ключевой элемент стоящий на пересечении ведущих строки и столбца.
- 1 | |||||||
24 | (4) | ||||||
Методом Гаусса преобразуем ведущий столбец в базисный. Для этого:
1. из первой строки вычтем ведущую (вторую)
2. из индексной строки (третьей) вычтем ведущую вторую).
Получим новую таблицу:
- 3 | ||||||
(5) | ||||||
- 1 |
Теперь выберем ведущим столбец и найдем ведущую строку с минимальным допустимым отношением:
- 3 | 4 | (6) | |||||
- 1 |
Преобразуем ведущий столбец в базисный. Для этого вычтем из второй и третьей строки ведущую (первую) строку. В результате получим таблицу:
- 3 | (7) | |||||
- 3 |
которая является симплексной. Действительно, матрица системы содержит единичную (если переставить столбцы () и ()), подматрицу размера ; столбец неотрицателен; функция F зависит только от свободных переменных и , что видно из того, что в индексной строке в столбцах базисных переменных и стоят нули.
Далее можно решить задачу описанным выше симплекс-методом. Это решение мы запишем в виде единой таблицы, состоящей из последовательно полученных симплекс-таблиц:
- 3 | 2 | ||||||
- 3 | |||||||
(8) | |||||||
- 3 | |||||||
- | |||||||
- 1 | 2 | ||||||
Последовательность операций.
1. Выбираем ведущим второй столбец по элементу (–3) в индексной строке.
2. Находим минимальное отношение .
3. Выбираем ведущей первую строку.
4. Делим ведущую строку на ключевой элемент 2 (в рамочке), стоящий в ведущей строке
5. Вычитаем из второй строки ведущую, умноженную на 2.
6. Прибавляем к индексной строке ведущую, умноженную на 3.
7. Выбираем ведущим первый столбец по элементу в индексной строке.
8. Определяем ведущую строку с минимальным допустимым отношением .
9. Делим ведущую строку на ключевой элемент 8.
10. Прибавляем к первой строке ведущую, умноженную на .
11. Прибавляем к индексной строке ведущую, умноженную на .
В результате всех операций 1-11 мы из первой симплекс-таблицы (7) получаем последнюю симплекс-таблицу:
(9) | ||||||
и из первого опорного решения
, (10)
получаем последнее опорное решение:
, (11)
которое оказывается оптимальным, поскольку в индексной строке таблицы (9) нет отрицательных элементов.
Пример № 1 решен.
Ответ:
Изложенный выше метод получения первого опорного решения основан на методе Гаусса и теореме о минимальном допустимом отношении.
Дата публикования: 2014-11-02; Прочитано: 259 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!