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

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

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

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

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

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

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

  1. Метод искусственного базиса
    Решить методом искусственного базиса.
  2. Задача о кормовой смеси. Пример решения
  3. Задача оптимального производства продукции
  4. Пример решения задачи симплексным методом в Excel
  5. Пример решения симлекс-методом
    Решить следующую задачу ЛП в неканонической форме симплекс-методом:
    f(x) = x1 – x2 – 3x3 → min
  6. М-метод
    Решить задачу М-методом.
  7. Симплекс-метод. Поиск наибольшего значения
  8. Пример нахождения максимума функции симплексным методом
  9. Пример нахождения минимума функции симплексным методом
  10. Решение прямой задачи линейного программирования симплексным методом
  11. Решение задачи симплексным методом путем преобразования симплекс–таблиц
  12. Подробное решение задачи симплекс-методом
  13. Математическая модель задачи
    Предприятие выпускает 3 вида микросхем: M1, M2, M3. Для производства используются одни и те же ресурсы: кремний (S), алюминий (Al), золото (Au), пластик (P), которые берутся в разных количествах. Расход ресурсов на единицу продукции каждого вида приведен в таблице 1. Максимальные суточные запасы ресурсов приведены в таблице 2. Изучение рынка сбыта показало, что разница суточного спроса между отдельно взятыми видами микросхем (Продукт1 – Продукт2) никогда не превышает величин, приведенных в таблице 3. Цены за микросхему каждого вида приведены в таблице 4.
  14. Линейное программирование в Excel
  15. Примеры задач линейного программирования
  16. Пример решения модифицированным симплекс-методом
    Решить задачу модифицированным симплексным методом.
  17. Задача линейного программирования модифицированным симплексным методом
  18. Решение задач линейного программирования модифицированным симплексным методом
  19. Пример решения симплекс-методом в столбцовой форме записи
  20. Симплекс-метод в строчечной форме записи. Пример решения
  21. Двухэтапный симплекс-метод
  22. Двухфазный симплекс-метод
  23. Сборник решений по симплекс-методу

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

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

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

  1. Пример решения методом Гомори
  2. Метод Гомори. Пример решения
  3. Сборник решений по методу Гомори
  4. Метод отсечений Гомори. Пример решения
  5. Пример решения методом ветвей и границ.
  6. Пример постановки задачи целочисленного программирования для решения методом ветвей и границ.

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

  1. Двойственный симплекс-метод. Подробный пример решения
  2. Алгоритм двойственного симплекс-метода
  3. Пример решения Р-методом
  4. Сборник решений Р-методом

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

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

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

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

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

загрузка...