Курс лекци Русакова по методам оптимизации (1083216), страница 7
Текст из файла (страница 7)
7 и 8).Как видно из рис. 8, максимальное значение целевая функция исходнойзадачи принимает в точке В. Следовательно, Х*=(2, 6) является оптимальнымпланом, при котором. Минимальное значение целевая функциядвойственной задачи принимает в точке Е (рис. 8). Значит, Y*=(1; 4) являетсяоптимальным планом двойственной задачи, при котором57Такимобразом, значения целевых функций исходной и двойственной задач при ихоптимальных планах равны между собой.Рис. 7рис. 8Из рис 7. видно, что при всяком плане исходной задачи значениецелевой функции не больше 46. Одновременно, как видно из рис. 8, значениецелевой функции двойственной задачи при любом ее плане не меньше 46.Таким образом, при любом плане исходной задачи значение целевойфункции не превосходит значения целевой функции двойственной задачипри ее произвольном плане.ПримерНайти решение двойственной пары задач.Исходная задача;Двойственная задача:Решение.58Как исходная, так и двойственная задача содержат по две переменные.Поэтому их решение находим, используя геометрическую интерпретациюзадачи линейного программирования (рис.
7 и 8).Из рис. 7 видно, что исходная задача не имеет оптимального плана изза неограниченности снизу ее целевой функции на множестве допустимыхрешений.Из рис. 10 следует, что двойственная задача не имеет планов,поскольку многоугольник решений ее пуст. Это означает, что если исходнаязадачадвойственнойпарынеимеетоптимальногопланаиз-занеограниченности на множестве допустимых решений ее целевой функции,то двойственная задача также не имеет планов.Рис.
10.Нахождениерешениядвойственныхзадач.Рассмотримпарудвойственных задач – основную задачу линейного программирования (д12) –(д14) и двойственную к ней задачу (д15), (д16).Предположим,чтоспомощьюсимплексногометоданайденоптимальный план X* задачи (д12) – (д14) и этот план определяется базисом,образованным векторамиОбозначимчерез.вектор-строку,составленнуюизкоэффициентов при неизвестных в целевой функции (д12) задачи (д12) –59(д14), а через– матрицу, обратную матрице Р, составленной из компонентвекторовбазиса.
Тогда имеет место следующее утверждение.Теорема.ЕслиосновнаяоптимальныйзадачаX*,планлинейноготопрограммированияявляетсяоптимальнымимеетпланомдвойственной задачи.Таким образом, если найти симплексным методом оптимальный планзадачи (д12) – (д14), то, используя последнюю симплекс–таблицу, можноопределитьии с помощью соотношениянайти оптимальныйплан двойственной задачи (д15), (д16).В том случае, когда среди векторов, составленных изкоэффициентов при неизвестных в системе уравнений (д13), имеется тединичных, указанную матрицуобразуют числа первых т строкпоследней симплекс–таблицы, стоящие в столбцах данных векторов.
Тогданет необходимости определять оптимальный план двойственной задачиумножениемна, поскольку компоненты этого плана совпадают ссоответствующими элементами (m+1)–й строки столбцов единичныхвекторов, если данный коэффициентэлемента этой строки и, и равны сумме соответствующегоеслиСказанное выше имеет место и для симметричной пары двойственныхзадач. При этом так как система ограничений исходной задачи содержитнеравенства вида “”, то компоненты оптимального плана двойственнойзадачи совпадают с соответствующими числами (m+1)–й строки последнейсимплекс–таблицы решения исходной задачи.
Указанные числа стоят встолбцах векторов, соответствующих дополнительным переменным.60Пример.Для задачи, состоящей в определении максимального значенияфункциипри условияхсоставить двойственную задачу и найти ее решение.Решение.Двойственная задача по отношению к исходной состоит в нахожденииминимума функциипри условияхЧтобы найти решение двойственной задачи, сначала находим решениеисходной задачи методом искусственного базиса. Оно приведено в таблице12.Из последней симплекс-таблицы видно, что двойственная задача имеетрешениеОптимальные двойственные оценки удовлетворяют всем условиямдвойственной задачи.
При этом минимальное значение целевой функциидвойственнойзадачи,равноемаксимальным значением целевой функцииТаблица 1261совпадаетисходной задачи.сiБазисСб Р012–100–МP24P3–2p41p50Р60120101p40P112 –12P5017 13p6–М 42–120010–1–2100045p40–4 –21–20001P5014 07/2–1101/22p1115 03/2101–1/2221–1/21001/234p2020–5/22001/21P51401–2/72/701/72p190013/7 –3/7 1–5/734106/71/704/7412 009/75/706/7Экономическая интерпретация двойственных задачЭкономическую интерпретацию двойственных задач и двойственныхоценок рассмотрим на примере.ПримерДля производства трех видов изделий А, В и С используется триразличных вида сырья. Каждый из видов сырья может быть использован вколичестве, соответственно не большем 180, 210 и 244 кг.
Нормы затрат62каждого из видов сырья на единицу продукции данного вида и цена единицыпродукции каждого вида приведены в таблице.Определить план выпуска продукции, при котором обеспечивается еемаксимальная стоимость, и оценить каждый из видов сырья, используемыхдля производства продукции.
Оценки, приписываемые каждому из видовсырья, должны быть такими, чтобы оценка всего используемого сырья быламинимальной, а суммарная оценка сырья, используемого на производствоединицы продукции каждого вида,– не меньше цены единицы продукцииданного вида.ТаблицаВид сырьяНормы затрат сырья (кг) наединицу продукцииIА4В2С1II313III125Ценаединицыпродукции(руб.)101412Решение.Предположим, что производится x1 изделий А,изделий В иизде-лий С. Для определения оптимального плана производства нужно решитьзадачу, состоящую в максимизации целевой функции(д17)при следующих условиях63(д18)(д19)Припишем каждому из видов сырья, используемых для производствапродукции, двойственную оценку, соответственно равнуюи у3.Тогдаобщая оценка сырья, используемого на производство продукции, составит(д20)Согласно условию, двойственные оценки должны быть такими, чтобыобщая оценка сырья, используемого на производство единицы продукциикаждого вида, была не меньше цены единицы продукции данного вида, т.е.и у3 должны удовлетворять следующей системе неравенств:(д21)(д22)Как видно, задачи (д17) – (д19) и (д20) – (д22) образуют симметричнуюпару двойственных задач.
Решение прямой задачи дает оптимальный планпроизводства изделий A, В и С, а решение двойственной – оптимальнуюсистему оценок сырья, используемого для производства этих изделий. Чтобынайти решение этих задач, следует сначала отыскать решение какой–либоодной из них. Так как система ограничений задачи (д17) – (д19) содержитлишь неравенства вида “”, то лучше сначала найти решение этой задачи.Ее решение приведено в таблице 14.Из этой таблицы видно, что оптимальным планом производстваизделий является такой, при котором изготовляется 82 изделия В и 16изделийС.
При данном плане производства остается неиспользованным 80 кгсырья II вида, а общая стоимость изделий равна 1340 руб. Из таблицы 1464такжевидно,чтооптимальнымрешениемдвойственнойзадачиявляетсяТаблицаiБазисСбР0101412000P21P30p45/8p50Р6–1/81p21482P119/82P508023/8001/81–5/83p31216–3/401–1/401/4134057/40023/405/4Переменныеиобозначают условные двойственные оценкиединицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, асырье 1 и III видов полностью используется при оптимальном планепроизводства продукции.
Двойственная оценка единицы сырья II вида равнанулю. Этот вид сырья не полностью используется при оптимальном планепроизводства продукции.Таким образом, положительную двойственную оценку имеют лишь тевиды сырья, которые полностью используются при оптимальном планепроизводстваизделий.Поэтомудвойственныеоценкиопределяютдефицитность используемого предприятием сырья. Более того, величинаданнойдвойственнойоценкипоказывает,наскольковозрастаетмаксимальное значение целевой функции прямой задачи при увеличенииколичества сырья соответствующего вида на 1 кг. Так, увеличениеколичества сырья I вида на 1 кг приведет к тому, что появится возможностьнайти новый оптимальный план производства изделий, при котором общаястоимость изготовляемой продукции возрастет на 5,75 руб.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
