Числовые последовательности Признак монотонности функции Функции нескольких переменных Система линейных алгебраических уравнений Экономический анализ транспортных задач

Математический анализ, математическая статистика

Понятие множества является первоначальным понятием математики, точное определение ему не дается, но его можно пояснить, описать через другие понятия. Можно сказать, что множество – это совокупность, собрание каких-то объектов, предметов, при этом объект, входящий в это множество, называют его элементом. Множества могут содержать как конечное число элементов, так и бесконечно много элементов. Рассматривают и множество, не содержащее элементов, его называют пустым и обозначают символом

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

Произвольную задачу линейного программирования можно определенным образом сопоставить с другой задачей линейного программирования, называемой двойственной. Первоначальная задача является исходной. Эти две задачи тесно связаны между собой и образуют единую двойственную пару.

Различают симметричные, несимметричные и смешанные двойственные задачи. Соленоидальное векторное поле Векторное поле называется соленоидальным, если существует такое векторное поле , для которого поле является полем его роторов: .

22.1. Виды двойственных задач и составление их математических моделей

Симметричные двойственные задачи

Дана исходная задача

при ограничениях:

Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, для этого:

каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную yi;

составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничений исходной задачи;

составляем систему ограничений. Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи. Знаки неравенств меняются на противоположные;

свободными членами системы ограничений являются коэффициенты целевой функции исходной задачи. Все переменные двойственной задачи неотрицательные.

Математическая модель двойственной задачи имеет вид

при ограничениях:

Несимметричные двойственные задачи

Дана исходная задача

при ограничениях:

Задача дана в каноническом виде. Составим математическую модель двойственной задачи.

Для ее составления пользуются тем же правилом, что и для составления симметричной задачи, с учетом следующих особенностей:

ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства ≥, если максимум, то ≤;

переменные yi — произвольные по знаку.

Математическая модель двойственной задачи имеет вид

при ограничениях:

Смешанные двойственные задачи

Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.

Основные теоремы двойственности

ТЕОРЕМА 1. Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений и выполняется равенство

Если одна из двойственных задач неразрешима ввиду того, что L()max →  (или S()min → -), тo другая задача не имеет допустимых решений.

ТЕОРЕМА 2. Для оптимальности допустимых решений  и  пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений

Теоремы позволяют определить оптимальное решение одной из пары задач по решению другой.

 


Решение двойственных задач

Решение симметричных задач

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

Решим исходную задачу графическим методом, получим опт = (4, 1), при этом L()mах = 3.

На основании 1-й теоремы двойственности

Так как x1, х2 > 0, то по 2-й теореме двойственности систему ограничений двойственной задачи можно записать в виде равенств:

Подставим опт в систему ограничений исходной задачи:

Тогда система ограничений двойственной задачи примет вид

Откуда опт = (0, 2/3, 1/3), при этом S()min = 3.

Пусть дано решение двойственной задачи опт = (0, 2/3, 1/3), S()min = 3, найдем решение исходной.

По 1-й теореме двойственности L()max = S()min = 3. Так как у2, y3 > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:

Откуда опт = (4,1), при этом L()mах = 3.

Рассмотрим решение задач методом, основанным на взаимно однозначном соответствии между переменными: основным переменным исходной задачи соответствуют балансовые переменные двойственной, и наоборот. Для этого решим двойственную задачу симплексным методом:

при ограничениях:

Из табл. 22.1 следует, что опт = (0, 2/3, 1/3), S()min = 3.

На основании 1-й теоремы двойственности получаем

Решение другой задачи найдем по соответствию между переменными:

Значение xj определяем по последней симплексной таблице в строке Δi в соответствующем столбце, причем значения xj берем по модулю:

Таким образом, решение исходной задачи:

Если исходная задача решена симплексным методом, то решение двойственной задачи может быть найдено по формуле

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

Решим симплексным методом исходную задачу вида

при ограничениях:

Из табл. 22.2 следует, что опт = (4,1), L()max = 3. Матрицы записываются в виде

тогда

Таким образом, решение двойственной задачи следующее:

Решение несимметричных задач

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

Решив двойственную задачу графическим методом, получим

По 1-й теореме двойственности L()min = S()max = 33/2.

Подставим опт в систему ограничений двойственной задачи:

Так как х3 = х4 = 0, то система ограничений исходной задачи примет вид

Решая данную систему, получим

Рассмотрим решение задач с использованием обратной матрицы.

Пусть решение исходной задачи

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

где

Таким образом, oпт = (1/2, 2), при этом S()max = 33/2.

Решение смешанных двойственных задач

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

Найдем оптимальное решение двойственной задачи:

По 1-й теореме двойственности

Так как х1 > 0, x3 > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств:

 

Экономический анализ задач с использованием теории двойственности

Рассмотрим задачу оптимального использования ресурсов, запишем ее математическую модель

при ограничениях:

Двойственная задача имеет вид

при ограничениях:

ТЕОРЕМА 3. Значения переменных уi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов системы ограничений исходной задачи на оптимальное значение ее целевой функции, т.е.

Примем Li ≈ ΔLi, bi ≈ Δbi, тогда ΔLi ≈ yi • Δbi.

Для задачи оптимального использования сырья это уравнение показывает, что при изменении i-го ресурса оптимальный доход является линейной функцией от его приращения, причем коэффициентом служит уi — i-я компонента оптимального решения двойственной задачи.

Если yi мало, то значительному увеличению i-го ресурса будет соответствовать небольшое увеличение оптимального дохода и ценность ресурса невелика.

Если yi = 0, то при увеличении i-го ресурса оптимальный доход остается неизменным и ценность этого ресурса равна нулю. В самом деле, сырье, запасы которого превышают потребности в нем, не представляет ценности для производства и его оценку можно принять за нуль.

Если уi велико, то незначительному увеличению i-го ресурса будет соответствовать существенное увеличение оптимального дохода и ценность ресурса высока. Уменьшение ресурса ведет к существенному сокращению выпуска продукции.

Переменную уi считают некоторой характеристикой ценности i-го ресурса. В частности, при увеличении i-го ресурса на единицу (Δbi = 1) оптимальный доход возрастает на yi, что позволяет рассматривать yi как "условную цену", оценку единицы i-го ресурса, объективно обусловленную оценку.

Так как уi представляет частную производную от оптимального дохода по i-му ресурсу, то уi характеризует скорость изменения оптимального дохода при изменении i-го ресурса.

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

где xj — значение переменной в оптимальном решении; dij — элементы матрицы (dij) = А-1, обратной к матрице базиса оптимального решения, для которой А = (aij)mxn.

Если в план включаются новые виды продукции, то их оценка находится по формуле

Если Δj < 0, то новый вид продукции улучшает план. При Δj > 0 нецелесообразно включать новый вид продукции.

Понятие комплексного числа. Комплексным числом называется выражение вида a + ib , где a и b – любые действительные числа, i – специальное число, которое называется мнимой единицей . Для таких выражений понятия равенства и операции сложения и умножения вводятся следующим образом: Два комплексных числа a + ib и c + id называются равными тогда и только тогда, когда a = b и c = d . Суммой двух комплексных чисел a + ib и c + id называется комплексное число a + c + i ( b + d ). Произведением двух комплексных чисел a + ib и c + id называется комплексное число ac – bd + i ( ad + bc ).
Решение задач математического анализа