Линейное программирование. Решение задач
Классификацию решения задач линейного программирования можно представить в виде следующей схемы.| Метод решения | Примечание | Целевая функция |
| 1. Графический метод | Используется при двух переменных (x1, x2) | max, min |
| 2. Симплексный метод | Формы записи: симплексная таблица, строчечная форма, строковая форма. Алгоритм решения: метод искусственного базиса (М-метод, двухфазный метод), правило прямоугольника, правило Креко | max, min |
| 3. Двойственный симплекс-метод | Формы записи: симплексная таблица, строчечная форма, строковая форма. Алгоритм решения: метод искусственного базиса (М-метод, двухфазный метод) | min |
| 4. Двойственная задача | Алгоритм решения: симплекс-метод, теоремы двойственности | max, min |
| 5. Метод Гомори | Алгоритм решения: метод отсечений | max, min |
Прежде чем решать ЗЛП, необходимо ознакомится с материалом Как привести задачу линейного программирования к канонической форме и Как привести каноническую задачу линейного программирования к стандартной форме.
Ниже представлены примеры решения задач линейного программирования.
Линейное программирование. Решение задач графическим способом
- Как решать графическим способом. Применение графического способа при трех и более переменных
- Графический анализ чувствительности
- Анализ эффективности оптимального решения задачи графическим методом
Симплексный метод решения задач линейного программирования
- Метод искусственного базиса
- Задача оптимального производства продукции
- Пример решения симлекс-методом
Решить следующую задачу ЛП в неканонической форме симплекс-методом:
f(x) = x1 – x2 – 3x3 → min - М-метод. Решить задачу М-задачу.
- Пример нахождения максимума функции симплексным методом
- Пример нахождения минимума функции симплексным методом
- Пример решения модифицированным симплекс-методом
- Пример решения симплекс-методом в столбцовой форме записи
- Симплекс-метод в строчечной форме записи. Пример решения
- Пример решения задачи симплексным методом в Excel
- Линейное программирование в Excel
Решение двойственной задачи линейного программирования
- Двойственная задача ЛП
Необходимо выполнить в указанном порядке следующие задания.
1. Найти оптимальный план прямой задачи:
а) графическим методом;
б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
2. Построить двойственную задачу.
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости. - Двойственная задача в Excel
- Оценка целесообразности выпуска новой продукции
Двойственный симплекс-метод
- Алгоритм двойственного симплекс-метода. Подробный пример решения Р-методом
Линейное программирование основано на решении системы линейных уравнений (с преобразованием в уравнения и неравенства), когда зависимость между изучаемыми явлениями строго функциональна. Для него характерны математическое выражение переменных величин, определенный порядок, последовательность расчетов (алгоритм), логический анализ. Применять его можно только в тех случаях, когда изучаемые переменные величины и факторы имеют математическую определенность и количественную ограниченность, когда в результате известной последовательности расчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическая логика, совмещаются с логически обоснованным пониманием сущности изучаемого явления.
Методом линейного программирования решается транспортная задача, т.е. задача рационального прикрепления предприятий-потребителей к предприятиям-производителям.
см. также Решение задач по ЭММ