--PAGE_BREAK--
Теорема. Если в оптимальном плане
(7)
М-задачи (4)-(6) все искусственные переменные , то план является оптимальным планом исходной задачи (1)-(3).
Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М-задачу, которая имеет начальный опорный план
Решение исходной задачи симплексным методом путем введения искусственных переменных называется симплексным методом с искусственным базисом.
Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные , то его первые nкомпоненты дают оптимальный план исходной задачи.
Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.
3.1 Признаки оптимальности.
Теорема.Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки неотрицательны, то такой план оптимален.
Теорема.Если исходная задача решается на минимум и для некоторого опорного плана все оценки неположительны, то такой план оптимален.
§4. Понятие двойственности.
Понятие двойственности рассмотрим на примере задачи оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья mвидов в объемахединиц . Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск nвидов неосновной продукции. Обозначим через норму расхода сырья i-го вида на единицу j-й продукции, — цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величины задачи: — объемы выпуска j-й продукции, обеспечивающие предприятию максимум выручки.
Математическая модель задачи:
(1)
(2)
(3)
Предположим далее, что с самого начала при изучении вопроса об использовании отходов основного производства на предприятии появилась возможность реализации их некоторой организации. Необходимо установить прикидочные оценки (цены) на эти отходы. Обозначим их .
Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы предприятия и организации:
1) общую стоимость отходов сырья покупающая организация стремится минимизировать;
2) предприятие согласно уступить отходы только по таким ценам, при которых оно получит за них выручку, не меньшую той, что могло бы получить, организовав собственное производство.
Эти требования формализуются в виде следующей ЗЛП.
Требование 1 покупающей организации – минимизация покупки: (4)
Требование 2 предприятия, реализующего отходы сырья, можно сформулировать в виде системы ограничений. Предприятие откажется от выпуска каждой единицы продукции первого вида, если , где левая часть означает выручку за сырьё идущее на единицу продукции первого вида; правая – её цену.
Аналогичные рассуждения логично провести в отношении выпуска продукции каждого вида. Поэтому требование предприятия, реализующего отходы сырья, можно формализовать в виде сл. системы ограничений:
(5)
По смыслу задачи оценки не должны быть отрицательными:
(6)
Переменные называют двойственными оценками или объективно обусловленными оценками.
Задачи (1)-(3) и (4)-(6) называют парой взаимно двойственных ЗПЛ.
Между прямой и двойственной задачами можно установить следующую взаимосвязь:
1. Если прямая задача на максимум, то двойственная к ней — на минимум, и наоборот.
2. Коэффициенты целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.
3. Свободные члены ограничений прямой задачи являются коэффициентами целевой функции двойственной.
4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.
5. Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа . Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .
6. Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной — числу переменных прямой.
7. Все переменные в обеих задачах неотрицательны.
Теорема. Для любых допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т.е.
(7) – основное неравенство теории двойственности.
Теорема. (критерий оптимальности Канторовича)
Если для некоторых допустимых планов и пары двойственных задач выполняется неравенство , то и являются оптимальными планами соответствующих задач.
Теорема. (малая теорема двойственности)
Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существование допустимого плана для каждой из них.
§5. Основные теоремы двойственности
и их экономическое содержание
Теорема.
Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций равны: . Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.
Экономическое содержание первой теоремы двойственности состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадение значений целевых функций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были оптимальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Двойственные оценки, обладают тем свойством, что они гарантируют рентабельность оптимального плана, т. е. равенство общей оценки продукции и ресурсов, и обусловливают убыточность всякого другого плана, отличного от оптимального. Двойственные оценки позволяют сопоставить и сбалансировать затраты и результаты системы.
Теорема. (о дополняющей нежесткости )
Для того, чтобы планы и пары двойственных задач были оптимальны, необходимо и достаточно выполнение условий:
(1)
(2)
Условия (1), (2) называются условиями дополняющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.
Экономически это означает, что если по некоторому оптимальному плану производства расход i-го ресурса строго меньше его запаса , то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его i-я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а ресурс избыточный (используемый не полностью) имеет нулевую оценку.
Теорема .(об оценках).Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи математического программирования, точнее
(3)
§6. Примеры экономических задач
5.1 Задача о наилучшем использовании ресурсов.Пусть некоторая производственная единица (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать nразличных видов продукции (товаров), известных под номерами, обозначаемыми индексом j. Ее будем обозначать . Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингредиентами . Пусть их число равно m; припишем им индекс i . Они ограничены, и их количества равны соответственно условных единиц. Таким образом, — вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т. д. Примем в качестве такой меры, например, цену реализации
, т. е. —вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов называют технологической и обозначают буквой А. Имеем . Обозначим через план производства, показывающий, какие виды товаров нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.
Так как — цена реализации единицы j'-й продукции, цена реализованных единиц будет равна , а общий объем реализации
Это выражение — целевая функция, которую нужно максимизировать.
Так как — расход i-го ресурса на производство единиц j-й продукции, то, просуммировав расход i-горесурса на выпуск всех nвидов продукции, получим общий расход этого ресурса, который не должен превосходить единиц:
Чтобы искомый план был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объёмы выпуска продукции:
.
Таким образом, модель задачи о наилучшем использовании ресурсов примет вид:
(1)
при ограничениях:
(2)
(3)
Так как переменные входят в функцию и систему ограничений только в первой степени, а показатели являются постоянными в планируемый период, то (1)-(3) – задача линейного программирования.
5.2 Задача о смесях.
В различных отраслях народного хозяйства возникает проблема составления таких рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего определенными свойствами. К этой группе задач относятся задачи о выборе диеты, составлении кормового рациона в животноводстве, шихт в металлургии, горючих и смазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве и т. д. Высокий уровень затрат на исходные сырьевые материалы и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными свойствами при наименьших затратах на исходные сырьевые материалы.
5.3 Задача о раскрое материалов.
Сущность задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму. Рассмотрим простейшую модель раскроя по одному измерению. Более сложные постановки ведут к задачам целочисленного программирования.
5.4 Транспортная задача.
Рассмотрим простейший вариант модели транспортной задачи, когда речь идет о рациональной перевозке некоторого однородного продукта от производителей к потребителям; при этом имеется баланс между суммарным спросом потребителей и возможностями поставщиков по их удовлетворению. Причем потребителям безразлично, из каких пунктов производства будет поступать продукция, лишь бы их заявки были полностью удовлетворены. Так как от схемы прикрепления потребителей к поставщикам существенно зависит объем транспортной работы, возникает задача о наиболее рациональном прикреплении, правильном направлении перевозок грузов, при котором потребности полностью удовлетворяются, вся продукция от поставщиков вывозится, а затраты на транспортировку минимальны.
5.5 Задача о размещении заказа.
Речь идет о задаче распределения заказа (загрузки взаимозаменяемых групп оборудования) между предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказа. Требуется составить план размещения заказа (загрузки оборудования), при котором с имеющимися производственными возможностями заказ был бы выполнен, а показатель эффективности достигал экстремального значения. продолжение
--PAGE_BREAK--
§7. Анализ задачи об оптимальном использовании сырья.
Исходя из специализации и своих технологических возможностей предприятие может выступать четыре вида продукции. Сбыт любого количества обеспечен. Для изготовления этой продукции используются трудовые ресурсы, полуфабрикаты и станочное оборудование. Общий объём ресурсов, расход каждого ресурса за единицу продукции, приведены в таблице 1. Требуется определить план выпуска, доставляющий предприятию максимум прибыли. Выполнить после оптимизационный анализ решения и параметров модели.
Ресурсы
Выпускаемая продукция
Объём
Ресурсов
Трудовые ресурсы, чел-ч
4
2
2
8
4800
Полуфабрикаты, кг
2
10
6
0
2400
Станочное оборудование, станко-ч
1
0
2
1
1500
Цена единицы продукции, р.
65
70
60
120
Решение.
Пусть — объёмы продукции планируемый к выпуску; — сумма ожидаемой выручки.
Математическая модель пря мой задачи:
Математическая модель двойственной задачи:
По условиям примера найти:
1. Ассортимент выпускаемой продукции, обеспечивающий предприятию максимум реализации (максимум выручки)
2. Оценки ресурсов, используемых при производстве продукции.
Симплексным методом решаем прямую задачу, модель которой составлена выше в таблице1.
После второй итерации все оценки оказались отрицательными, значит, найденный опорный план является оптимальным: ,
Основные переменные показывают, что продукциюи выпускать нецелесообразно, а продукции следует произвести 400 ед., — 500 ед.
Дополнительные переменные и показывают, что ресурсы используются полностью , а вот равенство свидетельствует о том, что 200 единиц продукции осталось неиспользованным.
Номера ит.
БП
Сб
65
70
60
120
0
0
0
0
0
4800
4
2
2
8
1
0
0
0
2400
2
10
6
0
0
1
0
0
1500
1
0
2
1
0
0
1
0
-65
-70
-60
-120
0
0
0
1
120
600
1/2
1/4
1/4
1
1/8
0
2400
2
6
1
0
900
1/2
-1/4
7/4
-1/8
1
72000
-5
-40
-30
15
2
120
500
5/12
-1/6
1
1/8
-1/24
60
400
1/3
5/3
1
1/6
200
-1/12
-19,6
-1/8
-7/24
1
84000
5
10
15
5
Выпишем из таблицы2. Компоненты оптимального плана двойственной задачи – двойственные оценки. В канонической форме прямой задачи переменные — являются свободными, а дополнительные переменные — базисными. В канонической форме двойственной задачи свободными будут переменные — а базисными
Соответствие между переменными примет вид
Учитывая это соответствие, выпишем из индексной строки последней итерации компоненты искомого плана — двойственные оценки.
minf= maxZ=84000.
Запишем это неравенство в развернутой форме:
48000*15 + 2400*5 + 1500*0 = 65*0 + 70*0 + 60*400 + 120*500
Учитывая, что компонеты представляют собой оценки ресурсов заключаем:
При оптимальном плане оценка ресурсов, затраченных на выпуск продукции, совпадает с оценкой произведенной продукции.
Теперь установим степень дефицитности используемых ресурсов и обоснуем рентабельность оптимального плана.
Мы нашли оптимальный план выпуска продукции. При этом плане третье ограничение прямой задачи выполняется как строгое неравенство:
0+2-400+500= 1300 меньше его запаса, т. е. ресурс избыточный. Именно поэтому в оптимальном плане двойственной задачи оценка этого ресурса равна нулю.
А вот оценки и ресурсов и выражаются положительными числами 15 и 5, что свидетельствует о дефицитности этих ресурсов: они при оптимальном плане используются полностью. В самом деле, ограничения по этим ресурсам выполняются как строгие равенства: 4.0+2.0+2.400+8.500=4800, 2-0+10.0+6.400=2400.
Поскольку 15>5, ресурс считается более дефицитным, чем ресурс .
На основе теоремы (о дополняющей нежесткости) нетрудно объяснить, почему не вошла в оптимальный план продукция и : первое и второе ограничения двойственной задачи выполняются как строгие неравенства: 4-15+2-5+0>65, 2-15+10*5>70.
Это означает, что оценки ресурсов, расходуемых на изготовление единицы продукции и , превышают оценки единицы этой продукции. Понятно, что такую продукцию выпускать предприятию невыгодно. Что же касается продукции и ,то выпуск ее оправдан, поскольку оценка израсходованных ресурсов совпадает с оценкой произведенной продукции: 2*15+ +6*5+2*0=60, 8*15+0=120.
Таким образом, в оптимальный план войдет только та продукция, которая выгодна предприятию, и не войдет убыточная продукция. В этом проявляется рентабельность оптимального плана.
Рассмотрим возможность дальнейшего совершенствования оптимального ассортимента выпускаемой продукции.
Выше установлено, что ресурсы и являются дефицитными. В связи с этим на основе теоремы (об оценках) можно утверждать, что на каждую единицу ресурса , введенную дополнительно в производство, будет получена дополнительная выручка , численно равная .В самом деле, при получаем . По тем же причинам каждая дополнительная единица ресурсаобеспечит прирост выручки, равный 5 р. Теперь становится понятно, почему ресурс считается более дефицитным по сравнению с ресурсом : он может содействовать получению большей выручки.
Что же касается избыточного ресурса продолжение
--PAGE_BREAK--