Материал: МО КР1

Решение:

Число пунктов отправления m=4, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=4+4−1=7 заполненных клетках таблицы. Тарифы перевозок единицы груза из каждого пункта отправления во все пункты назначения задаются матрицей

Наличие груза у поставщиков равно:

Общая потребность в грузе в пунктах назначения равна:

∑ Ai<∑ Bi. Модель транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительный пункт отправления A5 c запасами 350− 300=50. Тарифы перевозки из пункта отправления A5 во все пункты назначения полагаем равными нулю. В результате получим закрытую модель транспортной задачи:

Найдем опорный план задачи методом северно-западного угла.

A1≤B1. Следовательно в клетку (A1, B1) помещаем число min(A1, B1 )=50. Запасы пункта A1 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A1 и будем считать потребности пункта B1 равными 50−50=0.

A2>B1. Следовательно в клетку (A2, B1) помещаем число min(A2, B1)=0. Потребности пункта B1 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B1 и будем считать запасы пункта A2 равными 100−0=100.

A2≤B2. Следовательно в клетку (A2, B2 ) помещаем число min(A2, B2 )=100. Запасы пункта A2 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A2 и будем считать потребности пункта B2 равными 100−100=0.

A3>B2. Следовательно в клетку (A3, B2) помещаем число min(A3, B2)=0. Потребности пункта B2 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B2 и будем считать запасы пункта A3 равными 50−0=50.

A3≤B3. Следовательно в клетку (A3, B3 ) помещаем число min(A3, B3 )=50. Запасы пункта A3 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A3 и будем считать потребности пункта B3 равными 100−50=50.

A4>B3. Следовательно в клетку (A4, B3) помещаем число min(A4, B3)=50. Потребности пункта B3 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B3 и будем считать запасы пункта A4 равными 100−50=50.

A4≤B4. Следовательно в клетку (A4, B4 ) помещаем число min(A4, B4 )=50. Запасы пункта A4 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A4 и будем считать потребности пункта B4 равными 100−50=50.

A5≤B4. Следовательно в клетку (A5, B4 ) помещаем число min(A5, B4 )=50. Запасы пункта A5 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A5 и будем считать потребности пункта B4 равными 50−50=0.

Найдем оптимальный план транспортной задачи методом потенциалов.

Опорный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

S=2·50 +5·0+ 3·100 +1·0+ 2·50+ 6·50+ 9·50+ 0·50= 1250

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 8 уравнений с 9 неизвестными:

β1−α1=2; β1−α2=5; β2−α2=3; β2−α3=1; β3−α3=2; β3−α4=6; β4−α4=9; β4−α5=0;

Полагая α1=0, находим β1=2 α2=-3 β2=0 α3=-1 β3=1 α4=-5 β4=4 α5=4 .

α12=-4, α13=-4, α14=-4, α23=0, α24=1, α31=0, α34=1, α41=0, α42=3, α51=-2, α52=-4, α53=-3.

Полученные числа заключаем в рамки и записываем их в соответствующие клетки таблицы:

Среди чисел αij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 3 находится в пересечении строки A4 и столбца B2. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак "+" а остальные клетки цикла поочередно знаки "−" и "+".

Наименьшее из чисел в минусовых клетках равно 0. Клетка, в которой находится это число становится свободной. В новой таблице другие числа получаются так. Числам, находящимся в плюсовых клетках, добавляется 0, а из чисел, находящихся в минусовых клетках, вычитается это число.

Опорный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

S=2·50 +5·0+ 3·100 +2·50 +2·0+ 6·50+ 9·50+ 0·50= 1250

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 8 уравнений с 9 неизвестными:

β1−α1=2; β1−α2=5; β2−α2=3; β3−α3=2; β2−α4=2; β3−α4=6; β4−α4=9; β4−α5=0;

Полагая α1=0, находим β1=2 α2=-3 β2=0 α4=-2 β3=4 β4=7 α3=2 α5=7.

Для каждой свободной клетки вычисляем число αij=βj−αi−cij:

α12=-4, α13=-1, α14=-1, α23=3, α24=4, α31=-3, α32=-3, α34=1, α41=-3, α51=-5, α52=-7, α53=-3.

Полученные числа заключаем в рамки и записываем их в соответствующие клетки таблицы:

Среди чисел αij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 4 находится в пересечении строки A2 и столбца B4. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак "+" а остальные клетки цикла поочередно знаки "−" и "+".

Наименьшее из чисел в минусовых клетках равно 50. Клетка, в которой находится это число становится свободной. В новой таблице другие числа получаются так. Числам, находящимся в плюсовых клетках, добавляется 50, а из чисел, находящихся в минусовых клетках, вычитается это число.

Опорный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

S=2·50 +5·0+ 3·50+ 6·50+ 2·50+ 2·50+ 6·50+ 0·50= 1050

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 8 уравнений с 9 неизвестными:

β1−α1=2; β1−α2=5; β2−α2=3; β4−α2=6; β3−α3=2; β2−α4=2; β3−α4=6; β4−α5=0;

Полагая α1=0, находим β1=2 α2=-3 β2=0 β4=3 α4=-2 α5=3 β3=4 α3=2 .

Для каждой свободной клетки вычисляем число αij=βj−αi−cij:

α12=-4, α13=-1, α14=-5, α23=3, α31=-3, α32=-3, α34=-3, α41=-3, α44=-4, α51=-1, α52=-3, α53=1.

Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы:

Среди чисел αij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 3 находится в пересечении строки A2 и столбца B3. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак "+" а остальные клетки цикла поочередно знаки "−" и "+".

Наименьшее из чисел в минусовых клетках равно 50. Клетка, в которой находится это число становится свободной. В новой таблице другие числа получаются так. Числам, находящимся в плюсовых клетках, добавляется 50, а из чисел, находящихся в минусовых клетках, вычитается это число.

Опорный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

S=2·50 +5·0+ 3·0+4 ·50+6·50+2·50+2· 100+0·50=900

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 8 уравнений с 9 неизвестными:

β1−α1=2; β1−α2=5; β2−α2=3; β3−α2=4; β4−α2=6; β3−α3=2; β2−α4=2; β4−α5=0;

Полагая α1=0, находим β1=2 α2=-3 β2=0 β3=1 β4=3 α4=-2 α3=-1 α5=3 .

Для каждой свободной клетки вычисляем число αij=βj−αi−cij:

α12=-4, α13=-4, α14=-5, α31=0, α32=0, α34=0, α41=-3, α43=-3, α44=-4, α51=-1, α52=-3, α53=-2.

Полученные числа заключаем в рамки и записываем их в соответствующие клетки таблицы:

Среди чисел αij нет положительных. Следовательно данный опорный план является оптимальным.

Ответ:

Оптимальный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

S=2·50 +5·0+ 3·0+4 ·50+6·50+2·50+2· 100=900

При этом плане остается неудовлетворенным потребности (50) пункта B4.

Распределение ресурсов:

Из склада A1 отправить груз (50) в пункт B1

Из склада A2 отправить груз (50) в пункт B3

Из склада A2 отправить груз (50) в пункт B4

Из склада A3 отправить груз (50) в пункт B3

Из склада A4 отправить груз (100) в пункт B2

Сделаем проверку средствами Excel

Создадим таблицу с исходными данными сразу открытого типа:

Рис. 6 Excel

Зададим условия поиска решения:

Рис. 7 Excel

Результаты поиска решения:

Рис. 8 Excel

В результате работы программы были получены аналогичные результаты.

Выполним условия по ограничения X₄₂≤50, X₂₄ ≥50. Расчеты будем производить в таблице Excel. Для этого в параметрах поиска решения добавим новые условия:

Рис. 9 Excel

В результате работы программы ошибок не было обнаружено и было найдено оптимальное решение:

Рис.10 Excel

Рис.11 Excel

Оптимальный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

S=2·50 +3·19+1·31+2·50+4·31+2·19+6·50+6·50=1050

При этом плане остается неудовлетворенным потребности (50) пункта B4.

Распределение ресурсов:

Из склада A1 отправить груз (50) в пункт B1

Из склада A2 отправить груз (19) в пункт B2

Из склада A2 отправить груз (31) в пункт B3

Из склада A2 отправить груз (50) в пункт B4

Из склада A3 отправить груз (31) в пункт B2

Из склада A3 отправить груз (19) в пункт B3

Из склада A4 отправить груз (50) в пункт B2

Из склада A4 отправить груз (50) в пункт B3

Выводы:

Транспортная задача, это специальный вид задачи линейного программирования. Для решения транспортной задачи можно использовать методы решения задач линейного программирования, однако ввиду специфического вида задачи гораздо быстрее и удобнее использовать программные алгоритмы решения.

Задание 3:

После нескольких лет эксплуатации промышленное оборудование оказывается в одном из следующих состояний:

1) оборудование может использоваться в очередном году после профилактического ремонта;

2) для безаварийной работы оборудования в дальнейшем следует заменить отдельные его детали и узлы;

3) оборудование требует капитального ремонта или замены.

В зависимости от сложившейся ситуации руководство предприятия в состоянии принять такие решения: 1) отремонтировать оборудование силами заводских специалистов, что потребует, в зависимости от обстановки, затрат, равных а1, а2 или а 3 ден. ед.; 2) вызвать специальную бригаду ремонтников, расходы в этом случае составят b1, b2 или b3 ден. ед.; 3) заменить оборудование новым, реализовав устаревшее оборудование по его остаточной

стоимости; совокупные затраты в результате этого мероприятия будут равны соответственно с1, с2 или с3 ден. ед. Указанные выше расходы предприятия включают кроме стоимости ремонта и заменяемых деталей, и узлов убытки, вызванные ухудшением качества выпускаемой продукции, простоем неисправного оборудования, а также затраты на установку и отладку нового оборудования. Требуется:

1) придать описанной ситуации игровую схему, установить характер игры и выявить ее участников, указать возможные чистые стратегии сторон;

2) составить платежную матрицу;

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

а) накопленный на предприятии опыт эксплуатации аналогичного оборудования показывает, что вероятности указанных выше состояний оборудования равны соответственно q1, q2, q3;

б) имеющийся опыт свидетельствует о том, что все три возможных состояния оборудования равновероятны;

в) о вероятностях состояний оборудования ничего определенного сказать нельзя.

Указание. В п. 3 следует найти оптимальные чистые стратегии, пользуясь: в п. 3) а) — критерием Байеса, в п. 3) б) — критерием Лапласа, в п. 3) в) — критериями Вальда, Сэвиджа, Гурвица (значение параметра У в критерии Гурвица задается).

4) Решить в смешанных стратегиях (сведением к задаче линейного программирования).