Основы математики и ее приложения в экономическом образовании (стр. 34 )

21.7. L() = 3x1 + x2 + x3 + x4 → max при ограничениях:

21.8. L() = x1 - 5x2 – x3 → max при ограничениях:

21.9. L() = x1 + х2 + x3 + x4 → min при ограничениях:

21.10. L() = 3x1 + 5x2 + 4x3 → max при ограничениях:

21.11. Механический завод при изготовлении двух типов дета­лей использует токарное, фрезерное и сварочное оборудование. При этом обработку каждой детали можно вести двумя раз­личными технологическими способами. Необходимые исход­ные данные приведены в табл. 21.9.

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

21.12. Торговая фирма для продажи товаров трех видов ис­пользует ресурсы: время и площадь торговых залов. Затраты ресурсов на продажу одной партии товаров каждого вида да­ны в табл. 21.10. Прибыль, получаемая от реализации одной партии товаров 1-го вида, — 5 усл. ед., 2-го вида — 8 усл. ед., 3-го вида — 6 усл. ед.

Определить оптимальную структуру товарооборота, обес­печивающую фирме максимальную прибыль.

21.13. Фирма выпускает четыре пользующихся спросом изде­лия, причем месячная программа выпуска составляет 10 изде­лий типа 1 и 3, 200 изделий типа 2 и 120 изделий типа 4. Нормы затрат сырья на единицу различных типов изделий приведены в табл. 21.11.

Прибыль от реализации изделий типа 1 равна 6 усл. ед., изделий типа 2 — 2 усл. ед., изделий типа 3 — 2,5 усл. ед. и изделий типа 4 — 4 усл. ед.

Определить, является ли месячная программа выпуска из­делий оптимальной, и если нет, то определить оптимальную месячную программу и дополнительный доход, который фир­ма может при этом получить.

21.14. Металлургический завод из металлов A1, A2, А3 может выпускать сплавы B1, В2, В3. В течение планируемого пери­ода завод должен освоить не менее 640 т металла A1 и 800 т металла А2, при этом металла А3 может быть израсходовано не более 860 т.

Определить минимальные затраты, если данные о нормах расхода и себестоимость даны в табл. 21.12.

21.15. Ткань трех артикулов производится на ткацких станках двух типов с различной производительностью. Для изготов­ления ткани используются пряжа и красители. В табл. 21.13 указаны мощности станков в тысячах станко-часов, ресурсы пряжи и красителей в 1000 кг, производительности станков в метрах за час, нормы расхода пряжи и краски в килограммах на 1000 м и цена 1 м ткани.

По этим исходным данным решить следующие задачи:

1) определить оптимальный ассортимент, максимизирую­щий товарную продукцию предприятия;

2) приняв условие, что количество тканей трех артикулов находится в отношении 2:1:3, определить, какое мак­симальное количество комплектов ткани может выпус­тить предприятие;

3) определить оптимальный ассортимент, максимизирую­щий доход предприятия, если цена 1 м ткани составляет 8, 5 и 15 усл. ед. соответственно;

4) решить задачу (1) при условии, что станки 1-го типа ткань первого артикула не производят.

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

Различают симметричные, несимметричные и смешанные двойственные задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решим исходную задачу графическим методом, получим опт = (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-й теореме двойственности пер­вое и третье ограничения двойственной задачи выполняются в виде равенств:

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

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

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

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

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

ТЕОРЕМА 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.