- •Линейное программирование
- •Часть I Содержание:
- •1. Основные понятия
- •1.1. Примеры моделей, приводящих к задачам линейного программирования
- •Задача о диете
- •1.2. Стандартная и каноническая формы задачи линейного программирования
- •Первая стандартная форма задачи линейного программирования имеет вид
- •Канонической формой задачи линейного программирования называется задача вида
- •5. Ограничения на неотрицательность переменных.
- •1.3. Геометрическая интерпретация задач линейного программирования
- •Решение
- •Решение
- •Решение
- •2. Симплекс-метод
- •2.1. Выпуклые множества и многогранники
- •Доказательство
- •Доказательство.
- •Доказательство
- •2.2. Вершины выпуклого многогранника
- •Определение. Вершиной или крайней точкой выпуклого многогранника называется любая его точка, которая не является внутренней точкой никакого отрезка, целиком принадлежащего этому многограннику.
- •Доказательство
- •Доказательство
- •Доказательство
- •Доказательство
- •2.3. Переход от вершины к вершине
- •2.4. Переход к новому базису
- •2.5. Отыскание оптимального плана
- •Доказательство:
- •Доказательство:
- •2.6. Алгоритм симплекс-метода
- •Этап 1 Просматривается дополнительная строка снизу, где записаны разности .
- •Первая итерация
- •И он достигается на векторе , то этот вектор подлежит выводу из базиса и соответствующая ему строка и будет направляющей строкой.
- •Вторая итерация
- •2.7. Метод искусственного базиса
- •Вариант 1
- •Вариант 2
- •Первая итерация Так как из базиса выводится вектор , то в получающейся симплекс-таблице соответствующий столбец сразу удаляется.
- •Вторая итерация
- •Третья итерация Мы вернулись к исходной задаче и продолжаем решать ее по стандартной схеме.
- •3. Двойственные задачи
- •3.1. Постановка двойственных задач Симметричные двойственные задачи
- •Несимметричная двойственная задача
- •Переменные называется по-разному. Часто их называют учетными, неявными или фиктивными ценами.
- •3.2. Свойства двойственных задач
- •Доказательство.
- •1. Симметричная пара
- •2. Несимметричная пара Доказательство в этом случае почти дословно повторяет предыдущее.
- •Теорема 3. ( в формулировке для несимметричной двойственной задачи)
- •Доказательство.
- •Теорема 3. (в формулировке для симметричной двойственной задачи).
- •3.3. Двойственный симплекс-метод
- •4. Транспортная задача
- •4.1. Постановка задачи
- •Приведение открытой транспортной задачи к сбалансированной
- •4.2. Простейшие свойства транспортной задачи
- •Доказательство
- •Доказательство
- •Доказательство
- •4.3. Методы определения первоначального опорного плана
- •4.3.1. Построение исходного опорного плана (метод северо-западного угла)
- •Пример 1
- •Пример 2
- •4.3.2. Метод минимального (максимального) элемента
- •Пример № 2
- •Решение:
- •4.3.3. Метод аппроксимации Фогеля
- •Решение:
- •4.3.4. Метод двойного предпочтения
- •4.4. Методы проверки опорного плана на оптимальность
- •4.4.1. Потенциалы. Критерий оптимальности плана
- •4.4.2. Дельта-метод
- •4.5. Алгоритм улучшения плана
- •Вторая итерация Этап 1
- •Третья итерация Этап 1
- •Теорема Если все запасы и все потребности целые числа, то оптимальный план перевозок тоже целочисленный. Доказательство
- •4.6. Снятие вырожденности
- •4.6.1. Эпсилон-прием
- •Построение исходного опорного плана.
- •Первая итерация
- •Вторая итерация Этап 1
- •Третья итерация Этап 1
3. Двойственные задачи
3.1. Постановка двойственных задач Симметричные двойственные задачи
Рассмотрим задачу линейного программирования в стандартной форме
|
(1) |
,
или, в матричной форме,
|
(2) |
Рассмотрим теперь следующую задачу
|
(3) |
,
или, в матричной форме,
|
(4) |
Пара задач (1) и (3) (или, в матричной форме, пара задач (2) и (4) ) называются двойственными друг другу задачами в симметричной форме.
Несимметричная двойственная задача
Исходная задача имеет вид:
|
(5) |
,
или, в матричной форме,
|
(6) |
Двойственная задача в несимметричной форме имеет вид
|
(7) |
или, в матричной форме,
|
(8) |
Обратите внимание на то, что в несимметричной двойственной задаче не накладывается условие неотрицательности переменных.
Если исходная задача линейного программирования записана в произвольной форме, то для записи двойственной задачи следует сначала записать исходную задачу в канонической или стандартной форме, а затем выписать двойственную задачу. При желании, получившуюся двойственную задачу также можно привести к какой-либо нестандартной форме.
Экономическая интерпретация двойственной задачи в симметричной форме
Исходная задача:
Обычно эта задача связывается с задачей максимизации дохода при производстве некоторой продукции при наличии ограничений на ресурсы. Коэффициенты имеют смысл дохода от единицы продукции j-го ресурса, — количество единиц продукции j-го вида. Коэффициенты имеют смысл затрат i-го ресурса на производство продукции j-го типа. Что же представляет двойственная задача по своему смыслу?
Целевая функция двойственной задачи: ,
а ограничения: , где (1) — затраты i-го ресурса на производство единицы продукции j-го типа, а (2) — доход от продажи единицы продукта i-го типа. Поэтому в целевой функции на месте (?)получаем смысл стоимости всех ресурсов, т. е. Задача приобретает смысл: , при ограничениях: , где
(3) — запасы i-го ресурса;
(4) — стоимость единицы i-го ресурса;
(5) — общая стоимость всех ресурсов;
(6) — запасы i-го ресурса на производство единицы продукции j-го типа;
(7) — цена единицы i-го ресурса;
(8) — доход от продажи единицы продукции i-го вида.
Таким образом, задачи симметричной двойственной пары могут быть сформулированы так.
Исходная задача. Сколько единиц продукции каждого вида надо выпустить при доходе от продукции единицы j-го типа при имеющихся запасах каждого из ресурсов , чтобы получить максимальный доход?
Двойственная задача. Какую цену следует назначить единице каждого из ресурсов , чтобы при заданных величинах дохода от производства единицы каждого вида продукции минимизировать стоимость затрат?