Решение с помощью надстройки «Поиск решения»




Метод потенциалов

Найдем решение транспортной задачи, исходные данные которой приведены ниже в таблице.

Поставщики Потребители
В1 В2 В3 В4 В5 Запасы
А1            
А2            
А3            
Потребности            

Таблица 1. Исходные данные

Вставим эту таблицу в программу Excel (см. Рисунок 1). В ячейке G7 введена формула =СУММ(G4:G6)-СУММ(B7:F7), которая определяет вид транспортной задачи. Так как значение ячейки G7 равно нулю, то сумма запасов Поставщиков совпадает с суммой потребностей Потребителей. Поэтому рассматриваемая транспортная задача будет закрытой.

Рисунок 1. Основная таблица транспортной задачи

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

Выделим таблицу стоимостей Основной таблицы и скопируем ее в буфер обмена. Далее воспользуемся специальной вставкой, выбрав в окне специальной вставки в группе Вставка кнопку форматы (см. Рисунок 2).

 

Рисунок 2. Заполнение первого опорного плана

В ячейку G10 вставлена формула =G4-СУММ(B10:F10), которая копируется вниз до ячейки G12. В ячейку В13 вставлена формула =B7-СУММ(B10:B12), которая копируется вправо до ячейки F13. Таблица-план 1 создана, если значения ячеек справа и ниже этой таблицы примут нулевые значения и число заполненных ячеек будет равно сумме числа строк и столбцов таблицы стоимостей минус единица.

В таблице стоимостей ищем ячейку с минимальным значением. В Таблице-план 1 соответствующую ячейку заливаем выбранным цветом и в эту ячейку вводим значение. В таблице стоимостей перевозок выбираем следующую ячейку с минимальным значением. В Таблице-план 1 соответствующую ячейку заливаем выбранным цветом, и в эту ячейку вводим значение. Продолжая процесс заполнения ячеек Таблицы-план 1, выбирая минимальные значения в таблице стоимостей среди ячеек, соответствующие тем ячейкам Таблицы-план1, которые не окантованы нулевыми значениями справа в строке и ниже в столбце, получаем окончательно первый опорный план перевозок (см. Рисунок 3). Таблица, представленная на рисунке 3, действительно представляет опорный план: число заполненных ячеек равно 7 и таблица окантована нулевыми значениями (справа таблицы и ниже таблицы).

В ячейке Н13 введена формула =СУММПРОИЗВ($B$4:$F$6;B10:F12), которая рассчитывает стоимость перевозок от поставщиков к потребителям.

Рисунок 3. Заполнение первого опорного плана

Теперь проверим заполненную таблицу на оптимальность. Для этого воспользуемся методом потенциалов. Скопируем таблицу стоимостей перевозок и вставим на свободное место листа программы Excel. Скопируем Таблицу-план 1 (ее основную часть) и с помощью специальной вставки, выбрав форматы, вставим в тоже место, куда была вставлена таблица стоимостей перевозок (см. Рисунок 4). Вставим слева и выше Таблицы-потенциалов 1 названия потенциалов. Значения потенциалов будут находиться справа и ниже таблицы.

Рисунок 4. Заполнение таблицы потенциалов

Для нахождения потенциалов одному из потенциалов присвоим некоторое значение, например, потенциалу U1 присвоим значение, равное нулю. В данном случае неизвестен потенциал V5. Значение неизвестного потенциала всегда вычисляется по формуле: стоимость перевозки (в данном случае 3) минус значение известного потенциала (в данном случае 0). В ячейку Е20 вводим формулу =F17-G17. Остальные вычисляем по тому же принципу.

Теперь составим проверочную таблицу (см. Рисунок 5). В ячейку В23 вставлена формула =B17-B$20-$G17, которая вычисляет разность между стоимостью перевозки и суммы соответствующих потенциалов. Эта формула копируется во все ячейки Проверочной таблицы 1. Если потенциалы найдены правильно, то в значения закрашенных ячеек равно нулю. Таблица-план 1 будет оптимальной, если все значения Проверочной таблицы 1 будут равны нулю и больше нуля. В нашем случае Таблица-план 1 не оптимальна. Найдем максимальное по абсолютной величине отрицательное значение (если таких несколько, то выбираем любое из них).

Рисунок 5. Проверочная таблица

Скопируем основную часть Таблицы-план 1 и вставим ее в свободную часть листа программы Excel. В ячейку Таблицы - план 2, соответствующей максимальному по абсолютному значению отрицательному значению Проверочной таблицы 1, вводим некоторое, пока еще неизвестное, число W. После этого изменились на число W суммы значений ячеек строки и столбца, на пересечении которых находится ячейка со значением W Таблицы - план 2. Эта ячейка будет заполненной ячейкой. Для того, чтобы не изменилась сумма в измененном столбце, нужно по этому столбцу перейти к закрашенной ячейке и вычесть из ее значения число W. Переходим к следующей закрашенной ячейке по строке и прибавляем к ее значению число W. Сумма значений ячеек этой строки не изменилась. Подберем число W так, чтобы все значения измененных ячеек были неотрицательными. Максимально возможное число в данном случае равно 110. Ячейка с этим числом становиться незаполненной. Значения остальных ячеек пересчитываются по циклу с найденным числом W.

Проверим правильность заполнения Таблицы - план 2. В ячейку G27 введем формулу =G4-СУММ(В27:F27) и копируем ее вниз до ячейки G29. В ячейку В30 введем формулу =В7-СУММ(В27:В29) и копируем ее вправо до ячейки F30. В ячейке Н30 вычисляется общая сумма затрат на перевозки по формуле =СУММПРОИЗВ($B$4:$F$6;B27:F29).

Рисунок 6. Заполнение второго опорного плана перевозок

Таблица-план 2 будет заполнена правильно, если она окантована снизу и справа нулевыми значениями, число заполненных ячеек равно сумме числа строк и столбцов таблицы стоимостей минус один, стоимость перевозок будет не меньше, чем стоимость перевозок предыдущей таблицы-план.

Снова проверяем Таблицу-план 2 на оптимальность по указанному методу выше. В нашем случае Таблица-план 2 не оптимальна. Копируем основную часть Таблицы-план 2 в пустое место листа Excel, тем самым создаем Таблицу-план 3, с помощью ввода некоторого числа W и повторения методики, описанной выше. Проверяем Таблицу план 3 на оптимальность. В основной части проверочной таблицы 3 отсутствуют отрицательные значения (план улучшить нельзя), следовательно достигнуто оптимальное решение (Рисунок 7).

Рисунок 7. Таблица-план 3 оптимальна.

 


 

Решение с помощью надстройки «Поиск решения»

Найдем решение транспортной задачи, исходные данные которой приведены ниже в таблице

Поставщики Потребители
В1 В2 В3 В4 В5 Запасы
А1            
А2            
А3            
Потребности            

Таблица 2 - Исходные данные

Вставим эту таблицу в программу Excel (см. Рисунок 8)

Рисунок 8. Основная таблица транспортной задачи

Подготовим лист программы Excel для применения надстройки «Поиск решения» (см. Рисунок 9).

Прежде всего, заполним таблицу-план. Размеры таблицы-план совпадают с размерами таблицы стоимостей. Надстройка «Поиск решения» программы Excel, изменяя значения этих ячеек, будет находить по определенному алгоритму решение рассматриваемой задачи. Кроме того, надстройка «Поиск решения» требует, чтобы в этих ячейках до начала работы надстройки были введены начальные приближения решаемой

Рисунок 9. Подготовка листа программы Excel для применения надстройки «Поиск решения»

задачи. Для линейных задач, в большинстве случаев, начальное приближение может быть любым. Обычно выбирают в качестве начальных приближений единицы (см. рисунок 9).

Слева и снизу таблицы-план вводят левые части ограничений транспортной задачи: суммы значений ячеек таблицы-план по строкам и столбцам. В ячейку О4 введена формула =СУММ(J4:N4), которая копируется вниз до ячейки О6. В ячейку J7 введена формула =СУММ(J4:J6), которая копируется вправо до ячейки N7. В ячейке Q4 введена формула =СУММПРОИЗВ(B4:F6;J4:N6), которая вычисляет общую стоимость перевозок при выбранном плане перевозок. Заполненное окно надстройки «Поиск решения» показано на рисунке 10.

Рисунок 10. Окно надстройки «Поиск решения»

Рисунок 11. Результат работы надстройки «Поиск решения»


 

2. ЗАКЛЮЧЕНИЕ


 

3. СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. https://bb.usurt.ru/webapps/blackboard/execute/displayLearningUnit?course_id=_6200_1&content_id=_261315_1&framesetWrapped=true

2. https://bb.usurt.ru/webapps/blackboard/content/listContent.jsp?course_id=_6200_1&content_id=_261805_1

3. https://bb.usurt.ru/webapps/blackboard/execute/displayLearningUnit?course_id=_6200_1&content_id=_261597_1&framesetWrapped=true

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-06-11 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: