Здавалка
Главная | Обратная связь

Решение транспортных задач с использованием оптимизационной надстройки MICROSOFT EXCEL «Поиск решения»



 

Для практического решения транспортных задач может быть использована оптимизационная надстройка « Поиск решения » , входящая в стандартный пакет программ Microsoft OfficeÒ. Данная надстройка позволяет определять экстремальные значения ячейки листа Excel при изменении значений влияющих ячеек. Влияющие и зависимые ячейки должны быть связаны формулами листа. Для решения линейных и целочисленных задач с ограничениями используются алгоритмы симплексного метода и метода ветвей и границ.

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

Прежде всего необходимо составить таблицу исходных данных с указанием объемов производства и потребления и стоимостей доставки единицы груза (рис. 4). Некоторые маршруты перевозки при необходимости блокируются (см. п. 2.2).

 

 

Исходные данные к решению транспортной задачи

 

A B C D E F G H I
      Станции, принимающие груз    
      B1 B2   B3    
Пункты Виды j Т Т Т, Д Т, Д    
Отправления грузов I A(ik)  
A1 Т  
  Д  
A2 Т  
A3 Т  
  Д  
A4 Д  
    b(j)    
                 

Рис. 4

 

Затем составляется исходная форма плана перевозок ( рис. 5).

 

 

                 
      Станции, принимающие груз    
      B1 B2   B3    
Пункты Виды j Т Т Т, Д Т, Д    
Отправления грузов I A(ik)  
A1 Т  
  Д  
A2 Т  
A3 Т  
  Д  
A4 Д  
    b(j)    
               
              Z
     
               

Рис. 5

 

В ячейки D18 – G23 заносятся минимальные возможные значения объемов перевозок между пунктами (0). Значение в ячейке D24 определяется по формуле:

=СУММ(D18:D23). Фактически это значение . Аналогично вычисляются значения ячеек E24 – G24.

Значение в ячейке Н18 определяется по формуле: =СУММ(D18:G18). Эта запись соответствует значению . Аналогично вычисляются значения ячеек Н19 – Н23.

Значения, находящиеся в ячейках D27 – G27 соответствуют выражениям при j = 1 ( ячейка D27 ), j = 2 ( ячейка E27 ) и так далее. Значение в ячейке D27 будет вычисляться по формуле:

D6*D18+D7*D19+D8*D20+D9*D21+D10*D22+D11*D23.

По аналогичным формулам определяются значения ячеек E27 – G27. Значение в ячейке Н27 равно сумме значений ячеек D27 – G27 (=СУММ(D27:G27) и соответствует значению целевой функции Z рассматриваемой транспортной задачи.

После выполнения вышеперечисленных подготовительных действий переходят непосредственно к решению задачи. Для этого нужно из меню “Сервис” программы Microsoft Excel вызвать надстройку “Поиск решения” ( если данная надстройка не активизирована, это можно сделать через подменю “Надстройки” меню “Сервис” ).

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

1) Целевая функция – адрес ячейки, в которой она находится ( в нашем примере ячейка Н27). Целевая функция устанавливается равной минимальному значению ( поскольку цель оптимизации – минимизировать расходы на перевозки).

2) Изменяемые ячейки – те ячейки, в которые занесены параметры управления ( объемы перевозок по оптимизируемому плану). В нашем случае это ячейки с адресами в диапазоне D18 ¸ G23.

3) Ограничения – добавляются, изменяются и удаляются с помощью кнопок «Добавить», «Изменить» и «Удалить». В нашем примере таких ограничений будет три:

a) О полном вывозе груза из пунктов производства;

b) о полном удовлетворении потребностей пунктов потребления;

c) условие неотрицательности параметров управления ( см. п. 2.2 ).

Эти ограничения реализуются следующим образом: при помощи кнопки «Добавить» вызовите окно ввода ограничений. Укажите в нем необходимое ограничение.

Например, для ограничения (a) в качестве ссылок на ячейки указываем адреса ячеек Н18:Н23, знак условия « = », ограничение – адреса ячеек Н6:Н11. Это ограничение эквивалентно записи .

Для ограничения (b) ( ): D12:G12 = D24:G24.

Условие не отрицательности перевозок ( ) выглядит так: D18:G23 ≥ 0.

Поскольку рассматриваемые транспортные задачи – линейного типа, то в окне «Параметры поиска решения» (вызывается нажатием кнопки «Параметры») необходимо установить флажок рядом с пунктом «Линейная модель». Остальные параметры надстройки, установленные по умолчанию, не нуждаются в изменении («OK»).

После того, как были выполнены все перечисленные действия, все готово для запуска процесса решения задачи («Выполнить»). В процессе решения задачи в строке состояния будут отображаться сообщения. Через некоторое время появится сообщение о том, что решение найдено. Полученное решение можно сохранить.

Результаты решения задачи представлены на рис. 6. Целевая функция Z = 1252.

 

 

               
      Станции, принимающие груз  
      B1 B2   B3  
Пункты Виды J Т Т Т, Д Т, Д  
отправления грузов I A(ik)
A1 Т
  Д
A2 Т
A3 Т
  Д
A4 Д
    b(j)  
               
              Z
     
               

Рис. 6

Другие транспортные задачи решаются аналогичным образом, с учетом изменения исходных данных и ограничений.

 







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.