Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Упростить выражение
Примеры решений Метод Гомори Графический метод Теория игр
Симплекс-метод M-задача Теоремы двойственности
Одноканальные СМО Задача коммивояжера Транспортная задача

Линейное программирование. Решение задач

Классификацию решения задач линейного программирования можно представить в виде следующей схемы.
Метод решенияПримечаниеЦелевая функция
1. Графический методИспользуется при двух переменных (x1, x2)max, min
2. Симплексный методФормы записи: симплексная таблица, строчечная форма, строковая форма. Алгоритм решения: метод искусственного базиса (М-метод, двухфазный метод), правило прямоугольника, правило Крекоmax, min
3. Двойственный симплекс-методФормы записи: симплексная таблица, строчечная форма, строковая форма. Алгоритм решения: метод искусственного базиса (М-метод, двухфазный метод)min
4. Двойственная задачаАлгоритм решения: симплекс-метод, теоремы двойственностиmax, min
5. Метод ГомориАлгоритм решения: метод отсеченийmax, min

Прежде чем решать ЗЛП, необходимо ознакомится с материалом Как привести задачу линейного программирования к канонической форме и Как привести каноническую задачу линейного программирования к стандартной форме.

Ниже представлены примеры решения задач линейного программирования.

Линейное программирование. Решение задач графическим способом

  1. Как решать графическим способом. Применение графического способа при трех и более переменных
  2. Графический анализ чувствительности
  3. Анализ эффективности оптимального решения задачи графическим методом

Симплексный метод решения задач линейного программирования

  1. Метод искусственного базиса
  2. Задача оптимального производства продукции
  3. Пример решения симлекс-методом
    Решить следующую задачу ЛП в неканонической форме симплекс-методом:
    f(x) = x1 – x2 – 3x3 → min
  4. М-метод. Решить задачу М-задачу.
  5. Пример нахождения максимума функции симплексным методом
  6. Пример нахождения минимума функции симплексным методом
  7. Пример решения модифицированным симплекс-методом
  8. Пример решения симплекс-методом в столбцовой форме записи
  9. Симплекс-метод в строчечной форме записи. Пример решения
  10. Пример решения задачи симплексным методом в Excel
  11. Линейное программирование в Excel

Решение двойственной задачи линейного программирования

  1. Двойственная задача ЛП
    Необходимо выполнить в указанном порядке следующие задания.
    1. Найти оптимальный план прямой задачи:
    а) графическим методом;
    б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
    2. Построить двойственную задачу.
    3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
  2. Двойственная задача в Excel
  3. Оценка целесообразности выпуска новой продукции

Двойственный симплекс-метод

  1. Алгоритм двойственного симплекс-метода. Подробный пример решения Р-методом
Методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь дело в экономике. Решение таких задач сводится к нахождению крайних значений (максимума и минимума) некоторых функций переменных величин.

Линейное программирование основано на решении системы линейных уравнений (с преобразованием в уравнения и неравенства), когда зависимость между изучаемыми явлениями строго функциональна. Для него характерны математическое выражение переменных величин, определенный порядок, последовательность расчетов (алгоритм), логический анализ. Применять его можно только в тех случаях, когда изучаемые переменные величины и факторы имеют математическую определенность и количественную ограниченность, когда в результате известной последовательности расчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическая логика, совмещаются с логически обоснованным пониманием сущности изучаемого явления.

Методом линейного программирования решается транспортная задача, т.е. задача рационального прикрепления предприятий-потребителей к предприятиям-производителям.

см. также Решение задач по ЭММ