Решение транспортной задачи

Рассмотрим следующую транспортную задачу. Для строительства четырех объектов используется кирпич, изготавливаемый на трех заводах. Ежедневно каждый из заводов может изготовить 100, 150 и 50 условных единиц кирпича (предложение поставщиков). Потребности в кирпиче  на каждом из строящихся объектов ежедневно составляют 75, 80, 60 и 85 условных единиц (спрос потребителей). Тарифы перевозок одной условной единицы кирпича с каждого из заводов к каждому из строящихся объектов задаются матрицей транспортных расходов С.

 

Требуется составить такой план перевозок кирпича к строящимся объектам, при котором общая стоимость перевозок будет минимальной.

Для решения транспортной задачи на персональном компьютере с использованием EXCEL необходимо:

1. Ввести исходные данные в ячейки рабочего листа EXCEL;

2. Разметить блоки ячеек на рабочем листе EXCEL, необходимые для моделирования объемов перевозок, а также для формирования элементов математической модели и целевой функции;

3. Сформировать на рабочем листе EXCEL элементы математической модели и целевую функцию;

4. Настроить программу " Поиск решения" и выполнить ее.

Ввод исходных данных

Исходными данными для решения транспортной задачи являются:

• матрица транспортных расходов
• предложение поставщиков
• спрос потребителей

Напомним, что для ввода данного в ячейку рабочего листа EXCEL необходимо:

1. Селектировать ячейку;

2. Набрать вводимое данное на клавиатуре;

3. Нажать клавишу Enter.

Для наглядности блоки ячеек с введенными данными желательно обвести рамками (см. п. 4.5.).

Рабочий лист EXCEL с введенными исходными данными для решения транспортной задачи  показан на рис.1.

 

рис.1.

Разметка блоков ячеек рабочего листа

 

Кроме исходных данных на рабочем листе EXCEL для решения транспортной задачи необходимо предусмотреть:

1. Блок ячеек "Матрица перевозок", в котором будут моделироваться объемы перевозок;

2. Блок ячеек "Фактически реализовано", в котором будет моделироваться фактическая реализация продукции;

3. Блок ячеек "Фактически получено", в котором будет моделироваться фактическое удовлетворение спроса;

4. Блок ячеек "Транспортные расходы по потребителям", в котором будут подсчитываться транспортные расходы по каждому потребителю;

5. Ячейку "Итого расходы", в которой будут моделироваться итоговые транспортные расходы по всем потребителям (целевая ячейка).

Для наглядности указанные блоки ячеек целесообразно обвести рамками. Выполните эту операцию, называемую разметкой блоков ячеек, в соответствии п. 4.5.

Рабочий лист  EXCEL с размеченными блоками ячеек показан на рис.5.2.

Теперь в этих блоках ячеек можно формировать элементы математической модели и целевую функцию.

рис.2.

Формирование элементов математической модели

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

, - фактически реализовано  i-ым  поставщиком ;

, - фактически получено  j-ым  потребителями .

Для нашей задачи m=3, n=4.

Рассмотрим процесс формирования этих сумм на рабочем листе EXCEL.

Вначале сформируем ,  в блоке "Фактически реализовано".

 

1. Заполните ячейки блока "Матрица перевозок" (С14:F16) числом 0,01.

2. Селектируйте первую ячейку блока "Фактически реализовано" (ячейка I14);

3. Наведите курсор на кнопку  - автосуммирование и щелкните левой клавишей мыши;

4. Нажмите клавишу Delete;

5. Селектируйте первую строку блока "Матрица перевозок" (строка С14:F14);

6. Нажмите клавишу Enter;

7. Скопируйте формулу=СУММ(С14:F14) из первой ячейки блока "Фактически реализовано" на все остальные ячейки этого блока.

Сформируем теперь  - в блоке "Фактически получено".

Для этого выполните следующие действия:

1. Селектируйте первую ячейку блока "Фактически получено" (ячейка С18);

2. Наведите курсор на кнопку  - автосуммирование и щелкните левой клавишей мыши;

3. Нажмите клавишу Delete;

4. Селектируйте первый столбец блока "Матрица перевозок" (Столбец С14:C16);

5. Нажмите клавишу Enter;

6. Скопируйте формулу=CУММ(С14:С16) из первой ячейки блока "Фактически получено" на остальные ячейки этого блока.

4 Формирование целевой функции

Для формирования целевой функции введем вначале формулы, отражающие транспортные расходы по каждому потребителю, т.е. формулы:

 в ячейки блока “Транспортные расходы по потребителям”

Для ввода этих формул выполните следующие действия:

1. Селектируйте первую ячейку блока “Транспортные расходы по потребителям” (ячейка С21);

2. Наведите курсор на кнопку  - автосуммирование и щелкните левой клавишей мыши;

3. Нажмите клавишу “Delete ”;

4. Селектируйте первый столбец блока “Матрица Транспортных расходов” (столбец С6:С8);

5. Нажмите клавишу *;

6. Селектируйте первый столбец блока “Матрица превозок” (столбец С14:С16);

7. Активируйте строку формул, наведя на неё курсор и щелкнув затем левой клавишей мыши;

8. Нажмите одновременно три клавиши: “CTRL”+“SHIFT”+“ENTER”;

9. Скопируйте формулу {=СУММ (С6:С8*С14:С16)} в остальные ячейки блока “Транспортные расходы по потребителям”;

Сформируем теперь целевую функцию транспортной задачи, выражаемую формулой , в ячейку “Итого расходы”. Для этого:

Селектируйте ячейку “Итого расходы” (ячейка I21);

1.  Наведите курсор на кнопку  - автосуммирование и щелкните левой клавишей мыши;

2.  Нажмите клавишу “Delete”;

3.  Селектируйте блок ячеек “Транспортные расходы по потребителям”(С21:F21);

4.  Нажмите клавишу “Enter”;

После формирования элементов математической модели и целевой функции транспортной задачи рабочий лист EXСEL примет вид, показанный на рис.3.

Теперь можно приступить к настройке программы “Поиск решения”.

рис.3.

  5.5 Настройка программы Поиск решения

 Для настройки программы “Поиск решения” на решение транспортной задачи выполните следующие действия:

1. Селектируйте целевую ячейку “Итого расходы” (ячейка I21);

2. Установите курсор в строке главного меню на пункте “Сервис” и щелкните левой клавишей мыши;

3. Установите курсор на пункт "Поиск решения" меню "Сервис", щелкните левой клавишей мыши и убедитесь, что в поле “Установить целевую ячейку” окна диалога программы “Поиск решения” указана ячейка $I$21 (см. рис.4)

рис.4.

 

4. Установите курсор на переключатель “Равной Минимальному значению” и щелкните левой клавишей мыши;

5. Установите курсор в поле “Изменяя ячейки” и щелкните левой клавишей мыши;

6. Селектируйте блок ячеек “Матрица первозок” (блок С14:F16);

7. Установите курсор на кнопку “Добавить” и щелкните левой клавишей мыши;

Появившееся окно диалога команды “Добавление ограничения” показано на рис.5.5.

рис.5.

8. Селектируйте блок ячеек “Фактически реализовано” (блок I14:I16);

9. Убедитесь, что оператор сравнения <=уже выбран;

10. Установите курсор на поле “Ограничение”и щелкните левой клавишей мыши;

11. Селектируйте блок ячеек “Предложение поставщиков” (блок I6:I8) и убедитесь, что окно диалога команды “Добавление ограничения” имеет вид, показанный на рис.6.

рис.6.

12. Установить курсор на кнопку “Добавить” и щелкните левой клавишей мыши;

13. Селектируйте блок ячеек “Фактически получено” (блок С18:F18);

14. Установите курсор на стрелку прокрутки значений оператора сравнения и щелкните левой клавишей мыши;

15. Установите курсор на значение  >=  (больше или равно) и щелкните левой клавишей мыши;

16. Установите курсор на поле “Ограничение” и щелкните левой клавишей мыши;

17. Селектируйте блок ячеек “Спрос потребителей” (блок С10:F10) и убедитесь, что окно диалога команды “Добавление ограничения” имеет вид, показанный на рис.7.

рис.7.

 

18. Установите курсор на кнопку “Добавить” и щелкните левой клавишей мыши;

19. Селектируйте блок ячеек “Матрица перевозок” (блок С14:F16);

20. Установите курсор на стрелку прокрутки значений оператора сравнения и щелкните левой клавишей мыши;

21. Установите курсор на значение  >=  (больше или равно) и щелкните левой клавишей мыши;

22. Установите курсор на поле “Ограничение” и щелкните левой клавишей мыши;

23. Наберите на клавиатуре цифру 0 и убедитесь, что окно диалога команды “Добавление ограничения” имеет вид, показанный на рис.8.

рис.8.

 

24. Установите курсор на кнопку “Добавить” и щелкните левой клавишей мыши;

25. Установите курсор на кнопку "Отмена" и щелкните левой клавишей мыши;

26. Убедитесь, что появившееся окно программы “Поиск решения” имеет вид, показанный на рис.9.

рис.9.

 

27. Установите курсор на кнопку “Параметры” и щелкните клавишей мыши;

28. В появившемся окне диалога “Параметры поиска решения” (см. рис.5.10) установите курсор на флажок “Линейная модель” и щелкните левой клавишей мыши;

29. Установите курсор на кнопку “ОК” и щелкните левой клавишей мыши;

30. В появившемся окне "Поиск решения" установите курсор на кнопку "Выполнить" и щелкните левой клавишей мыши.

рис.10.

31. Убедитесь, что на рабочем листе EXCEL в блоке "Матрица перевозок" появляется решение транспортной задачи, показанное на рис.5.11.

рис.11.

В появившемся диалоговом окне "Результаты поиска решения" установите курсор на переключатель "Восстановить исходные значения" и щелкните левой клавишей мыши. Для завершения расчетов щелкните на кнопке ОК. (см. рис.12).

 

рис.12.

 

Замечание. Выполнение пунктов 19-24 можно заменить установкой флажка "Неотрицательные значения" в окне диалога "Параметры поиска решения".