Транспортна задача

 

Самый тяжёлый нуль находится в  ячейке (1,7), но если удалить строку 1 в шестом столбце не останется  ни одного пути, следовательно, подмножество решений (7,5) надо разбить на и .

Таблица 2.15 Преобразованная матрица

lij	1	2	3	4	7
2	85	∞	0	5	55
3	∞	0	∞	5	∞
4	∞	5	0	∞	∞
6	∞	∞	∞	∞	0
8	∞	0	∞	0	50

 

Четвёртая итерация

Выполним редукцию столбцов, так как редукцию строк проводить не имеет смысла:

Таблица 2.16 Редукция столбцов в четвёртой  итерации

lij	1	2	3	4	7	ci
2	0	∞	0	5	55	0
3	∞	0	∞	5	∞	0
4	∞	5	0	∞	∞	0
6	∞	∞	∞	∞	0	0
8	∞	0	∞	0	50	0
qj	85	0	0	0	0	H=85

Проверка:

В полученной таблице можно выбрать  по только по одному нулевому элементу в каждых строке и столбце, следовательно  получено оптимальное решение: это элементы (2, 1), (3, 2), (4, 3), (6, 7), (8, 4).

Ответ:

Оптимальный маршрут состоит из следующих звеньев или пар пунктов: (1, 6), (6, 7), (7, 5), (5, 8), (8, 4), (4, 3), (3, 2), (2, 1), или

Сиэтл→ Сан-Франциско→ Солт-Лейк-Сити→  Хьюстон→ Сент-Луис→Мемфис→ Нью-Йорк→  Чикаго→ Сиэтл. Он является ориентированным  графом с длиной маршрута

 

 

3. Спецификация программного  продукта

Созданный программный  продукт, получивший название «CIRCLE», предназначен для решения транспортных задач  на замкнутые маршруты по методу Литтла.

Интерфейс программы  представлен на рисунке 3.1:

Рисунок 3.1 Интерфейс программы «CIRCLE»

 

На главной форме  расположены главное меню, содержащая все доступные функции программы  в виде пунктов, разбитых по категориям, панель инструментов, на которую в  виде кнопок вынесены наиболее часто  используемые команды, и панель состояния для отображения времени, индикации состояния клавиш Num Lock, Caps  Lock, Scroll Lock а также для вывода подсказок, облегчающих работу. Имеется возможность конфигурирования панели инструментов по собственному вкусу путём помещения/удаления каких-либо команд.

На дочерней форме  находится сетка StringGrid, которая служит для задания программе исходной матрицы расстояний/стоимости перехода. Размерность сетки устанавливается через пункт меню Решение→Кол-во узлов, либо по нажатии на соответствующую кнопку панели инструментов.

Редактирование сетки  осуществляется двойным щелчком  на необходимой ячейке, в результате чего выскакивает окно ввода, представленное на рисунке 3.2:

 

    Рисунок 3.2 Окно редактирования ячейки

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

Задание исходной матрицы  также может быть осуществлено путём  загрузки оной из заранее сохранённого файла. Для этого нужно выбрать пункт меню Файл→Сохранить как…, либо нажать соответствующую клавишу на панели инструментов. В появившемся диалоговом окне надо выбрать нужный файл.

Аналогичным образом  выполняется и сохранение матрицы  в формате *.MyFile.

Нажатие на кнопку (Решение→Вычислить) приводит к появлению окна с результатами вычислений (рисунок 3.3):

Рисунок 3.3 Окно вывода результата

Если же программе  не удаётся найти ни одного Замкнутого маршрута (Матрица задана некорректно) выводится (рисунок 3.4).

Рисунок 3.4 Окно вывода информации о некорректном вводе исходных данных

 

Заключение

Результатом выполнения курсовой работы явилось создание программы  для решения транспортной задачи на замкнутые маршруты

В процессе работы были поставлены и выполнены следующие цели:

• Построена математическая модель задачи
• Рассмотрена классификация транспортных задач
• Рассмотрены методы их решения
• Написана и отлажена программа для решения транспортных задач на замкнутые маршруты
• В дальнейшем планируется модифицировать данный программный продукт, введя в него и дополнив следующие функции:
• Расширение команд главного меню
• Возможность отображения результатов всех итераций
• Возможность записи в файл всех этапов решения и окончательного маршрута
• Повышение точности вычислений
• Более наглядное представление исходный данных за счёт замены пустых узлов на символ бесконечности
• Возможность решения всех видов транспортных задач

 

 

 

 

 

Список использованной литературы

1. Барановская Т.П., Лойко В.И., Семенов М.И., Трубилин А.И. Архитектура компьютерных систем и сетей: Учебное пособие. – М.: Финансы и статистика, 2003.
2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология: учебное пособие для вузов. – 4-е издание, стереотип. – М.: Дрофа, 2006.
3. Гмурман В.Е. Теория вероятностей и математическая статистика: Учебное пособие для вузов. – 8-е издание, стер. – М.: Высшая школа, 2002.
4. Грешилов А.А. Математические методы принятия решений: Учебное пособие для вузов. – Издательство МГТУ им. Н.Э. Баумана, 2006.
5. Грешилов А.А. Прикладные задачи математического программирования: Учебное пособие. – 2-е издание. – М.: Логос, 2006.
6. Катулев А.Н., Северцев Н.А. Математические методы в системах поддержки принятия решений: Учебное пособие. – М.: Высшая школа, 2005.
7. Коробов П.Н. Математическое программирование и моделирование экономических процессов. Учебник. Изд. Третье перераб. и доп. – СПб.: ООО «Издательство ДНК», 2006.
8. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах: Учебное пособие. – М.: Высшая школа, 2002.

 

Приложение. Листинг программы CIRCLE

 

1 Исполняемый файл (course.dpr)

program course;

uses

  Forms,

  main in 'Model\main\main.pas' {Главная  форма},

  uOption in 'Model\uOption\uOption.pas' {Форма настройки сетки},

  uAboutBox in 'Model\uAboutBox\uAboutBox.pas' {Форма  копирайта},

  param in 'Model\param\param.pas',

  uQuery in 'Model\uQuery\uQuery.pas' {Редактор  ячейки};

{$R Resourses\course.RES}

begin

  Application.Initialize;

  Application.Title := 'Результат';

  Application.CreateForm(TMainForm, MainForm);

  Application.CreateForm(TfOption, fOption);

  Application.CreateForm(TAboutBox, AboutBox);

  Application.CreateForm(TParamDlg, ParamDlg);

  Application.CreateForm(TfQuery, fQuery);

  Application.Run;

end.

 

2. Главная форма

  2.1 Файл main.dfm

object MainForm: TMainForm

  Left = 260

  Top = 172

  Width = 588

  Height = 441

  BorderWidth = 5

  Caption =

    '.:: '#1055#1088#1086#1075#1088#1072#1084#1084#1072' '#1076#1083#1103' '#1088#1077#1096#1077#1085#1080#1103' '#1090#1088#1072#1085#1089#1087#1086#1088#1090#1085#1099#1093' '#1079#1072#1076#1072#1095' '#1085#1072' '#1079#1072#1084#1082#1085#1091#1090#1099#1077' '#1084#1072#1088#1096#1088#1091 +

    #1090#1099' ::.'

  Color = clBtnFace

  Font.Charset = DEFAULT_CHARSET

  Font.Color = clWindowText

  Font.Height = -11

  Font.Name = 'MS Sans Serif'

  Font.Style = []

  OldCreateOrder = False

  Position = poScreenCenter

  OnCloseQuery = FormCloseQuery

  OnCreate = FormCreate

  PixelsPerInch = 96

  TextHeight = 13

  object Splitter1: TSplitter

    Left = 0

    Top = 24

    Width = 570

    Height = 3

    Cursor = crVSplit

    Align = alTop

    Beveled = True

  end

  object WaightGrid: TStringGrid

    Left = 0

    Top = 53

    Width = 570

    Height = 330

    Hint = #1044#1074#1086#1081#1085#1086#1081' '#1097#1077#1083#1095#1086#1082' - '#1088#1077#1076#1072#1082#1090#1080#1088#1086#1074#1072#1090#1100' '#1103#1095#1077#1081#1082#1091

    Align = alClient

    DefaultColWidth = 70

    DefaultRowHeight = 26

    Font.Charset = RUSSIAN_CHARSET

    Font.Color = clGreen

    Font.Height = -13

    Font.Name = 'Tahoma'

    Font.Style = [fsBold]

    ParentFont = False

    TabOrder = 0

    OnDblClick = WaightGridDblClick

    OnSelectCell = WaightGridSelectCell

  end

  object ActionMainMenuBar1: TActionMainMenuBar

    Left = 0

    Top = 0

    Width = 570

    Height = 24

    UseSystemFont = False

    ActionManager = ActionManager1

    Caption = 'ActionMainMenuBar1'

    ColorMap.HighlightColor = clWhite

    ColorMap.BtnSelectedColor = clBtnFace

    ColorMap.UnusedColor = clWhite

    Font.Charset = DEFAULT_CHARSET

    Font.Color = clWindowText

    Font.Height = -11

    Font.Name = 'Tahoma'

    Font.Style = []

    Spacing = 0

  end

  object ActionToolBar1: TActionToolBar

    Left = 0

    Top = 27

    Width = 570

    Height = 26

    ActionManager = ActionManager1

    Caption = 'ActionToolBar1'

    ColorMap.HighlightColor = clWhite

    ColorMap.BtnSelectedColor = clBtnFace

    ColorMap.UnusedColor = clWhite

    Spacing = 0

  end

  object StatusBar: TStatusBar

    Left = 0

    Top = 383

    Width = 570

    Height = 19

    BiDiMode = bdRightToLeft

    Panels = <

      item

        BiDiMode = bdLeftToRight

        ParentBiDiMode = False

        Width = 300

      end

      item

        Width = 50

      end

      item

        Width = 50

      end

      item

        Width = 50

      end

      item

        Alignment = taRightJustify

        BiDiMode = bdLeftToRight

        ParentBiDiMode = False

        Width = 50

      end>

    ParentBiDiMode = False

  end

  object ImageList1: TImageList

    Left = 600

    Top = 400

  end

  object ActionManager1: TActionManager

    ActionBars = <

      item

        Items = <

          item

            Items = <

              item

                Action = Action3

                ImageIndex = 7

              end

              item

                Action = Action4

                ImageIndex = 9