5. Задача лп, стандартная форма, каноническая форма.
К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.
Задачей линейного программирования является выбор из множества допустимых планов наиболее выгодного (оптимального).
Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.
В общем виде модель записывается следующим образом:
Целевая функция: F (x)= c1x1 + c2x2 + ... + cnxn → max(min)
ограничения: a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1,
a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2,
...
am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm;
требование неотрицательности: xj ≥ 0,
Задача имеет каноническую форму, если является задачей на максимум (минимум) линейной функции F и ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х1, х2, ..., хn являются неотрицательными:
F (x) =
, i= 1,2…m
, j = 1,2…n
В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной функции f и система ограничений ее состоит из одних линейных неравенств типа « <= ». Все переменные задачи неотрицательны.
F (x) =
, i= 1,2…m
, j = 1,2…n
Свойства задачи ЛП.
Допустимое множество решений задачи ЛП либо пусто, либо является выпуклым многогранником (как пересечение полупространств, описываемых ограничениями-неравенствами). Оно может быть как ограниченным, так и неограниченным; в любом случае это замкнутый многогранник.
Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации - ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение.
Оптимальные решения задачи ЛП (если они существуют) всегда находятся на границе допустимого множества. Точнее, если существует единственное оптимальное решение, то им является какая-либо вершина многогранника допустимых решений; если две или несколько вершин являются оптимальными решениями, то любая их выпуклая комбинация также является оптимальным решением (т.е. существует бесконечно много точек максимума или минимума)
- 1. Определение задачи математического программирования
- 2. Допустимое решение задачи, одр, оптимальное решение задачи.
- 3. Экономико–математические модели задач лп: задача о банке
- Задача о банке
- 4. Экономико – математические модели задач лп: задача определения оптимального ассортимента продукции.
- 5. Задача лп, стандартная форма, каноническая форма.
- 6. Целевая функция, градиент
- 7. Двойственная задача и ее свойства
- 8. Первая теорема двойственности и ее следствия
- 94. Экономическая интерпретация двойственной задачи.
- 10. Транспортная задача, математическая модель и ее свойства.
- 11. Метод минимального элемента, метод северо-западного угла.
- 12. Метод потенциала, цикл
- 13.Открытые модели транс-ой задачи.Принцип замыкания
- 14. Матричные игры с нулевой суммой.
- 15. Смешанные стратегии, чистые стратегии.
- 16. Оптим-ое решение игры в смешанных стратегиях, седловая точка
- 21. Кооперативная игра, коалиции и дележи.
- 24 Альтернатива (альтернативная стратегия)
- 28. Риск, источники риска.
- 26. Динамическое программирование.
- 27. Метод дп включает три основных этапа:
- 29. Полнота и арбитраж.
- 30. Модель (b,s) – рынка. Пример дискретной и непрерывной модели.
- 31. Хеджирование как метод защиты от риска.
- 32. Модель Марковица.
- 33. Общие сведения о сетях
- 34 Сетевое планирование и управление
- 35. Временные параметры сетевых моделей
- 36.Сетевые графики и их анализ
- 37. Однофакторное и многофакторное уравнения регрессии
- 38. Типы связи между случайными величинами.
- 39. Коэффициент корреляции, детерминации.
- Вопрос 16. Метод северо-западного угла
- Вопрос 17. Метод потенциалов