20.11.2019, 14:29 [+3 UTC]
в нашей команде: 3 984 чел. | участники онлайн: 10 (рекорд: 21)

:: РЕГИСТРАЦИЯ

задать вопрос

все разделы

правила

новости

участники

доска почёта

форум

блоги

поиск

статистика

наш журнал

наши встречи

наша галерея

отзывы о нас

поддержка

руководство

Версия системы:
7.78 (18.11.2019)
JS-v.1.34 | CSS-v.3.35

Общие новости:
28.04.2019, 09:13

Форум:
16.11.2019, 20:23

Последний вопрос:
20.11.2019, 12:41
Всего: 151019

Последний ответ:
20.11.2019, 13:20
Всего: 259433

Последняя рассылка:
20.11.2019, 11:45

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
29.09.2010, 03:34 »
Kardashevskij Anatolij Mikhajlovich
Большущее спасибо я еще попытаюсь разобраться так сказать переварить. С этим у меня туго. Но я надеюсь на дальнейшее сотрудничество хотя это нельзя назвать сотрудничеством так как IQ у вас на 2 порядка выше. [вопрос № 180068, ответ № 263229]
07.06.2013, 14:43 »
Александр Сергеевич
Спасибо!!! [вопрос № 187447, ответ № 272400]

РАЗДЕЛ • Исследование операций

Консультации и решение задач по исследованию операций, линейному, динамическому программированию, теории игр и сетевому планированию.

[администратор рассылки: Коцюрбенко Алексей Владимирович (Модератор)]

Лучшие эксперты в этом разделе

Коцюрбенко Алексей Владимирович
Статус: Модератор
Рейтинг: 1375
solowey
Статус: Бакалавр
Рейтинг: 215
Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 153

Перейти к консультации №:
 

Консультация онлайн # 188421
Автор вопроса: Посетитель - 399202 (1-й класс)
Отправлена: 13.12.2015, 19:58
Поступило ответов: 1

Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Еще 1 страшная задачка.....вроде последняя....помогите пожалуйста! smile

Последнее редактирование 13.12.2015, 20:02 Гордиенко Андрей Владимирович (Профессионал)

Состояние: Консультация закрыта

Здравствуйте, Посетитель - 399202!

1. Метод северо-западного угла состоит в следующем:
перебираем ячейки таблицы, начиная с левой верхней ("северо-западной");
для очередной ячейки определяем максимально возможную отгрузку как минимум из величины потребности соответствующего потребителя и запаса соответствующего поставщика;
уменьшаем потребность и запас на величину отгрузки;
если потребность стала равна нулю, то исключаем соответствующий столбец (потребителя) из дальнейшего рассмотрения;
аналогично, если запас стал равен нулю, то исключаем соответствующую строку (поставщика);
повторяем для оставшейся части таблицы, пока не дойдём до правой нижней ячейки.

В данном случае исходная таблица имеет вид:

ПоставщикиB1B2B3B4Запас
A1120
A2140
A3230
A4200
Потребность160180200150690

(стоимости перевозки не указываем, так как при построении опорного плана они не учитываются). Начинаем с левой верхней ячейки (строка A1, столбец B1). Потребность равна 160, запас равен 120, поэтому отгрузка равна min(160,120)=120. Потребность потребителя B1 стала равна 40 (160-120), запас поставщика A1 стал равен 0 (120-120), поэтому исключаем из дальнейшего рассмотрения первую строку (соответствующую поставщику A1):
ПоставщикиB1B2B3B4Запас
A11200
A2140
A3230
A4200
Потребность40180200150570

В оставшейся части таблицы левая верхняя ячейка находится на пересечении строки A2 (запас 140) и столбца B1 (потребность 40). Отгрузка равна min(40,140)=40, оставшаяся потребность B1 равна 0, оставшийся запас A2 равен 100, исключаем столбец B1:
ПоставщикиB1B2B3B4Запас
A11200
A240100
A3230
A4200
Потребность0180200150530

Ячейка A2:B2, отгрузка min(180,100)=100, исключаем строку A2:
ПоставщикиB1B2B3B4Запас
A11200
A2401000
A3230
A4200
Потребность080200150430

Ячейка A3:B2, отгрузка min(80,230)=80, исключаем столбец B2:
ПоставщикиB1B2B3B4Запас
A11200
A2401000
A380150
A4200
Потребность00200150350

Ячейка A3:B3, отгрузка min(200,150)=150, исключаем строку A3:
ПоставщикиB1B2B3B4Запас
A11200
A2401000
A3801500
A4200
Потребность0050150200

Ячейка A4:B3, отгрузка min(50,200)=50, исключаем столбец B3:
ПоставщикиB1B2B3B4Запас
A11200
A2401000
A3801500
A450150
Потребность000150150

Ячейка A4:B4, отгрузка min(150,150)=150, исключаем строку A4 и столбец B4:
ПоставщикиB1B2B3B4Запас
A11200
A2401000
A3801500
A4501500
Потребность00000

Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Добавим в таблицу значения стоимости перевозок:
ПоставщикиB1B2B3B4Запас
A12*1200
A21*404*1000
A32*804*1500
A42*501*1500
Потребность0000

и вычислим общую стоимость перевозок:
2·120 + 1·40 + 4·100 + 2·80 + 4·150 + 2·50 + 1·150 = 1690.

2. Метод двойного предпочтения состоит в следующем:
в каждом столбце и в каждой строке отмечаем ячейку с наименьшей стоимостью перевозки (очевидно, что некоторые ячейки могут быть отмечены дважды, если они минимальны по стоимости, как в строке, так и в столбце);
выбираем ячейку таблицы с наибольшим числом отметок и наименьшей стоимостью перевозки (если таких несколько, выбираем любую);
определяем максимально возможную отгрузку как минимум из величины потребности соответствующего потребителя и запаса соответствующего поставщика;
уменьшаем потребность и запас на величину отгрузки;
если потребность стала равна нулю, то исключаем соответствующий столбец (потребителя) из дальнейшего рассмотрения;
аналогично, если запас стал равен нулю, то исключаем соответствующую строку (поставщика);
повторяем для оставшейся части таблицы, пока не будут распределены все запасы и удовлетворены все потребности.
В данном случае исходная таблица имеет вид:
ПоставщикиB1B2B3B4Запас
A12132120
A21412140
A31245230
A43421200
Потребность160180200150690

Отметим ячейки c наименьшей в строке стоимостью перевозки:
ПоставщикиB1B2B3B4Запас
A121*32120
A21*41*2140
A31*245230
A43421*200
Потребность160180200150690

Отметим ячейки c наименьшей в столбце стоимостью перевозки:
ПоставщикиB1B2B3B4Запас
A121**32120
A21**41**2140
A31**245230
A43421**200
Потребность160180200150690

Получилось пять отмеченных ячеек, причём все отмечены дважды и имеют одну и ту же стоимость перевозки (1).
ПоставщикиB1B2B3B4Запас
A121**32120
A21**41**2140
A31**245230
A43421**200
Потребность160180200150690

Выберем одну из отмеченных ячеек, например, A1:B2. Потребность равна 180, запас равен 120, поэтому отгрузка будет равна min(180,120)=120. Потребность потребителя B2 стала равна 60 (180-120), запас поставщика A1 стал равен 0 (120-120), поэтому исключаем из дальнейшего рассмотрения первую строку (соответствующую поставщику A1):
ПоставщикиB1B2B3B4Запас
A121*120320
A21**41**2140
A31**245230
A43421**200
Потребность16060200150570

В оставшейся части таблицы снова выберем одну из отмеченных ячеек, например, A2:B1. Потребность равна 160, запас равен 140, поэтому отгрузка будет равна min(160,140)=140. Потребность потребителя B1 стала равна 20 (160-140), запас поставщика A2 стал равен 0 (140-140), поэтому исключаем из дальнейшего рассмотрения вторую строку (соответствующую поставщику A2):
ПоставщикиB1B2B3B4Запас
A121*120320
A21*14041**20
A31**245230
A43421**200
Потребность2060200150430

Дважды отмеченная ячейка A3:B1, отгрузка min(20,230)=20, исключаем столбец B1:
ПоставщикиB1B2B3B4Запас
A121*120320
A21*14041**20
A31*20245210
A43421**200
Потребность060200150410

Дважды отмеченная ячейка A4:B4, отгрузка min(150,200)=150, исключаем столбец B4:
ПоставщикиB1B2B3B4Запас
A121*120320
A21*14041**20
A31*20245210
A43421*15050
Потребность0602000260

В оставшейся части таблицы больше нет отмеченных ячеек, поэтому выбираем среди неотмеченных ячейку с наименьшей стоимостью, например, A3:B2. Отгрузка равна min(60,210)=60, исключаем столбец B2:
ПоставщикиB1B2B3B4Запас
A121*120320
A21*14041**20
A31*202*6045150
A43421*15050
Потребность002000200

Ячейка A4:B3, отгрузка min(200,50)=50, исключаем строку A4:
ПоставщикиB1B2B3B4Запас
A121*120320
A21*14041**20
A31*202*6045150
A4342*501*1500
Потребность001500150

Ячейка A3:B3, отгрузка min(150,150)=150, исключаем строку A3 и столбец B3:
ПоставщикиB1B2B3B4Запас
A121*120320
A21*14041**20
A31*202*604*15050
A4342*501*1500
Потребность00000

Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Вычислим общую стоимость перевозок:
1·120 + 1·140 + 1·20 + 2·60 + 4·150 + 2·50 + 1·150 = 1250.

3. Метод наименьших стоимостей состоит в следующем:
выбираем ячейку таблицы с наименьшей стоимостью перевозки (если таких несколько, выбираем любую);
определяем максимально возможную отгрузку как минимум из величины потребности соответствующего потребителя и запаса соответствующего поставщика;
уменьшаем потребность и запас на величину отгрузки;
если потребность стала равна нулю, то исключаем соответствующий столбец (потребителя) из дальнейшего рассмотрения;
аналогично, если запас стал равен нулю, то исключаем соответствующую строку (поставщика);
повторяем для оставшейся части таблицы, пока не будут распределены все запасы и удовлетворены все потребности.

В данном случае исходная таблица имеет вид:
ПоставщикиB1B2B3B4Запас
A12132120
A21412140
A31245230
A43421200
Потребность160180200150690

Наименьшая стоимость перевозки в таблице равна 1. Выберем одну из клеток с данной стоимостью, например, A1:B2. Потребность равна 180, запас равен 120, поэтому отгрузка будет равна min(180,120)=120. Потребность потребителя B2 стала равна 60 (180-120), запас поставщика A1 стал равен 0 (120-120), поэтому исключаем из дальнейшего рассмотрения первую строку (соответствующую поставщику A1):
ПоставщикиB1B2B3B4Запас
A121*120320
A21412140
A31245230
A43421200
Потребность16060200150570

В оставшейся части таблицы наименьшая стоимость перевозки равна 1. Выберем одну из клеток с данной стоимостью, например, A2:B1. Потребность равна 160, запас равен 140, поэтому отгрузка будет равна min(160,140)=140. Потребность потребителя B1 стала равна 20 (160-140), запас поставщика A2 стал равен 0 (140-140), поэтому исключаем из дальнейшего рассмотрения вторую строку (соответствующую поставщику A2):
ПоставщикиB1B2B3B4Запас
A121*120320
A21*1404120
A31245230
A43421200
Потребность2060200150430

Наименьшая стоимость 1, ячейка A3:B1, отгрузка min(20,230)=20, исключаем столбец B1:
ПоставщикиB1B2B3B4Запас
A121*120320
A21*1404120
A31*20245210
A43421200
Потребность060200150410

Наименьшая стоимость 1, ячейка A4:B4, отгрузка min(150,200)=150, исключаем столбец B4:
ПоставщикиB1B2B3B4Запас
A121*120320
A21*1404120
A31*20245210
A43421*15050
Потребность0602000260

Наименьшая стоимость 2, ячейка A3:B2, отгрузка min(60,210)=60, исключаем столбец B2:
ПоставщикиB1B2B3B4Запас
A121*120320
A21*1404120
A31*202*6045150
A43421*15050
Потребность002000200

Наименьшая стоимость 2, ячейка A4:B3, отгрузка min(200,50)=50, исключаем строку A4:
ПоставщикиB1B2B3B4Запас
A121*120320
A21*1404120
A31*202*6045150
A4342*501*1500
Потребность001500150

Наименьшая стоимость 4, ячейка A3:B3, отгрузка min(150,150)=150, исключаем столбец B3 и строку A3:
ПоставщикиB1B2B3B4Запас
A121*120320
A21*1404120
A31*202*604*15050
A4342*501*1500
Потребность00000

Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Вычислим общую стоимость перевозок:
1·120 + 1·140 + 1·20 + 2·60 + 4·150 + 2·50 + 1·150 = 1250.
Данное опорное решение совпадает с полученным методом двойного предпочтения.

4. Метод потенциалов используется для оптимизации уже имеющегося опорного решения. Он выглядит следующим образом:
всем поставщикам Ai и потребителям Bj ставим в соответствие некоторые значения ui и vj, называемые потенциалами. Один из потенциалов задаём (например, ui=0), остальные определяем исходя из того, что для стоимости cij поставки, входящей в опорное решение, должно выполняться равенство cij=ui+vj;
находим для всех поставок оценки по формуле Δij=cij-(ui+vj). Для поставок, входящих в опорное решение, они будут нулевые, для остальных могут отличаться от нуля;
если нет отрицательных оценок, то текущее решение является оптимальным, и оптимизация заканчивается;
в противном случае выбираем ячейку с наименьшей оценкой (то есть с максимальной по абсолютной величине отрицательной оценкой;
начиная с выбранной ячейки, строим в таблице замкнутый цикл, содержащий ячейки опорного решения;
обходим ячейки цикла в произвольном порядке, помечая их по очереди как "положительные" и "отрицательные" (выбранная ячейка с наименьшей оценкой помечается как "положительная");
находим минимальное значение величины поставки для всех "отрицательных" ячеек;
уменьшаем на эту величину объёмы поставок для всех "отрицательных" ячеек цикла и увеличиваем - для всех "положительных";
получаем новое опорное решение, для которого повторяем всё сначала.

Воспользуемся методом потенциалов для оптимизации решения, полученного методом северо-западного угла:
ПоставщикиB1B2B3B4Запас
A12*120132120
A21*404*10012140
A312*804*1505230
A4342*501*150200
Потребность160180200150690

Вычислим потенциалы:
u1=0;
c11=u1+v1=2v1=2-0=2;
c21=u2+v1=1u2=1-2=-1;
c22=u2+v2=4v2=4-(-1)=5;
c32=u3+v2=2u3=2-5=-3;
c33=u3+v3=4v3=4-(-3)=7;
c43=u4+v3=2u4=2-7=-5;
c44=u4+v4=1v4=1-(-5)=6.
и добавим их в таблицу:
ПоставщикиB1B2B3B4ЗапасU
A12*1201321200
A21*404*10012140-1
A312*804*1505230-3
A4342*501*150200-5
Потребность160180200150690
V2576

Найдём оценки поставок:
Δ11=0;
Δ12=c12-(u1+v2)=1-(0+5)=-4;
Δ13=c13-(u1+v3)=3-(0+7)=-4;
Δ14=c14-(u1+v4)=2-(0+6)=-4;
Δ2122=0;
Δ23=c23-(u2+v3)=1-(-1+7)=-5;
Δ24=c24-(u2+v4)=2-(-1+6)=-3;
Δ31=c31-(u3+v1)=1-(-3+2)=2;
Δ3233=0;
Δ34=c34-(u3+v4)=5-(-3+6)=2;
Δ41=c41-(u4+v1)=3-(-5+2)=6;
Δ42=c42-(u4+v2)=4-(-5+5)=4;
Δ4344=0;
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
ПоставщикиB1B2B3B4Запас
A12*1201/-43/-42/-4120
A21*404*1001/-52/-3140
A31/22*804*1505/2230
A43/64/42*501*150200
Потребность160180200150690

Ячейка A2:B3 содержит наименьшую оценку (-5). Вместе с ячейками A3:B3, A3:B2 и A2:B2 она образует замкнутый цикл, в котором ячейки A2:B3 и A3:B2 - "положительные", а A3:B3 и A2:B2 - "отрицательные":
ПоставщикиB1B2B3B4Запас
A12*1201/-43/-42/-4120
A21*404*1001/-52/-3140
A31/22*804*1505/2230
A43/64/42*501*150200
Потребность160180200150690

Среди "отрицательных" ячеек наименьшее значение поставки достигается в A2:B2 (100). Уменьшаем на 100 объём поставок для ячеек A3:B3 и A2:B2, увеличиваем на 100 объём поставок для ячеек A2:B3 и A3:B2. Получаем новое опорное решение:
ПоставщикиB1B2B3B4Запас
A12*120132120
A21*4041*1002140
A312*1804*505230
A4342*501*150200
Потребность160180200150690

и вычисляем новую стоимость перевозок:
2·120 + 1·40 + 1·100 + 2·180 + 4·50 + 2·50 + 1·150 = 1190.
Можно заметить, что по сравнению с исходным опорным решением стоимость изменилась на величину -500 = -5·100, равную произведению оценки выбранной ячейки (-5) на величину изменения объёмов поставок для ячеек цикла (100).
Вычислим потенциалы:
u1=0;
c11=u1+v1=2v1=2-0=2;
c21=u2+v1=1u2=1-2=-1;
c23=u2+v3=1v3=1-(-1)=2;
c33=u3+v3=4u3=4-2=2;
c32=u3+v2=2v2=2-2=0;
c43=u4+v3=2u4=2-2=0;
c44=u4+v4=1v4=1-0=1.
и добавим их в таблицу:
ПоставщикиB1B2B3B4ЗапасU
A12*1201321200
A21*4041*1002140-1
A312*1804*5052302
A4342*501*1502000
Потребность160180200150690
V2021

Найдём оценки поставок:
Δ11=0;
Δ12=c12-(u1+v2)=1-(0+0)=1;
Δ13=c13-(u1+v3)=3-(0+2)=1;
Δ14=c14-(u1+v4)=2-(0+1)=1;
Δ21=0;
Δ22=c22-(u2+v2)=4-(-1+0)=5;
Δ23=0;
Δ24=c24-(u2+v4)=2-(-1+1)=2;
Δ31=c31-(u3+v1)=1-(2+2)=-3;
Δ3233=0;
Δ34=c34-(u3+v4)=5-(2+1)=2;
Δ41=c41-(u4+v1)=3-(0+2)=1;
Δ42=c42-(u4+v2)=4-(0+0)=4;
Δ4344=0;
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
ПоставщикиB1B2B3B4Запас
A12*1201/13/12/1120
A21*404/51*1002/2140
A31/-32*1804*505/2230
A43/14/42*501*150200
Потребность160180200150690

В новой таблице только ячейка A3:B1 содержит отрицательную оценку (-3). Вместе с ячейками A3:B3, A2:B3 и A2:B1 она образует замкнутый цикл, в котором ячейки A3:B1 и A2:B3 - "положительные", а A3:B3 и A2:B1 - "отрицательные":
ПоставщикиB1B2B3B4Запас
A12*1201/13/12/1120
A21*404/51*1002/2140
A31/-32*1804*505/2230
A43/14/42*501*150200
Потребность160180200150690

Среди "отрицательных" ячеек наименьшее значение поставки достигается в A2:B1 (40). Уменьшаем на 40 объём поставок для ячеек A3:B3 и A2:B1, увеличиваем на 40 объём поставок для ячеек A3:B1 и A2:B3. Получаем новое опорное решение:
ПоставщикиB1B2B3B4Запас
A12*120132120
A2141*1402140
A31*402*1804*105230
A4342*501*150200
Потребность160180200150690

и вычисляем новую стоимость перевозок:
2·120 + 1·140 + 1·40 + 2·180 + 4·10 + 2·50 + 1·150 = 1070,
либо как
1190 - 3·40 = 1070.
Для нового решения вычислим потенциалы:
u1=0;
c11=u1+v1=2v1=2-0=2;
c31=u3+v1=1u3=1-2=-1;
c32=u3+v2=2v2=2-(-1)=3;
c33=u3+v3=4v3=4-(-1)=5;
c23=u2+v3=1u2=1-5=-4;
c43=u4+v3=2u4=2-5=-3;
c44=u4+v4=1v4=1-(-3)=4.
и добавим их в таблицу:
ПоставщикиB1B2B3B4ЗапасU
A12*1201321200
A2141*1402140-4
A31*402*1804*105230-1
A4342*501*150200-3
Потребность160180200150690
V2354

Найдём оценки поставок:
Δ11=0;
Δ12=c12-(u1+v2)=1-(0+3)=-2;
Δ13=c13-(u1+v3)=3-(0+5)=-2;
Δ14=c14-(u1+v4)=2-(0+4)=-2;
Δ21=c21-(u2+v1)=1-(-4+2)=3;
Δ22=c22-(u2+v2)=4-(-4+3)=5;
Δ23=0;
Δ24=c24-(u2+v4)=2-(-4+4)=2;
Δ313233=0;
Δ34=c34-(u3+v4)=5-(-1+4)=2;
Δ41=c41-(u4+v1)=3-(-3+5)=1;
Δ42=c42-(u4+v2)=4-(-3+4)=3;
Δ4344=0;
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
ПоставщикиB1B2B3B4Запас
A12*1201/-23/-22/-2120
A21/34/51*1402/2140
A31*402*1804*105/2230
A43/44/42*501*150200
Потребность160180200150690

Наименьшую оценку -2 содержат ячейки A1:B2, A1:B3 и A1:B4. Выберем одну из них, например A1:B2. Вместе с ячейками A3:B2, A3:B1 и A1:B1 она образует замкнутый цикл, в котором ячейки A1:B2 и A3:B1 - "положительные", а A3:B2 и A1:B1 - "отрицательные":
ПоставщикиB1B2B3B4Запас
A12*1201/-23/-22/-2120
A21/34/51*1402/2140
A31*402*1804*105/2230
A43/44/42*501*150200
Потребность160180200150690

Среди "отрицательных" ячеек наименьшее значение поставки достигается в A1:B1 (120). Уменьшаем на 120 объём поставок для ячеек A3:B2 и A1:B1, увеличиваем на 40 объём поставок для ячеек A1:B2 и A3:B1. Получаем новое опорное решение:
ПоставщикиB1B2B3B4Запас
A121*12032120
A2141*1402140
A31*1602*604*105230
A4342*501*150200
Потребность160180200150690

и вычисляем новую стоимость перевозок:
1·120 + 1·140 + 1·160 + 2·60 + 4·10 + 2·50 + 1·150 = 830,
либо как
1070 - 2·120 = 830.
Для нового решения вычислим потенциалы:
u1=0;
c12=u1+v2=1v2=1-0=1;
c32=u3+v2=2u3=2-1=1;
c31=u3+v1=1v1=1-1=0;
c33=u3+v3=4v3=4-1=3;
c23=u2+v3=1u2=1-3=-2;
c43=u4+v3=2u4=2-3=-1;
c44=u4+v4=1v4=1-(-1)=2.
и добавим их в таблицу:
ПоставщикиB1B2B3B4ЗапасU
A121*120321200
A2141*1402140-2
A31*1602*604*1052301
A4342*501*150200-1
Потребность160180200150690
V0132

Найдём оценки поставок:
Δ11=c11-(u1+v1)=2-(0+0)=2;
Δ12=0;
Δ13=c13-(u1+v3)=3-(0+3)=0;
Δ14=c14-(u1+v4)=2-(0+2)=0;
Δ21=c21-(u2+v1)=1-(-2+0)=3;
Δ22=c22-(u2+v2)=4-(-2+1)=5;
Δ23=0;
Δ24=c24-(u2+v4)=2-(-2+2)=2;
Δ313233=0;
Δ34=c34-(u3+v4)=5-(1+2)=2;
Δ41=c41-(u4+v1)=3-(-1+0)=4;
Δ42=c42-(u4+v2)=4-(-1+1)=4;
Δ4344=0.
Отрицательных оценок нет, следовательно, последнее решение со стоимостью 830 является оптимальным.

5. Используем также метод потенциалов для оптимизации опорного решения, полученного методом двойного предпочтения и методом минимальной стоимости:
ПоставщикиB1B2B3B4Запас
A121*12032120
A21*140412140
A31*202*604*1505220
A4342*501*150200
Потребность160180200150690

Вычислим потенциалы:
u1=0;
c12=u1+v2=1v2=1-0=1;
c32=u3+v2=2u3=2-1=1;
c31=u3+v1=1v1=1-1=0;
c21=u2+v1=1u2=1-0=1;
c33=u3+v3=4v3=4-1=3;
c43=u4+v3=2u4=2-3=-1;
c44=u4+v4=1v4=1-(-1)=2.
и добавим их в таблицу:
ПоставщикиB1B2B3B4ЗапасU
A121*120321200
A21*1404121401
A31*202*604*15052201
A4342*501*150200-1
Потребность160180200150690
V0132

Найдём оценки поставок:
Δ11=c11-(u1+v1)=2-(0+0)=2;
Δ12=0;
Δ13=c13-(u1+v3)=3-(0+3)=0;
Δ14=c14-(u1+v4)=2-(0+2)=0;
Δ21=0;
Δ22=c22-(u2+v2)=4-(1+1)=2;
Δ23=c23-(u2+v3)=1-(1+3)=-3;
Δ24=c24-(u2+v4)=2-(1+2)=-1;
Δ313233=0;
Δ34=c34-(u3+v4)=5-(1+2)=2;
Δ41=c41-(u4+v1)=3-(-1+0)=4;
Δ42=c42-(u4+v2)=4-(-1+1)=4;
Δ4344=0.
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
ПоставщикиB1B2B3B4Запас
A12/21*1203/02/0120
A21*1404/21/-32/-1140
A31*202*604*1505/2220
A43/44/42*501*150200
Потребность160180200150690

Ячейка A2:B3 содержит наименьшую оценку (-3). Вместе с ячейками A3:B3, A3:B1 и A2:B1 она образует замкнутый цикл, в котором ячейки A2:B3 и A3:B1 - "положительные", а A3:B3 и A2:B1 - "отрицательные":
ПоставщикиB1B2B3B4Запас
A12/21*1203/02/0120
A21*1404/21/-32/-1140
A31*202*604*1505/2220
A43/44/42*501*150200
Потребность160180200150690

Среди "отрицательных" ячеек наименьшее значение поставки достигается в A2:B1 (140). Уменьшаем на 140 объём поставок для ячеек A3:B3 и A2:B1, увеличиваем на 140 объём поставок для ячеек A2:B3 и A3:B1. Получаем новое опорное решение:
ПоставщикиB1B2B3B4Запас
A121*12032120
A2141*1402140
A31*1602*604*105220
A4342*501*150200
Потребность160180200150690

и вычисляем новую стоимость перевозок:
1·120 + 1·140 + 1·160 + 2·60 + 4·10 + 2·50 + 1·150 = 830,
либо как
1250 - 3·140 = 830.
Решение совпадает с полученным ранее. Поскольку в данном случае исходное опорное решение было более оптимальным, оптимизация потребовала всего одного шага (вместо трёх).


Консультировал: Коцюрбенко Алексей Владимирович (Модератор)
Дата отправки: 23.12.2015, 17:09

5
нет комментария
-----
Дата оценки: 23.12.2015, 17:19

Рейтинг ответа:

+3

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 188421
Посетитель - 399202
1-й класс

ID: 399202

# 1

= общий = | 13.12.2015, 19:59 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

http://rfpro.ru/question/188421#

-----
 Прикрепленный файл (кликните по картинке для увеличения):

Посетитель - 399202
1-й класс

ID: 399202

# 2

= общий = | 13.12.2015, 20:00 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

http://rfpro.ru/question/188421#

-----
 Прикрепленный файл (кликните по картинке для увеличения):

Гордиенко Андрей Владимирович
Профессионал

ID: 17387

# 3

= общий = | 13.12.2015, 20:03 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Экспертам раздела:

Обратите, пожалуйста, внимание на эту задачу.

=====
Facta loquuntur.

Коцюрбенко Алексей Владимирович
Модератор

ID: 312929

# 4

= общий = | 23.12.2015, 17:12 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Посетитель - 399202:

Опорные решения построил, оптимизацию методом потенциалов добавлю чуть позже.

Посетитель - 399202
1-й класс

ID: 399202

# 5

= общий = | 23.12.2015, 17:18 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

smile спасибо вам огромное!

Посетитель - 399202
1-й класс

ID: 399202

# 6

= общий = | 24.12.2015, 16:17 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

я подожду когда полностью будет задача готова, вы только не удаляйте пожалуйста решение...спасибо smile

Коцюрбенко Алексей Владимирович
Модератор

ID: 312929

# 7

= общий = | 25.12.2015, 05:22 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Посетитель - 399202:

Решение готово. Насчёт удаления не беспокойтесь, правильные решения на портале никогда не удаляют.

 

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.20623 сек.

© 2001-2019, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.78 от 18.11.2019
Версия JS: 1.34 | Версия CSS: 3.35