|
Реферат: Линейное и динамическое программированиеОбозначим через xij количество груза, планируемого к перевозке от i-ro поставщика j-му потребителю. При наличии баланса производства и потребления математическая модель транспортной задачи будет выглядеть так: найти план перевозок X=(xij), xij³0, iÎNm, jÎNn минимизирующий общую стоимость всех перевозок
при условии, что из любого пункта производства вывозится весь продукт , iÎNm и любому потребителю доставляется необходимое количество груза , jÎNn Для решения транспортной задачи чаще всего применяется метод потенциалов. Пусть исходные данные задачи имеют вид А(а1,а2,а3)=(40;45;70); В(b1,b2,b3)=(48;30;29;40); 3 6 4 3 С= 2 3 1 3 6 5 1 4 Общий объем производства Sai=40+45+70=155 больше, чем требуется всем потребителям Sbj=48+30+29+40=147, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 155-147=8 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами. Первое базисное допустимое решение легко построить по правилу "северо-западного угла". Таблица 1
Обозначим через m(p1, p2,…, pm, q1, q2,…, qn) вектор симплексных множителей или потенциалов. Тогда Dij=mAij-cij , iÎNm, jÎNn, откуда следует Dij=pi+qj-cij , iÎNm, jÎNn Положим, что p1=0. Остальные потенциалы находим из условия, что для базисных клеток Dij=0. В данном случае получаем D11=0, p1+q1-c11=0, 0+q1-3=0, q1=3 D21=0, p2+q1-c21=0, p2+3-2=0, p2= -1 D23=0, p2+q3-c23=0, -1+q3-1=0, q3=2 аналогично, получим: q2=4, р3=-1, q4=5, q5=1. Затем вычисляем оценки всех свободных клеток: D12=p1+q2-c12=0+4-6= -2 D13=p1+q3-c13=0+2-4=-2 D14=2; D15=1; D24=1; D25=0; D31= -4; D32= -2 Находим наибольшую положительную оценку: mах(Dij >0)=2=D14, Для найденной свободной клетки 14 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 14-34-33-23-21-11. Производим перераспределение поставок вдоль цикла пересчета:
rmax=7 Получаем второе базисное допустимое решение: Таблица 2
Находим новые потенциалы. Новые оценки: D12= -2; D13= -4; D15= -1; D23= -2; D24= -1; D25= -2; D31= -2; D32=0. Поскольку все Dij£0 решение является оптимальным: 33 0 0 7 Xоpt1 = 15 30 0 0 0 0 29 33 Однако, так как оценка клетки D32=0, делаем вывод о наличие другого возможного оптимального решения. Для его нахождения строим цикл пересчета клетки 32: 32-22-21-11-14-34, производим перераспределение: Таблица 3
Находим новые потенциалы. Получаем рi и qj соответственно равные потенциалам первого базисного оптимального решения (см. табл. 2). Исходя из этого Dmax=D32, однако элемент с индексом 32 уже присутствует в базисе, поэтому пересчет не имеет смысла. Таким образом получаем второе и последнее базисное оптимальное решение: 3 0 0 37 Xоpt2 = 45 0 0 0 0 30 29 3 Оптимальное распределение инвестицийДанная задача с n переменными представляется, как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только по одной переменной. Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере ξ (сотен тыс. рублей) выражается функцией fi(xi). Приходим к задаче fl(xl)+f2(x2)+f3(x3)+f4(x4)àmax , где xi - пока еще неизвестный размер х1+х2+х3+х4≤7; х1,х2,х3.х4≥0 инвестиций i-й фирме. Эта задача решается методом динамического программирования: последовательно ищется оптимальное распределение для k=2,3 и 4 фирм. Пусть первым двум фирмам выделено ξ инвестиций. обозначим z2(ξ) величину инвестиций 2-й фирме, при которой сумма f2(z2j)+fl(ξ-z2j), 0≤j≤ ξ максимальна, саму эту максимальную величину обозначим F2(ξ). Далее действуем также: находим функции z3 и F3 и т.д. На k-ом шаге для нахождения Fk(ξ) используем основное рекуррентное соотношение: Fk(ξ)=max{fkj(хk)+F(k-1)( ξ-хk); 0 ≤ хk ≤ ξ
Таблица 1
Жирным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций по 2-м предприятиям.
Таблица 2
Жирным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций по 3-м предприятиям. |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Рефераты бесплатно, реферат бесплатно, курсовые работы, реферат, доклады, рефераты, рефераты скачать, рефераты на тему, сочинения, курсовые, дипломы, научные работы и многое другое. |
||
При использовании материалов - ссылка на сайт обязательна. |