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

     В этом методе строке i и столбцу j ставятся в соответствие числа U_i и V_j.  Для каждой базисной переменной Х_ij текущего решения потенциалы U_i и V_j   должны удовлетворять условию:

     U_i + V_j. =С_ij .                                                   (6)

     Оценки  для небазисных переменных определяются исходя из формулы:

      .                                                 (7)

     Если  условия не выполняются то, для включения в базис выбирается небазисная переменная, имеющая самое большое положительное значение. Для нахождения выводимой переменной строится замкнутый цикл. Цикл начинается и заканчивается выбранной небазисной переменной. Он состоит из последовательности вертикальных и горизонтальных отрезков, концами которых должны быть небазисные переменные. Построение данного цикла необходимо для того, чтобы после ввода новой переменной сбалансировать значения базисных переменных.

      Не  существенно, в каком направлении происходит обход цикла. Для каждого базисного переменного и соответствующей небазисной переменной можно построить только один цикл. После построения цикла вводимой небазисной переменной ставится в соответствие знака «+», далее базисным переменным, находящимся в узлах цикла ставятся поочередно знаки «-» и «+». Выводимой переменной считается базисная переменная, имеющая минимальное значение на местах со знаком «-». Далее к базисным переменным, находящимся на местах со знаком «+» прибавляется это значение, из переменных со знаком «-» – вычитается. Вводимой переменной присваивается найденное минимальное значение. После снова производятся оценки базисных и небазисных переменных и устанавливается, выполнены ли условия оптимальности. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      3 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ

      Рассмотрим  основные алгоритм решения задачи. Он состоит из следующего:

• нахождение начального базисного решения,
• из число небазисных переменных выделяем переменную вводимую в базис, проверяем условия оптимальности, если они удовлетворены то заканчиваем расчет, если нет – переходим к следующему шагу,
• из числа базисных переменных выделяем выводимую из базиса, находим новое базисное решение и возвращаемся ко второму шагу.

      Далее приведены основные шаги алгоритма и демонстрация их   на примере

 который представлен в данной курсовой работе как тестовый пример.

      Данные  приведены в таблице 1.

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

 

      Шаг 1. Находим начальное допустимое решение. Как уже сказано выше в  данной курсовой работе для отыскания начального решения будем   применять процедуру северо-западного угла (табл. 2).

      Таблица 2.

 

      И в данном случае мы имеем базисные переменные – X₁₁,, X₂₁, X₂₂, X₂₃, X₃₃ и X₃₄.

      И небазисные переменные - X₁₂, X₁₃, X₁₄, X₃₁, X₂₄ и X₃₂.

      Шаг 2. Выделить из числа небазисных переменных переменную, которую  введем в базис.

      Оценки  для базисных переменных:

      С₁₁=20

      С₂₁=10

      С₂₂=25

      С₂₃=25

      С₃₃=30

      С₃₄=20

      Обычно  полагают что U₁=0. Оценки для небазисных переменных   определяются в соответствии с отношением:

       

      

      

      

      

      

      Имеем переменную с наибольшим положительным  значением X₁₃=20,   которую и будем вводить в базис (табл. 3).

      Таблица 3. Построение цикла

 

        Далее переходим к «шагу 3».

      Шаг 3. Выбираем выводимую из базиса переменную из числа переменных   текущего базиса. Затем находим новое базисное решение и вернутся к «шагу 2».

      X₂₃ – выводим эту переменную из базиса.

        Таблица 4. Новое базисное решение

 

      Оценки  для базисных переменных:

      С₁₁=20

      С₁₃=15

      С₂₂=25

      С₂₃=25

      С₃₃=30

      С₃₄=20

      Оценки  для небазисных переменных:

      

      

      

      

      

      

      X₁₁ – выводим эту переменную из базиса, а X₃₁ – вводим в базис.

      Таблица 5. Новое базисное решение

 

      Данное  решение будет оптимальным.

      Оптимальное решение будет формулироваться  следующим образом:  общие расходы составят 4450 у.е., а маршруты будут таковы:

        1-ая фабрика поставила товар в 3-й склад   (1-й маршрут),

      2-ая  фабрика поставила товар в 1-й 2-й склады   (2-й маршрут),

      3-ая  фабрика поставила товар в  1-й 3-й 4-й склады   (3-й маршрут).

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

  Листинг программы представлен в приложении Б. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      4 РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

      Для входа в программу необходимо запустить файл Transport.exe. После чего на экране появится главное окно программы, изображенное на рисунке 1.

Рисунок 1 - Основное окно программы

      В данном окне пользователь может изменять и задавать значения в основных таблицах: «Спрос», «Предложение», «Фабрика» и «Склады».

      На  панели расположены основные элементы управления:

• ячейки для задания количества складов и фабрик,
• кнопка «Применить» используется для задания вводимых параметров,
• кнопка «По умолчанию» используется для задания значений по умолчанию,
• кнопка «Решить» используется для вычисления результата,
• кнопка «Задание» выводит окно с содержание задания к курсовой работе.

     Ответ пользователь может прочитать  из текстового поля.

              Применение  всех возможностей можно просмотреть  на рисунке 2.  

Рисунок 2 – Работа программы.

Для работы с  программой необходимы минимальные  аппаратные требования:

1) разрешение  экрана − 800*600;

2) цветопередача  − 16 бит;

4) память −  12 Mb;

6) Pentium II 400 MHz;

7) клавиатура;

8) мышь;

     9) Microsoft Windows 98 и выше; 
 
 
 
 
 
 

      ЗАКЛЮЧЕНИЕ

      В процессе работы были рассмотрены и  изучены такие понятия как  транспортная задача, основные методы решения транспортных задач, а так же был произведен расчет тестового примера. Для оптимизации расчетов и для уменьшении погрешностей вычислений был создан программный модуль в программной среде Delphi 7 под названием Transport.exe, который может использоваться как совместно с другими модулями, так и быть самостоятельным программным продуктом. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Ашманов С.А. Линейное программирование/ С.А Ашманов – М.: Наука. Главная редакция физико-математической литературы, 1981. - 340 с.
2. Вентцтель Е.С. Исследование операций. Задачи, примеры, методология: Учеб. пособие для студентов ВТУЗОВ – М. Высш. шк., 2001 – 208 с.
3. Бобровский С. Delphi 7/ С. Бобровский – СПб.: Питер, 2006. –736 с.
4. Исследование операций. /Под ред. Дж.Моудера и С.Элмаграби/, - М.: Мир, 1981.
5. Эддоус М., Стэнефильд Р. Методы принятия решений / Пер. с англ. Под ред. член-корр. РАН И.И. Елисеевой. – М.: Аудит. ЮНИТИ, 1997. – 590 с.