Задача на динамическое программирование: Имеется фирма, производящая аппаратуру, которая собирается из нескольких блоков. Она обращается к 4 фирмам-поставщикам, чтобы заказать им изготовление 4 блоков. Одна фирма может выполнить только один заказ. Дана таблица, где для каждого номера заказа, каждый поставщик указал свою цену $%{c_{ij}}$%, по которой он готов поставить фирме различные блоки. Надо минимизировать общие затраты. (т.е. имеется таблица 4x4, где указаны цены) Помогите составить рекуррентное соотношение.

задан 22 Ноя '15 21:00

10|600 символов нужно символов осталось
0

Не знаю, по какой схеме полагается здесь решать, но я бы сделал так.

Введём величины $%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

изменен 23 Ноя '15 23:42

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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×76

задан
22 Ноя '15 21:00

показан
438 раз

обновлен
24 Ноя '15 11:24

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru