- 2. Различные виды записи задач линейного программирования. Переход от одного вида задачи линейного программирования к другому.
- Симплексный метод
- Алгоритм симплексного метода решения задач линейного программирования
- Общая, стандартная и основная задачи линейного программирования
- Геометрическая интерпретация задачи линейного программирования
- Линейное программирование
- 1.1. Примеры моделей, приводящих к задачам линейного программирования
- Задача о диете
2. Различные виды записи задач линейного программирования. Переход от одного вида задачи линейного программирования к другому.
Во многих областях практической деятельности человека возникают своеобразные задачи математического программирования, для которых характерны следующие особенности:
− целевая функция является линейной функцией переменных составляющих план задачи математического программирования;
− система ограничений (2.2) имеет вид системы линейных уравнений и/или неравенств.
Такие задачи называют задачами линейного программирования.
Существует несколько форм записи задач линейного программирования. Рассмотрим их.
1. Общая форма записи задачи линейного программирования: необходимо найти экстремальное значение целевой функции
на некоторые неизвестные могут быть наложены условия неотрицательности:
Здесь (и везде далее) заданные числа
2. Каноническая форма записи задачи линейного программирования: необходимо найти экстремальное значение целевой функции (4.1) при ограничениях
На все неизвестные наложены условия неотрицательности:
3. Симметричная форма записи задачи линейного программирования. Здесь принято выделять две стандартные задачи − задачу максимизации и задачу минимизации.
3.1. Стандартная задача максимизации: необходимо найти максимальное значение целевой функции (4.1) при ограничениях
и условиях неотрицательности (4.2).
3.2. Стандартная задача минимизации: необходимо найти минимальное значение целевой функции (4.1) при ограничениях
и условиях неотрицательности (4.2).
Симплексный метод
Данный метод является методом целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует.
Основное содержание симплексного метода заключается в следующем:
- Указать способ нахождения оптимального опорного решения
- Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции будет ближе к оптимальному, т.е. указать способ улучшения опорного решения
- Задать критерии, которые позволяют своевременно прекратить перебор опорных решений на оптимальном решении или следать заключение об отсутствии оптимального решения.
Алгоритм симплексного метода решения задач линейного программирования
Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:
- Привести задачу к каноническому виду
- Найти начальное опорное решение с «единичным базисом» (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
- Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
- Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
- Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения
Общая, стандартная и основная задачи линейного программирования
Определение 1. Общей задачей ЛП называется задача нахождения максимального (минимального) значения линейной целевой функции 
(1) при условиях 
, 
(2) 
, 
(3) 
, 
,
(4), где 
,
,
— заданные постоянные величины и
. Определение.2. Функция Z называется целевой функцией задачи (1 — 4), 
—проектными параметрами задачи, а условия (2 — 4) ограничениями данной задачи. Определение 3. Стандартной задачей ЛП называется задача нахождения целевой функции (1) при выполнении условий (2), (4), где k=m,l=n, т.е. когда ограничения заданы только в виде неравенств (2), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде равенств отсутствуют: 
, 
, 
. Определение 4. Канонической (или основной) задачей ЛП называется задача нахождения максимального (минимального) значения функции (1) при выполнении условий (3), (4), где k=0,l=n,mn, т.е. когда ограничения заданы только в виде равенств (3), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде неравенств (2) отсутствуют: 
, 
, 
,
. Определение 5. Совокупность значений проектных параметров 
, удовлетворяющих ограничениям задачи (2-4), называетсядопустимым решением, или планом. Определение 6. План 
, при котором целевая функция (1) принимает свое максимальное (минимальное) значение, называетсяоптимальным, т.е. 
. Все три формы задачи ЛП эквивалентны, ибо каждая из них с помощью некоторых преобразований может быть переписана в форме другой задачи. При этом необходимо пользоваться следующими правилами:
- Задачу минимизации функции можно свести к задаче максимизации, и, наоборот, путем замены знаков коэффициентов
на противоположные, поскольку. - Ограничения-неравенства (2) можно заменить эквивалентными ограничениями-равенствами путем введения дополнительных неотрицательных переменных следующим образом:
на противоположные, поскольку
. Ограничение-неравенство вида 
преобразуется в ограничение-равенство
,
, а ограничение-неравенство вида
— в ограничение-равенство
,
. При этом число дополнительных переменных равно числу преобразуемых неравенств. Вводимые дополнительные переменные имеют вполне определенный смысл. Так, например, для задачи распределения ресурсов числовое значение дополнительной переменной равно объему неиспользованного соответствующего ресурса. С математической точки зрения основные и дополнительные переменные играют одинаковую роль. Поэтому целесообразно их единообразное обозначение.
- Каждое ограничение-равенство вида (3) можно записать в виде двух неравенств .
- Переменная , неограниченная условием неотрицательности вида (4), можно заменить разностью двух дополнительных неотрицательных переменных:,,.
.
, неограниченная условием неотрицательности вида (4), можно заменить разностью двух дополнительных неотрицательных переменных:
,
,
.-
Геометрическая интерпретация задачи линейного программирования
Рассмотрим задачу, состоящую в определении максимального значения функции: 
(5) при условиях 
, 
(6) 
, 
(7). Эта задача ЛП в стандартной форме с двумя переменными. Каждое неравенство вида (6), (7) геометрически определяет полуплоскость соответственно с граничными прямыми 
(8). При этом вектор 
, как градиента функции
, указывает ту полуплоскость, которая определяется неравенством
, а вектор
— полуплоскость, определяемую неравенством
. Если система неравенств (6), (7) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Пересечение этих полуплоскостей образует выпуклый многоугольник решений, или область допустимых решений (ОДР). Таким образом, исходная задача ЛП состоит в нахождении таких точек многоугольника решений, в которых целевая функция Z принимает максимальное (минимальное) значение. Эта точка существует тогда, когда многоугольник решений не пуст, и на нем целевая функция ограничена. Линейная целевая функция достигает точек экстремума только на границе выпуклого многоугольника. Рассмотрим градиент функции цели 
. Это будет вектор
(см. рис.2.), указывающий направление возрастания функции цели. Очевидно, если взять обратное направление, то это будет направлением убывания функции цели. Если построить произвольную прямую
— const, то её движение параллельно самой себе в направлении вектора 
приведет к возрастанию функции цели. При этом для допустимости решения эта прямая должна иметь хотя бы одну общую точку с многоугольником решений. Два крайних положения этой прямой в ОДР соответствуют наименьшему и наибольшему значениям целевой функции. При этом могут встретиться случаи, изображенные на рис.2-5, когда исходная задача имеет единственное решение (минимальное и максимальное значение) (рис.2), множество решений (координаты любой точки прямой
на рис.3), и решение исходной задачи не существует в силу неограниченности целевой функции (рис.4) или несовместности системы неравенств (6), (7) (рис.5). 
Линейное программирование
1.1. Примеры моделей, приводящих к задачам линейного программирования
Линейное программирование является одной из основных частей того раздела современной математики, который получил название математического программирования. В общей постановке задачи этого раздела выглядят следующим образом.
Имеются какие-то переменные 
и функция этих переменных 
, которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции 
при условии, что переменные x принадлежат некоторой области G:
В зависимости от вида функции и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Подробнее об этом будет сказано в заключении.
Линейное программирование характеризуется тем, что
является линейной функцией переменных ;
б) область G определяется системой линейных равенств или неравенств.
Чтобы понять, откуда берутся задачи линейного программирования, рассмотрим некоторые, уже ставшие классическими, примеры подобных задач.
Задача о диете
Задача о диете возникает при составлении наиболее экономного (т.е. наиболее дешевого) рациона питания животных, удовлетворяющего определенным медицинским требованиям.
Предположим, что в нашем распоряжении имеется n продуктов питания (сено, зерно, комбикорм, соль и т.д.). Обозначим эти продукты через
. Предположим, что 
есть стоимость единицы веса (например,
стоимость одного килограмма) продукта .
Рациональная диета должна доставлять животному определенные компоненты (белки, жиры, углеводы, витамины, микроэлементы и т.д.). Обозначим эти компоненты через . Тогда можно составить таблицу — справочник, указывающую, какое количество каждого компонента имеется в единице веса каждого продукта.