|
Задача на динамическое программирование: Имеется фирма, производящая аппаратуру, которая собирается из нескольких блоков. Она обращается к 4 фирмам-поставщикам, чтобы заказать им изготовление 4 блоков. Одна фирма может выполнить только один заказ. Дана таблица, где для каждого номера заказа, каждый поставщик указал свою цену $%{c_{ij}}$%, по которой он готов поставить фирме различные блоки. Надо минимизировать общие затраты. (т.е. имеется таблица 4x4, где указаны цены) Помогите составить рекуррентное соотношение. задан 22 Ноя '15 21:00 
Яська |
|
Не знаю, по какой схеме полагается здесь решать, но я бы сделал так. Введём величины $%x_i$% (4 штуки), $%x_{ij}$% (6 штук, для $%i < j$%), $%x_{ijk}$% (4 штуки, для $%i < j < k$%), и $%x_{1234}=x$%. Смысл величин: $%x_i=c_{i1}$% -- стоимость покупки 1-го блока у $%i$%-й фирмы. Число $%x_{ij}$% означает минимальную стоимость заказа 1-го и 2-го блока у $%i$%-й и $%j$%-й фирм в том или ином порядке. Рекуррентная формула: $%x_{ij}=\min(x_i+c_{j2},x_j+c_{i2})$%. Число $%x_{ijk}$% означает минимальную стоимость заказа 1-го, 2-го и 3-го блока у $%i$%-й, $%j$%-й и $%k$%-й фирм в каком-либо порядке. Рекуррентная формула: $%x_{ijk}=\min(x_{ij}+c_{k3},x_{ik}+c_{j3},x_{jk}+c_{i3})$%. Наконец, $%x$% есть минимальная стоимость всего заказа. Формула: $%x=\min(x_{123}+c_{44},x_{124}+c_{34},x_{134}+c_{24},x_{234}+c_{14})$%. отвечен 23 Ноя '15 0:24 
falcao 1
@falcao, а у Вас ничего не перепутано для рекуррентной формулы xij? может там сi1?
(23 Ноя '15 23:28)
Яська
@Яська: да, перепутано, только там $%c_{i2}$% должно быть. Сейчас подправлю.
(23 Ноя '15 23:42)
falcao
@falcao, получается, что для первой итерации,когда находим xij надо рассмотреть для каждой фирмы минимум, то есть смотреть минимум из: первая фирма делает первую деталь, а вторая вторую, потом первая фирма делает первую деталь, а третья фирма вторую и тд, но это же будет таких значений аж 12 штук, и это уже на первой итерации
(24 Ноя '15 0:17)
Яська
@Яська: нет, здесь всё просто. Сначала мы просто находим четыре числа по "прайс-листу" и записываем их. Потом надо найти 6 значений переменных x_{ij}. Это делается пошагово, и каждый раз сравниваются только две суммы. Результаты запоминаем, и получаем 6 новых чисел. Вычисление каждого из них -- дело совсем простое, оно фактически устное, с записью на листочке. Потом ещё четыре числа, и в конце ответ. Я делал это вручную на матрицах 4x4, и это просто. А "волшебных" способов тут нет.
(24 Ноя '15 1:01)
falcao
@falcao, не понятно почему 6 значений, из прайс-листа берем 4 значения, а теперь к каждому из них надо добавить три числа, и в итоге будет 12 значений...мне не ясно почему у Вас 6.
(24 Ноя '15 9:13)
Яська
@Яська: переменных вида x_{ij} будет ровно 6, по числу сочетаний из 4 по 2. Это временные величины; из смысл -- минимизация закупок 1-го и 2-го блока (у i-й и j-й фирм). Может быть, мне сделать добавление с разбором какого-нибудь примера для случайно сгенерированной числовой матрицы?
(24 Ноя '15 11:24)
falcao
показано 5 из 6
показать еще 1
|