26. Мат постановка обобщенной тз. Критерии оптимальности.

Математическая модель распределительной ТЗ

Здесь:i -индекс ресурсов, j-индекс производимой продукции, ai - ресурсы с номером i ,bj - потребность с номером j .хij - объем работы j производимой с помощью ресурсов i. kij - производительность ресурсов при выполнении работы j .cij - себестоимость при выполнении работы с привлечением ресурсов i.

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

27. Решение распределит задачи методом разрешающих множителей. Л.В. Канторовича Алгоритм метода разрешающих множителей состоит из двух этапов. На первом необходимо построить первоначальное распределение. На втором этапе осуществляется построение оптимального плана методом разрешающих множителей Л.В.Канторовича. Шаг 1. Построение первоначального плана. В каждом столбце отыскивается максимальное значение показателя производительности ресурса относительно выпуска данного вида продукции. В соответствующую клетку заносится максимальный объем потребности данного столбца, невзирая на затраты необходимого объема ресурсов, и так далее до распределения всех потребностей. Шаг 2. Находятся небалансы Шаг 3. Проверка решения на оптимальность. Для задач должно выполняться условие: все небалансы должны иметь один знак или равны нулю. Если условие оптимальности не выполняется, переход к шагу 4; иначе получен оптимальный и допустимый план. Шаг 4. Расчет разрешающих множителей Шаг 5. Корректировка показателей производительности ресурсов. Шаг 6.Построение контура перераспределения базиса задачи. переход к шагу 3.

Ресурсы	1600	1300	600	400	1200	Небаланс
60	25	30	30	30	20	60-14=+46
				400 14
40	30	40	35	20	30	40-104=-64
	1600 54	1300 33	600 17
70	20	25	28	25	40	70-30=+40
					1200 30
	30/25=1,2	40/30=1,33	35/30=1,17	-	-

28. Решение распределй тз модиф методом потенциалов.

Здесь:i -индекс ресурсов, j-индекс производимой продукции, ai - ресурсы с номером i ,bj - потребность с номером j .хij - объем работы j производимой с помощью ресурсов i. kij - производительность ресурсов при выполнении работы j .cij - себестоимость(расходы) при выполнении работы с привлечением ресурсов i.

Алгоритм модифицированного метода потенциалов состоит из двух этапов. На первом этапе осуществляется построение допустимого плана.

Шаг 1. Построение базиса выполняется с учетом минимальной стоимости ресурса и максимальной производительности его использования. Для этого в каждом столбце отыскивается клета с max показателем производительности (kij) и min стоимости (сij).

Шаг 2. Выполняется расстановка потенциалов по базисным элеметам матрицы по формулам: Vj=(Ui+Cij)\Kij, Ui=Vj*Kij-Cij

Расстановка потенциалов начинается с одной из строк, имеющей резерв неиспользованных ресурсов. Такой строке присваивается потенциал, равный нулю. Шаг 3. Выполняется проверка решения на оптимальность. Должны выполняться условия: Vi*Kij-Ui<=Cij

Если условия не выполняется, переход к шагу 4; иначе получен оптимальный и допустимый план. Шаг 4. Построение нового базиса. Отыскивается внебазисная клетка с наибольшим нарушением условия оптимальности относительно которой строится контур перераспределения элементов базиса. Существует два типа контуров. Первый - замкнутого вида,. Другой контур - открытого типа , включает в себя два элемента n+1 столбца с резервами ресурсов. После построения нового базиса с учетом расчетов по найденному контуру - переход к шагу 2.