Министерство  образования и науки Республики Казахстан 

Восточно-Казахстанский  государственный технический университет

им. Д.М.Серикбаева 
 

Колледж ВКГТУ 
 

Отделение  Информационных технологий, управления и экономики 

Комиссия   Программирования и информатики 
 
 
 

Пояснительная записка 

к курсовому  проекту

по предмету «Моделирование производственных и  экономических процессов» 
 

Тема: «Решение транспортной задачи методом Фогеля» 
 

Специальность 3706002 «Программное обеспечение вычислительной техники и автоматизированных систем» 

Группа 06-КП-1 
 
 
 
 
 
 
 
 

Преподаватель        Осадчая Н.А. 

Учащаяся         Пампурина Т.В. 
 
 

г.Усть-Каменогорск

2009

 

Министерство  образования и науки Республики Казахстан 

Восточно-Казахстанский  государственный технический университет

им. Д.Серикбаева 

Колледж ВКГТУ 

Специальность 3706002 «Программное обеспечение вычислительной техники и автоматизированных систем» 

ЗАДАНИЕ НА КУРСОВОЕ ПРОЕКТИРОВАНИЕ 

Учащейся Пампуриной Татьяне Владимировне          

Группы  06-КП-1  курса   4    .           

Тема  «Решение транспортной задачи методом Фогеля» 

Выполнить следующие задания:

1. Написать программный продукт
2. Написать пояснительную записку, содержащую  следующие разделы:

       СОДЕРЖАНИЕ 

       ВВЕДЕНИЕ 

       1.АНАЛИТИЧЕСКАЯ  ЧАСТЬ

       1.1.Описание  и постановка задачи

       1.2. Описание и анализ математической  модели

       1.3.Обоснование выбора инструментальных средств

       2. ТЕХНОЛОГИЧЕСКАЯ ЧАСТЬ

       2.1. Назначение и цель создания

       2.2. Требования к системе

       2.2.1 Требования к функциям системы

       2.2.2.Требования  к интерфейсу пользователя

       2.2.3.Требования  к защите информации

       2.3.Перечень  и описание входных данных

       2.4.Руководство  к использованию и эксплуатации

       2.5.Результаты  экспериментальной проверки

       3.Охрана  труда и техника  безопасности

       ЗАКЛЮЧЕНИЕ

       СПИСОК  ИСПОЛЬЗУЕМой литературы

       ПРИЛОЖЕНИЯ 
 

Дата  выдачи задания     03.09.2008г.        

Срок  окончания разработки проекта  03.12.2008г.     

Задание выдал преподаватель _________ Осадчая  Н.А. 

 

Содержание 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

 

       Исторически математическая экономика началась с моделей простого и расширенного воспроизводства. В них отражались потоки денег и потоки товаров и продуктов. Это, например, модель Ф. Кенэ. Позднее эти модели подробно и более глубоко изучались в экономической кибернетике - здесь можно указать на работы О. Ланге. Рассмотрены схемы денежных и материальных потоков, обеспечивающих простое и расширенное воспроизводство, их идентификацию, модели математической статистики. Далее возникли концепции производственных функций, предельных и маргинальных значений, предельных полезностей и субъективных полезностей. Дальнейшее развитие - в рамках линейного и выпуклого программирования, выпуклого анализа, развитие тонких техник моделирования: имитационное моделирование, экспертные системы, нейронные сети.

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

 

1. Аналитическая часть

1. Описание  и постановка задачи

 

       Транспортная  задача – это задача о наиболее экономном плане перевозок однородного продукта из пунктов производства (станций отправления) в пункты потребления (станции назначения).

       Общая формулировка.

       Некоторый однородный продукт производится в  m пунктах производства A₁, А₂,…,A_m. Задан объём производства  a_i пункта A_i ( ). Произведённый продукт должен быть перевезён в n пунктов потребления B₁, B₂, …,B_n. Известен спрос b_j пункта B_j ( ). Заданы также транспортные издержки C_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт B_j. Требуется составить план перевозок, обеспечивающий при минимальных транспортных расходах удовлетворение спроса всех пунктов потребления за счёт продукта, произведённого во всех пунктах производства. 

2. Описание  и анализ математической модели

 

       В поставленной задаче обозначив через х_ij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю, сведём задачу в так называемую матрицу планирования, представленную в таблице 1.1 

Таблица 1.1

 

       Тогда математическая формулировка транспортной задачи сводится к минимизации линейной формы

                                                 

                                                    (1.1)

при ограничениях:

 ограничение по запасам:

                                                 

                                              (1.2)

ограничение по потребностям:

                                                                                                 (1.3) 

                                                           x_ij³0                                                           (1.4)                                     

       Различают задачи с закрытой моделью, когда Sa_i=Sb_j и открытой моделью, когда Sa_i¹Sb_j, т.е. баланс между запасами и потребностями отсутствует.

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

                                                                                                 (1.5)

       Если  , то вводят фиктивный (n+1)-й пункт назначения с потребностью и полагают c_i,n+1=0, .

       Если  , то вводят фиктивный (m+1)-й пункт отправления с запасами и принимают c_m+1,j=0, .

       Основные  особенности транспортной задачи:

1. ограничения заданы в виде равенств;
2. каждая неизвестная входит лишь в 2 уравнения;
3. коэффициенты при неизвестных равны 1.

       И хотя транспортная задача относится к задачам линейного программирования, в связи с вышеперечисленными особенностями для её решения созданы специальные алгоритмы.

       Решение транспортной задачи разбивается на 2 этапа:

1. Определение начального опорного плана.
2. Улучшение опорного плана.

       Опорный план называется невырожденным, если содержит ровно (m+n-1) перевозку. Если перевозок меньше, чем m+n-1, то это вырожденный опорный план.

       Для решения транспортной задачи используют различные методы, такие как: метод  северо-западного угла, метод минимальной  стоимости, метод Фогеля и метод потенциалов.

       В данном курсовом проекте для решения  транспортной задачи используется метод  минимальной стоимости, а оптимизация опорного плана производиться методом потенциалов.

       Был выбран метод потенциалов, т.к. этот метод производит улучшение опорного плана.  

       В методе Минимальной стоимости для  отыскания опорного плана необходимо просмотреть всю матрицу стоимостей и выбрать наименьшую стоимость. Если таких стоимостей окажется несколько, то выбрать ту из них, в столбце или строке которой имеется наибольшая стоимость. Разместить в соответствующую клетку наибольшее возможное количество груза, при этом строка или/и столбец выпадает из дальнейших расчётов. С оставшимися стоимостями произвести те же действия. По окончании расчётов проверить правильность размещения перевозок в соответствии с отграничениями по запасам и по потребностям, посчитать стоимость перевозки. 

       Метод потенциалов можно применить  только к невырожденному опорному плану. Если план вырожден, то его можно дополнить необходимым количеством нулевых перевозок.

       Алгоритм  метода потенциалов. 

1. Любым методом  построить опорный план, убедиться, что он невырожденный.
2. Каждому поставщику A_i поставить в соответствие некоторый потенциал u_i, а каждому потребителю B_j – потенциал p_j.
3. Для каждой перевозки опорного плана составить сумму потенциалов, приравнять её к стоимости перевозки: u_i+ p_j=с_ij. Таким образом будет получена система (m+n-1) уравнений с (m+n) неизвестными. Такая система имеет бесконечное множество решений.
4. Выделить одно из возможных решений системы, присвоив любому из неизвестных произвольное значение. Из полученных значений потенциалов составить матрицу :