АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Работа рассчитана на 2 аудиторных часа. Пример 4. Определить наикратчайший путь между вершиной 1 и вершиной 7 на графе с циклами, представленном на рис

Читайте также:
  1. II. Работа с кувезом.
  2. II. Самостоятельная работа студентов на занятии.
  3. III. Работа с подобранной литературой
  4. III. Работа с подобранной литературой
  5. IV. Контрольная работа, ее характеристика
  6. T-FACTORY HRM - управление персоналом и работами
  7. V. САМОСТОЯТЕЛЬНАЯ РАБОТА
  8. V. САМОСТОЯТЕЛЬНАЯ РАБОТА СТУДЕНТОВ
  9. V. Самостоятельная работа студентов с больными.
  10. V2: Работа и энергия
  11. Window - работа с окнами.
  12. А) Образовательные технологии, используемые в аудиторных занятиях

Пример 4. Определить наикратчайший путь между вершиной 1 и вершиной 7 на графе с циклами, представленном на рис. 4.1.

 

Задание 1. Решение задачи при помощи преобразования матрицы

 

Для решения транспортной задачи в процедуре EXCEL «Поиск решения», представим ее как транспортную задачу с промежуточными пунктами. Будем считать, что транспортные расходы при перевозке одной единицы груза равны (в условных единицах) расстояниям между вершинами. Одна единица груза отправляется из вершины 1 (исходный пункт) и должна прибыть в вершину 7 (пункт назначения). Вершины 2, 3, 4, 5, 6 рассматриваются как промежуточные пункты, которые являются одновременно и исходными пунктами и пунктами назначения.

Требуется определить такую последовательность вершин, по которым должна перемещаться единица груза, отправленная из вершины 1, при которой стоимость транспортных расходов будет минимальна и груз попадет в вершину 7.

Так как транспортные расходы при перемещении груза из одной вершины в другую равны расстоянию между вершинами, то последовательность вершин, при которой транспортные расходы будут минимальными, определяет наикратчайший путь из вершины 1 в вершину 7. Матрица транспортных расходов, соответствующая данному графу, представлена в табл. 4.2.

Таблица 4.2

Исходные пункты Пункты назначения Количество груза отправленного из пункта
           
          М М  
    М   М   М  
  М       М М  
            М  
  М            
    М          
Количество груза прибывшего в пункт              

Буквой М обозначается случай, когда между соответствующими вершинами нет пути. В качестве М берут число, значительно большее самого большего пути. В данной задаче наибольший путь между 5-й и 7-ой вершинами, поэтому можно взять, например, М = 50. Для промежуточных пунктов 2, 3, 4, 5, 6 должны быть предусмотрены буферные емкости В, которая должна быть не меньшей, чем количество груза, перемещаемого в сети, описываемой графом. В данной задаче В = 1. После введения буферных емкостей в первый столбец и нижнюю строку таблицы и замены М = 50, получим транспортную задачу, представляющую задачу о назначениях (табл. 4.3).

Таблица 4.3

Исходные пункты Пункты назначения Количество груза отправленного из пункта
           
               
               
               
               
               
               
Количество груза прибывшего в пункт              

 

Последовательные преобразования матрицы транспортных расходов показаны на рис. 4.2, 4.3, 4.4.

 

           
           
           
           
           
           

 

Рис. 4.2

 
           
           
           
           
           
           

 

Рис. 4.3.

 

Рис. 4.4.

 

На рис. 4.2 показаны результаты вычитания минимального элемента первой строки (он равен 2) из первой строки, на рис. 4.3 приведены результаты вычитания минимального элемента из шестого столбца (он равен 4) и результат вычеркивания строк и столбцов с нулями. На рис. 4.5 показаны результаты вычитания из не вычеркнутых элементов минимального элемента (он равен единице) и результат вычеркивания строк и столбцов второй раз.

       
   


           
           
51          
6          
           
7          

 

Рис. 4.5

 

На рис. 4.6 приведены окончательные результаты преобразования и результаты допустимого выбора из множества нулей.

 

           
           
           
           
           
           

Рис. 4.6.

 

Перенеся эти результаты на исходную таблицу (табл. 4.3), получим новую таблицу 4.4.

Таблица 4.4

Исходные пункты Пункты назначения Количество груза, отправленного из пункта
           
          М М  
    М   М   М  
  М       М М  
            М  
  М            
    М          
Количество груза, прибывшего в пункт              

 

Наикратчайший путь из вершины 1 в вершину 7 определяется следующей траекторией: 1 → 2 → 6 → 7

Длина наикратчайшего пути равна: 2 + 2 + 4 = 8.

Задание 2. Решение задачи в процедуре MS EXCEL «Поиск решения»

1) Ввод данных. Переносим данные задачи в MS EXCEL. Результаты заполнения таблицы EXCEL можно увидеть на рис. 4.7.

 

В ячейках B4: G9 введены длины путей из исходных пунктов в пункты назначения.

Ячейки B12: G17 являются изменяемыми ячейками для нашей процедуры.

В ячейках B18: G18 находятся суммы значений соответствующих столбцов изменяемых ячеек. Так в ячейке B18 находится сумма ячеек B12: B17. Аналогично в ячейках:

в С18 находится сумма ячеек С12: С17;

в D18 находится сумма ячеек D12: D17;

в E18 находится сумма ячеек E12: E17;

в F18 находится сумма ячеек F12: F17;

в G18 находится сумма ячеек G12: G17.

 

Рис. 4.7.

 

В ячейках H12: H17 находятся суммы значений соответствующих строк изменяемых ячеек. Так в ячейке H12 находится сумма ячеек B12: G12. Аналогично в ячейках:

в H13 находится сумма ячеек B13: G13;

в H14 находится сумма ячеек B14: G14;

в H15 находится сумма ячеек B15: G15;

в H16 находится сумма ячеек B16: G16;

в H17 находится сумма ячеек B17: G17.

Целевая функция заносится в ячейку I3 и вычисляется по формуле «СУММПРОИЗВ (B4:G9; B12:G17)».

 

2) Заполнение окна процедуры «Поиск решения».

целевая функция: I3;

значение целевой функции: min;

изменяемые ячейки: B12: G17;

ограничения задачи:

B18: G18 = 1 и H12: H17 = 1;

B12: G17 0 (ячейки должны иметь положительные значения).

В окне «Параметры» установить «Линейная модель», что соответствует решению задачи симплекс-методом. Результаты заполнения окна показаны на рис. 4.8:

 

Рис. 4.8.

 

3) Выполнив процедуру «Поиск решения» в первоначальной таблице (см. рис. 4.8) получим следующие результаты (рис. 4.9).

 

Рис. 4.9.

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

 

1 → 2 → 6 → 7, длина = 8.

 

 

Контрольные вопросы

 

1. Для чего в задаче о нахождении наикратчайшего расстояния необходимо проводить преобразование матрицы?

2. С помощью каких методов и почему решается задача нахождения наикратчайшего расстояния?

3. Почему задачу нахождения наикратчайшего расстояния можно представить как транспортную задачу?

4. Какая процедура используется в EXCEL «Поиск решения» для решения задачи о нахождении наикратчайшего расстояния?

5. При частном решении матрицы каким образом обозначается случай, когда между соответствующими вершинами нет пути?

6. Что представляют собой буферные емкости и какой величины они должны быть?

7. Каким образом из задачи о нахождении наикратчайшего расстояния получают транспортную задачу, представляющую задачу о назначениях?


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.01 сек.)