Шпаргалка по Математическому программированию (стр. 6 из 8)
6. Загруж-т перспективную клетку. Оформл-т нов.опорн.план в виде трансп.таблицы. Переходят к пункту 4.
54. Учет затрат на производство и транспортировку продукции. Транспортная задача с запретами на поставки.
При решении некоторых задач необходимо учитывать затраты не только на перевозку груза, но и на производство перевозимой продукции. Для этого в матрице трансп. задачи
Где Cij ‘ – приведенные затрат на производство одной единицы продукции.
Cij “– затраты на транспортировку одной единицы продукции.
Дальше задача решается обычным способом.
Задачи с запретами на поставки.
В некоторых ситуациях нельзя перевозить продукцию по какому-либо маршруту.
Для этого в матрице транспортной задачи перевозка через которую является запретной проставляется запрещающий тариф М. дальше задача решается обычным способом., однако этой клетке всегда будет соответствовать отрицательная оценка клетки.
55. учет ограничений по пропускной способности маршрутов, учет обязательности некоторых поставок в транспортной задаче.
учет ограничений по пропускной способности маршрутов.
В некоторых транспортных задачах по некоторым маршрутам устанавливают меньшую пропускную способность чем необходимо для удовлетворения спроса пункта потребления.
учет обязательности некоторых поставок в транспортной задаче.
В некоторых случаях в задаче требуется, что например по маршруту Ak Bs должно обязательно осуществиться поставка в объема А ед. В этом случае из объема производства пункта А и объем S Bs вчитается обязательная поставка и задача решается относительно необязательности поставок. После получения оптимального решения обязательно поставка добавляется к объему стоящему в клетке Ak Bs.
56. Возможные выводы при экономич. интерпретации оптимального распределения для открытых транспортных задач.
При получении оптимального распределения необходимо вернуться к исходной задаче и сделать соответствующие экономич. выводы. Они следующие:
1. если введен пункт потребления, то это означает, что в анализируемоой системе излишни объемы производства, и можно без ущерба для рассматриваемой системы уменьшить мощности тех пунктов производства на величину привязки, которые привязались к фиктивному пункту потребления.
2. если же введен фиктивный пункт производства, то это означает, что мощностей реальных пунктов производства не хватает и их необходимо увеличить. Увеличиваются мощности тех пунктов производства, которые ближе всего расположены к пунктам потребления, привязанным к фиктивному пункту производства. Производится увеличение мощности производителя на величину привязки. Для этого рассматривают столбец пункта потребления, который привязан к фиктивному пункту производства, и находят в нем наименьший тариф. Мощность соответствующего этому тарифу пункта производства наиболее эффективно увеличить на величину привязки.
57.Понятие двойственности. Экономическая постановка двойственных задач на примере задачи об оптимизации плана выпуска продукции.
Двойственная задача - это вспомогательная задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой задачи.
Пусть имеется зада об оптимизации плана выпуска продукции. Она имеет следующий вид:
Исходная задача:
а11х1+а12х2+…+ а1пхп≤в1 |у1
а21х1+а22х2+…+ а2пхп≤в2 |у2
……………….. |.. (1)
ат1х1+ат2х2+…+ атпхп≤в1 | ут
xj≥0, j = 1,n(2)
z = c1x1+c2x2+…+cnxn ->max(3)
_
X = (x1,x2,…, xn)
aij – кол-во сырья i- го вида, затраченного для выпуска j-го вида продукции
Двойственная задача
Пусть предприятие по какой-либо причине не может выпускать продукцию. Для того, чтобы уменьшить затраты простоя, предприятие может реализовать сырье, которое у него имеется. По каким ценам нужно реализовать сырье?
уi- цена i- го вида сырья имеющегося на предприятии.
а11у1+а21у2+…+ ат1ут≥с1
а12х1+а22у2+…+ ат2хп≥с2
……………….. (1’)
а1пу1+а2пу2+…+ атпут≥сп
уi≥0, j = 1,m(2’)
F = b1y1+b2y2+…+bmym ->min(3’)
58. Соответствие между структурными элементами прямой и двойственной задачи
Каждой задаче линейного программирования можно сопоставить
двойственную задачу по следующим правилам:
1. Во всех ограничениях исходной задачи свободные члены должны
находиться справа, а члены с неизвестными - слева.
2. Ограничения-неравенства исходной задачи должны иметь знаки,
направленные в одну строну.
3. Если целевая функция в исходной задаче минимизируется, ограничения-неравенства следует записать со знаком «≤» , тогда в двойственной задаче целевая функция будет минимизироваться и знаки ограничений-неравенств будут «≥».
4. Каждому ограничению исходной задачи соответствует переменная в
двойственной задаче. Если переменная соответствует неравенству, она неотрицательна, если равенству – то переменная без ограничений на знак («произвольная»).
5. Коэффициенты при переменных в ограничениях двойственной задачи получаются транспонированием матрицы, составленной из
коэффициентов при переменных исходной задачи.
6. Свободные члены исходной задачи являются коэффициентами при
переменных в функции цели двойственной задачи, а свободными
членами в двойственной задаче – коэффициенты при переменных в
функции исходной задачи.Отметим также, что соотношение двойственности взаимное, т.е. задача, двойственная по отношению к двойственной, совпадает с исходной.Двойственные пары задач подразделяются на симметричные и несимметричные. В симметричной паре ограничения прямой и двойственной задач являются нестрогими неравенствами и, следовательно, переменные обеих задач могут принимать только неотрицательные значения.
59. Построение двойственных задач к исходным задачам, записанным в стандартной, канонической и общей форме модели(построение симметричных и несимметричных двойств. задач)
Стандартная форма (исходная)
n
Σ aijxj ≤ bi, i=1,n(1)
j=1
xj≥0, j=1,n(2)
n
z = Σ cjxj ->max(3)
j=1
Двойственная стандартная
m
Σ aijyi ≤ cj, j=1,n(1)
i=1
yi≥0, j=1,m(2)
m
F = Σ biyi ->min(3)
i=1
Исходная задача в канонической форме:
n
Σ aijxj = bi, i=1,m(1)
j=1
xj≥0, j=1,n(2)
n
z = Σ cjxj ->min(3)
j=1
Двойственная каноническая
m
Σ aijyi ≤ cj, j=1,n(1)
i=1
yi- любые (2)
m
F = Σ biyi ->max(3)
i=1
Дадим экономическую интерпретацию пары двойственных задач. Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами b1,b2,…bm, которые могут использ-ся для выпуска n-видов продукции. Пусть также известны стоимость единицы j-вида продукции cj (j=1,n) и норма потребления i-го ресурса (i=1,m) на производство единицы j-й продукции – aij.Требуется определить объем производства продукции каждого вида xj (j=1,n), максимизирующий суммарную стоимость
f= c1x1+…+cnxn (1)
При этом расход ресурсов не должен превышать их наличия:
a11x1+…+a1nxn<=b1 }
…………………….. } (2)
am1x1+…+amnxn<=bm }
Все известные по своему экономическому смыслу неотрицательны:
Xj>=0 (j=1,n). (3)
Заметим, что это задача образуют симитричную двойственную задачу.
Несимметричные двойственные задачи.
Возьмем ЗЛП на максимум в канонической форме:
Max Z=(n;j=1)Σcj*xj
(n;j=1)Σaij*xj=bi (i=1,m)
Xj>=0 (j=1,n).
60.Основная и вторая теорема двойственности (сформулировать теоремы и разъяснить)
Первая теорема двойственности.
Теорема: если одна из двойственных задач имеет оптимальный план, то и другая решима, т.е. имеет опт.план. При этом экстремальные значен.целевых функций совпадают (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi* если в исходн. задаче целевая функция неограниченна на множестве планов, то в двойственной задаче система ограничений несовместна.
Вторая теорема двойственности и ее эконом.интерпритация.
Для того, чтобы допустимые решения пары двойственных задач были оптимальными, необходимо и достаточно выполнение условия: xj*(∑aij yi*-cj)=0, j от 1 до n, yi*(∑aij xj*-bi)=0, I от 1 до m. Это условия дополняющей нежесткости. Из них следует: если какое-либо ограничение двойств.задачи обращ-ся оптималь.планом в строгое равенство, то соответствующая компонента опт. плана двойственной задачи должно равняться нулю.Если же какая-то компонента опт. плана равна нулю, то соответствующее ограничение двойств.задачи обращается опт.планом в строгое равенство хj*>0 следовательно (i= от 1 до m)Σaij yi*=cj (затраты на пр-во продукции=цене) – Если продукция вошла в опт.план, то если затраты>цены, объем пр-ва=0 Σaij yi* >cj следовательно xj*=0
yi*>0 следовательно (j=от 1 до n) Σaij xj*=bi (рас-ды рес-ов =запас рес-ов).
(j=от 1 до n) Σaij xj* <bi следовательно yi*=0