Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 189477
23.05.2016, 12:04
0.00 руб.
0 16 1
Образование
Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Можете нарисовать и объяснить циклы в данной решенной задаче:


Можно от руки.....

Обсуждение

давно
Посетитель - 399158
Посетитель
399158
228
24.05.2016, 23:20
общий
неужели никто не может помочь?
давно
Посетитель - 399158
Посетитель
399158
228
27.05.2016, 15:06
общий
люди...
давно
Коцюрбенко Алексей Владимирович
Старший Модератор
312929
1973
27.05.2016, 19:27
общий
это ответ
Здравствуйте, Посетитель - 399158!

Рассмотрим на примере первого шага метода потенциалов. Пусть имеется опорное решение
[table]
[row][col][/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]B5[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col lime]4*80[/col][col]7[/col][col]8[/col][col]1[/col][col]200[/col][/row]
[row][col]A2[/col][col]2[/col][col lime]3*50[/col][col lime]1*100[/col][col]4[/col][col]1[/col][col]150[/col][/row]
[row][col]A3[/col][col]5[/col][col]1[/col][col lime]3*35[/col][col]2[/col][col]3[/col][col]35[/col][/row]
[row][col]A4[/col][col]0[/col][col]0[/col][col lime]0*65[/col][col lime]0*180[/col][col lime]0*110[/col][col]355[/col][/row]
[row][col]Потребность[/col][col]120[/col][col]130[/col][col]200[/col][col]180[/col][col]110[/col][col]740[/col][/row]
[/table]
для которого уже вычислены потенциалы и оценки поставок. Если есть ячейки с отрицательной оценкой, выбираем одну из них. В данном случае выбрана ячейка A[sub]1[/sub]B[sub]5[/sub] с отрицательной оценкой -1:
[table]
[row][col][/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]B5[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col lime]4*80[/col][col]7[/col][col]8[/col][col silver]1[/col][col]200[/col][/row]
[row][col]A2[/col][col]2[/col][col lime]3*50[/col][col lime]1*100[/col][col]4[/col][col]1[/col][col]150[/col][/row]
[row][col]A3[/col][col]5[/col][col]1[/col][col lime]3*35[/col][col]2[/col][col]3[/col][col]35[/col][/row]
[row][col]A4[/col][col]0[/col][col]0[/col][col lime]0*65[/col][col lime]0*180[/col][col lime]0*110[/col][col]355[/col][/row]
[row][col]Потребность[/col][col]120[/col][col]130[/col][col]200[/col][col]180[/col][col]110[/col][col]740[/col][/row]
[/table]
Теперь строим замкнутый цикл, начинающийся и заканчивающийся в выбранной ячейке. В нём горизонтальные отрезки (содержащие две ячейки одной строки) будут чередоваться с вертикальными (содержащими две ячейки одного столбца), причём все ячейки, кроме выбранной, должны входить в текущее решение. При построении цикла входящие в него ячейки отмечаем по очереди как "положительные" и "отрицательные" (выбранная для начала цикла ячейка всегда "положительная").
В данном случае цикл начинается с "положительной" ячейки A[sub]1[/sub]B[sub]5[/sub]. Добавляем в цикл ячейку A[sub]4[/sub]B[sub]5[/sub] (в столбце B[sub]5[/sub] нет других ячеек из опорного решения) и отмечаем её как "отрицательную":
[table]
[row][col][/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]B5[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col lime]4*80[/col][col]7[/col][col]8[/col][col silver]1[/col][col]200[/col][/row]
[row][col]A2[/col][col]2[/col][col lime]3*50[/col][col lime]1*100[/col][col]4[/col][col]1[/col][col]150[/col][/row]
[row][col]A3[/col][col]5[/col][col]1[/col][col lime]3*35[/col][col]2[/col][col]3[/col][col]35[/col][/row]
[row][col]A4[/col][col]0[/col][col]0[/col][col lime]0*65[/col][col lime]0*180[/col][col grey]0*110[/col][col]355[/col][/row]
[row][col]Потребность[/col][col]120[/col][col]130[/col][col]200[/col][col]180[/col][col]110[/col][col]740[/col][/row]
[/table]
Следующей добавляем "положительную" ячейку A[sub]4[/sub]B[sub]3[/sub] (ячейка A[sub]4[/sub]B[sub]4[/sub] не подойдёт, потому что из неё нельзя будет продолжить цикл в вертикальном направлении - в столбце B[sub]4[/sub] нет других ячеек из опорного решения, а в столбце B[sub]3[/sub] - есть):
[table]
[row][col][/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]B5[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col lime]4*80[/col][col]7[/col][col]8[/col][col silver]1[/col][col]200[/col][/row]
[row][col]A2[/col][col]2[/col][col lime]3*50[/col][col lime]1*100[/col][col]4[/col][col]1[/col][col]150[/col][/row]
[row][col]A3[/col][col]5[/col][col]1[/col][col lime]3*35[/col][col]2[/col][col]3[/col][col]35[/col][/row]
[row][col]A4[/col][col]0[/col][col]0[/col][col silver]0*65[/col][col lime]0*180[/col][col grey]0*110[/col][col]355[/col][/row]
[row][col]Потребность[/col][col]120[/col][col]130[/col][col]200[/col][col]180[/col][col]110[/col][col]740[/col][/row]
[/table]
Аналогичным образом добавляем в цикл "отрицательную" ячейку A[sub]2[/sub]B[sub]3[/sub] из столбца A[sub]2[/sub]B[sub]3[/sub] (A[sub]3[/sub]B[sub]3[/sub] не подойдёт - в строке A[sub]3[/sub] нет других ячеек из опорного решения):
[table]
[row][col][/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]B5[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col lime]4*80[/col][col]7[/col][col]8[/col][col silver]1[/col][col]200[/col][/row]
[row][col]A2[/col][col]2[/col][col lime]3*50[/col][col gray]1*100[/col][col]4[/col][col]1[/col][col]150[/col][/row]
[row][col]A3[/col][col]5[/col][col]1[/col][col lime]3*35[/col][col]2[/col][col]3[/col][col]35[/col][/row]
[row][col]A4[/col][col]0[/col][col]0[/col][col silver]0*65[/col][col lime]0*180[/col][col grey]0*110[/col][col]355[/col][/row]
[row][col]Потребность[/col][col]120[/col][col]130[/col][col]200[/col][col]180[/col][col]110[/col][col]740[/col][/row]
[/table]
Затем добавляем "положительную" ячейку A[sub]2[/sub]B[sub]2[/sub] и "отрицательную" ячейку A[sub]1[/sub]B[sub]2[/sub] (в обоих случаях это единственно возможный выбор). На этом цикл замыкается:
[table]
[row][col][/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]B5[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col gray]4*80[/col][col]7[/col][col]8[/col][col silver]1[/col][col]200[/col][/row]
[row][col]A2[/col][col]2[/col][col silver]3*50[/col][col gray]1*100[/col][col]4[/col][col]1[/col][col]150[/col][/row]
[row][col]A3[/col][col]5[/col][col]1[/col][col lime]3*35[/col][col]2[/col][col]3[/col][col]35[/col][/row]
[row][col]A4[/col][col]0[/col][col]0[/col][col silver]0*65[/col][col lime]0*180[/col][col grey]0*110[/col][col]355[/col][/row]
[row][col]Потребность[/col][col]120[/col][col]130[/col][col]200[/col][col]180[/col][col]110[/col][col]740[/col][/row]
[/table]
Таким образом, получаем следующий цикл: A[sub]1[/sub]B[sub]5[/sub](+) [$8594$] A[sub]4[/sub]B[sub]5[/sub](-) [$8594$] A[sub]4[/sub]B[sub]3[/sub](+) [$8594$] A[sub]2[/sub]B[sub]3[/sub](-) [$8594$] A[sub]2[/sub]B[sub]2[/sub](+) [$8594$] A[sub]1[/sub]B[sub]2[/sub](-) [$8594$] A[sub]1[/sub]B[sub]5[/sub](+). Теперь изменяем поставки для всех ячеек цикла на одну и ту же величину (для "положительных" увеличиваем, для "отрицательных" - уменьшаем). Так как объём поставок не может стать отрицательным, то максимально возможная величина изменения равна минимуму по всем значениям для "отрицательных" ячеек цикла. В данном случае их три - A[sub]4[/sub]B[sub]5[/sub], A[sub]2[/sub]B[sub]3[/sub] и A[sub]1[/sub]B[sub]2[/sub] с поставками 110, 100 и 80. Минимальная из них - 80, поэтому для ячеек A[sub]4[/sub]B[sub]5[/sub], A[sub]2[/sub]B[sub]3[/sub] и A[sub]1[/sub]B[sub]2[/sub] уменьшаем поставку на 80, а для ячеек A[sub]1[/sub]B[sub]5[/sub], A[sub]4[/sub]B[sub]3[/sub] и A[sub]2[/sub]B[sub]2[/sub] - увеличиваем на 80:
[table]
[row][col][/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]B5[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]4[/col][col]7[/col][col]8[/col][col lime]1*80[/col][col]200[/col][/row]
[row][col]A2[/col][col]2[/col][col lime]3*130[/col][col lime]1*20[/col][col]4[/col][col]1[/col][col]150[/col][/row]
[row][col]A3[/col][col]5[/col][col]1[/col][col lime]3*35[/col][col]2[/col][col]3[/col][col]35[/col][/row]
[row][col]A4[/col][col]0[/col][col]0[/col][col lime]0*145[/col][col lime]0*180[/col][col lime]0*30[/col][col]355[/col][/row]
[row][col]Потребность[/col][col]120[/col][col]130[/col][col]200[/col][col]180[/col][col]110[/col][col]740[/col][/row]
[/table]
В результате ячейка A[sub]1[/sub]B[sub]2[/sub], для которой объём поставок стал равен 0, исключается из решения, а ячейка A[sub]1[/sub]B[sub]5[/sub] - добавляется к нему.
Для остальных шагов циклы строятся аналогично (там они проще - всего четыре ячейки).
5
Все понятно объяснили. Спасибо.
давно
Посетитель - 399158
Посетитель
399158
228
27.05.2016, 19:35
общий
это так циклы помечаются?
давно
Коцюрбенко Алексей Владимирович
Старший Модератор
312929
1973
28.05.2016, 06:51
общий
Адресаты:
У меня ячейки, входящие в текущее решение, помечены зелёным, а те из них, что образуют цикл - серым ("положительные" - светло-серым, а "отрицательные" - тёмно-серым). Можно помечать как угодно (цветом или специальными значками), главное, чтобы ячейки цикла отличались от остальных, а "положительные" ячейки цикла - от "отрицательных".
давно
Посетитель - 399158
Посетитель
399158
228
30.05.2016, 13:28
общий
а можете для всех шагов показать это?
давно
Посетитель - 399158
Посетитель
399158
228
30.05.2016, 13:55
общий
помогите со вторым шагом. на 3 шаге будет следующий цикл: A4B3(-) → A4B2(+) → A2B2(-) → A2B3(-) → A2B3(+) так?
давно
Посетитель - 399158
Посетитель
399158
228
30.05.2016, 13:58
общий
на 2 шаге: A3B2(+) → A2B2(-) → A2B3(+) → A3B3(-) так?
давно
Коцюрбенко Алексей Владимирович
Старший Модератор
312929
1973
30.05.2016, 17:46
общий
Адресаты:
Цитата: Посетитель - 399158
на 2 шаге: A3B2(+) → A2B2(-) → A2B3(+) → A3B3(-) так?

Совершенно верно.
давно
Коцюрбенко Алексей Владимирович
Старший Модератор
312929
1973
30.05.2016, 17:50
общий
Адресаты:
Цитата: Посетитель - 399158
помогите со вторым шагом. на 3 шаге будет следующий цикл: A4B3(-) → A4B2(+) → A2B2(-) → A2B3(-) → A2B3(+) так?

Не совсем, правильно будет A4B2(+) → A2B2(-) → A2B3(+) → A4B3(-). Здесь общий принцип такой: "плюсы" и "минусы" всегда чередуются, у выбранной ячейки, с которой начинается обход цикла, всегда "плюс".
давно
Посетитель - 399158
Посетитель
399158
228
30.05.2016, 23:10
общий
Понял. последний вопрос, по поводу 3 шага, мы же могли тогда с A2B3 начать... и по часовой или нет? почему именно с A4B2 начали?
давно
Коцюрбенко Алексей Владимирович
Старший Модератор
312929
1973
31.05.2016, 05:30
общий
Адресаты:
Цитата: Посетитель - 399158
Понял. последний вопрос, по поводу 3 шага, мы же могли тогда с A2B3 начать... и по часовой или нет? почему именно с A4B2 начали?

Начинаем всегда с выбранной ячейки (которая НЕ принадлежит текущему решению и имеет отрицательную оценку) - в данном случае это именно A4B2 с оценкой -2. А направление можно выбрать любое, то есть вариант A4B2(+) → A4B3(-) → A2B3(+) → A2B2(-) тоже правильный.
давно
Посетитель - 399158
Посетитель
399158
228
31.05.2016, 07:56
общий
Я вас понял. Спасибо большое за объяснение.
давно
Посетитель - 399158
Посетитель
399158
228
12.06.2016, 12:59
общий
12.06.2016, 13:01
У меня вопрос, вот я начал решать задачу и дошел до этого шага, дальше не знаю как, можете объяснить, что делать далее?
давно
Посетитель - 399158
Посетитель
399158
228
12.06.2016, 21:06
общий
можете помочь?
давно
Коцюрбенко Алексей Владимирович
Старший Модератор
312929
1973
13.06.2016, 01:19
общий
Адресаты:
Задайте отдельный вопрос в этом же разделе.
Форма ответа