- •Введение
- •Экономико-математическая модель
- •Примеры задач линейного программирования
- •Задача об использовании ресурсов (задача планирования производства).
- •Задача о составлении рациона (задача о диете, задача о смесях).
- •Задача об использовании мощностей (задача о загрузке оборудования).
- •6) Транспортная задача.
- •Общая задача линейного программирования
- •Задача с двумя неизвестными.
- •Геометрическая интерпретация и графическое решение задачи линейного программирования
- •II. Задача с n переменными.
- •Свойства решений задачи линейного программирования
- •Симплекс – метод (метод перебора крайних точек)
- •Симплекс – алгоритм
- •Особые случаи симплекс – метода
- •Отсутствие конечного оптимума.
- •Симплекс – таблицы
- •Метод искусственного базиса
- •Двойственные задачи
- •Основные теоремы двойственности и их экономическое содержание
- •Применение оценок в послеоптимизационном анализе
- •Транспортная задача
- •Усложнённые постановки задач транспортного вида
- •Метод разрешающих коэффициентов
- •Транспортная задача по критерию времени
- •Венгерский метод.
- •Задачи целочисленного линейного программирования
- •Заключение
- •Библиографический список
II. Задача с n переменными.
Графическим методом можно решать ЗЛП с n>2 переменными, если в её канонической записи число неизвестных “n” и число линейно независимых уравнений “m” связаны соотношением n-m≤2. В этом случае каноническую форму задачи преобразовывают в симметричную, которая будет содержать не более двух переменных. Решая эту задачу графически, находят два компонента оптимального плана. Подставляя их в ограничения задачи, определяют и остальные компоненты.
Пример:
Найти
при ограничениях
Решение:
Т.к.
,
,
,
то
Тогда
Мы свели задачу к задаче с двумя переменными, которую мы уже умеем решать.
Свойства решений задачи линейного программирования
Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым (если оно не пусто).
Целевая функция задачи линейного программирования достигает своего минимального (максимального) значения в угловой точке многогранника решений. Если целевая функция принимает минимальное (максимальное) значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.
Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение.
Итак, если линейная функция задачи линейного программирования ограничена на многограннике решений, то: 1) существует такая угловая точка многогранника решений, в которой линейная функция задачи линейного программирования достигает своего оптимума; 2) каждый опорный план соответствует угловой точке многогранника. Поэтому для решения задачи линейного программирования необходимо исследовать только угловые точки многогранника решений, т.е. только опорные планы.
Симплекс – метод (метод перебора крайних точек)
Симплекс-метод (метод последовательного улучшения плана) – классический метод в линейном программировании. Он позволяет найти крайнюю точку области и определить является ли она точкой экстремума целевой функции Z. Если нет, то обеспечивается переход в соседнюю крайнюю точку, где значения функции Z больше (меньше) предыдущего. Тем самым делается шаг, приближающий получение решения.
Симплекс-метод в его непосредственной форме предназначен для решения канонической задачи линейного программирования.
Определение.
Любые
- переменных системы
- линейных уравнений с
- переменными, где
называют основными или базисными, если
определитель матрицы коэффициентов
при них отличен от нуля. Тогда остальные
переменных называются небазисными или
свободными.
Общее число групп основных переменных не превосходит число сочетаний
Критерий оптимальности. Целевая функция на min(max) оптимальна, если в выражении целевой функции через свободные переменные отсутствуют отрицательные (положительные) коэффициенты при свободных переменных.
Определение. Базисным решением системы линейных уравнений с переменными называется решение, в котором все свободных переменных равны 0.
Определение. Допустимое базисное решение – это базисное решение, в котором все переменные больше либо равны нулю. Допустимые базисные решения называют опорными планами.
Определение. Система уравнений называется совместной, если она имеет хотя бы одно решение и несовместной, если она не имеет решений.
Определение. Совместная система уравнений называется определенной, если она имеет единственное решение, и неопределенной, если она имеет более одного решения.
Теорема Кронекера – Капелли. Система линейных уравнений совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы этой системы.
Теорема 1. Если
ранг матрицы совместной системы равен
числу переменных, т. е.
,
то система имеет единственное решение.
Теорема 2. Если
,
то система неопределенная и имеет
бесконечное множество решений.
