Тема 5: Двойственные оценки

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

Решение. Как видим, прямая задача записана в общей форме. Это будем учитывать при расстановке знаков в условиях двойственной задачи. А пока, произведём универсальное действие - составим матрицу B прямой задачи и транспонированную матрицу B ' двойственной задачи:

,

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

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

Решение. Третье неравенство системы исходной задачи не удовлетворяет пункту 1 правил составления двойственной задачи. Поэтому умножим его на минус единицу:

Для облегчения составления двойственной задачи лучше пользоваться расширенной матрицей B, в которую наряду с коэффициентами при переменных системы ограничений исходной задачи запишем свободные члены и коэффициенты при переменных в функции цели, выделив для этой цели дополнительные столбец (отделён чертой) и строку (выделена красным цветом). Матрицу B транспонируем и, используя транспонированную матрицу B ', составляем задачу, двойственную исходной. Матрицы B и B ' имеют вид

,

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

Тема 6: Транспортная задача

Из трех холодильников A_i, i=1..3, вмещающих мороженную рыбу в количествах a_i т, необходимо последнюю доставить в пять магазинов B_j, j=1..5 в количествах b_j т. Стоимости перевозки 1т рыбы из холодильника A_i в магазин B_j заданы в виде матрицы C_ij, 3x5.

Построить закрытую модель транспортной задачи.

Тема 1: Общая методология оптимизационных задач. Основные

Понятия

Производственная задача. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

Обозначим: Х ₁ - число изготовленных стульев, Х ₂ - число сделанных столов. Задача оптимизации имеет вид:

45 Х ₁ + 80 Х ₂ → max,

5 Х ₁ + 20 Х ₂ ≤ 400,

10 Х ₁ + 15 Х ₂ ≤ 450,

Х ₁ ≥ 0,

Х ₂ ≥ 0.

В первой строке выписана целевая функция - прибыль при выпуске Х ₁ стульев и Х ₂ столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х₁ и Х ₂ . При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если Х ₁ = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то Х ₁ положительно. Но невозможно представить себе отрицательный выпуск - Х ₁ не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.

. Будем по горизонтальной оси абсцисс откладывать значения Х ₁, а по вертикальной оси ординат - значения Х ₂. Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х _1, Х ₂) объемов выпуска в виде треугольника (рис.1).

Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х ₁, соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х ₂, соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на

изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - материал останется.

Аналогичным образом можно изобразить и ограничения по труду (рис.2).

Таким образом, ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х ₁, соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х ₂, соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - часть рабочих будет простаивать.

Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?

Чтобы ответить на этот вопрос, надо "совместить" рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).

Таким образом, множество возможных значений объемов выпуска стульев и столов (Х ₁, Х ₂ ), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений

5 Х ₁ + 20 Х ₂ = 400,

10 Х ₁ + 15 Х ₂ = 450.

Из первого уравнения: 5 Х ₁ = 400 - 20 Х ₂, Х ₁ = 80 - 4 Х ₂. Подставляем во второе уравнение:

10 (80 - 4 Х ₂) + 15 Х ₂ = 800 - 40 Х ₂ + 15 Х ₂ = 800 - 25 Х ₂ = 450,

следовательно, 25 Х ₂ = 350, Х ₂ = 14, откуда Х ₁ = 80 - 4 х 14 = 80 -56 =24.

Итак, четвертая вершина четырехугольника - это (24, 14).

Надо найти максимум линейной функции на выпуклом многоугольнике. (В общем случае линейного программирования - максимум линейной функции на выпуклом многограннике, лежащем в конечномерном линейном пространстве.) Основная идея линейного программирования состоит в том, что максимум достигается в вершинах многоугольника. В общем случае - в одной вершине, и это - единственная точка максимума. В частном - в двух, и тогда отрезок, их соединяющий, тоже состоит из точек максимума.

Целевая функция 45 Х ₁ + 80 Х ₂ принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х ₁ + 80 Х ₂ = 2200 проходит между прямыми ограничений 5 Х ₁ + 20 Х ₂ = 400 и 10 Х ₁ + 15 Х ₂ = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).

Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.