Автор работы: Пользователь скрыл имя, 19 Января 2012 в 20:21, курсовая работа
Имеется m пунктов отправления, в каждом из которых сосредоточено
определенное количество единиц однородного продукта, предназначенного к
отправке: в первом пункте имеется a1 единиц этого продукта, во втором - a2
единиц, в i− м пункте ai единиц, и, наконец, в m− м пункте am единиц
продукта. Этот продукт следует доставить в n пунктов назначения
(потребления), причем в первый пункт назначения следует доставить b1 единиц
продукта, во второй - b2 единиц, в j− й пункт b j единиц, и, наконец, в n− й
пункт bn единиц продукта.
1.Постановка задачи........................................................................................3
2.Обоснование математической модели.......................................................4
3.Краткие сведения о методе решения задачи..............................................5
3.1.Метод северо-западного угла...................................................................5
3.2.Метод потенциалов...................................................................................6
3.3.Вариант метода потенциалов, при дополнительных условиях,
вводимых последовательно в процессе решения задачи.........................................8
4.Проверка достоверности полученных результатов..................................9
5.Алгоритм решения задачи.........................................................................10
6.Листинг фрагмента программы, реализующего алгоритм решения
задачи.........................................................................................................................11
7.Руководство пользователя.........................................................................19
7.1.Системные требования...........................................................................19
7.2.Описание возможностей.........................................................................19
7.3.Основное окно программы.....................................................................20
7.4.Главное меню программы......................................................................20
7.5.Использование.........................................................................................21
7.5.1.Ввод данных и результаты работы.....................................................21
7.5.2.Использование инженерного режима.................................................24
8.Решение задачи курсовой работы на ПЭВМ по исходным данным
индивидуального варианта.......................................................................................25
9.Список использованной литературы........................................................28
Предварительный этап. С помощью известного метода (например
северо-западного угла или минимального элемента) определяют начальный
опорный план X 0 и вычисляют предварительные потенциалы
v j
0 j=11n ,ui
0 i=11m .
Вычисление
предварительных потенциалов
найденному опорному плану X 0 строят схему перевозок Т-задачи из
основных коммуникаций плана. Основные коммуникации Pij плана
6
X 0=∣xij
0∣ - это те, которым отвечают базисные компоненты плана, т.е.
коммуникации для которых xij
0 0 . Далее образуют следующие множества:
J 1 - множество индексов всех пунктов B j , которые связаны с пунктом
A1 основными коммуникациями; I 1 - множество индексов тех пунктов
Ai , которые связаны основными коммуникациями с множеством J 1 ; J 2
– множество пунктов B j , которые связаны основными коммуникациями с
множеством I 1 и т.д. Образование таких множеств I k продолжаем до тех
пор, пока не получим пустое множество.
Поскольку на выполнение
условий оптимальности
лишь разности v j−ui , то за начало отсчета (нуль) можно принять потенциал
любого из пунктов.
Полагаем для определенности u1
0=0 и вычислим систему
потенциалов относительно A1 . Тогда v j
0=c1ju1
0=c1j , где j∈J 1 . Затем
по значениям v j
0 j∈J 1 определяем потенциалы пунктов Ai i∈I 1 :
ui
0=v j
0−cij j∈J 1, i∈I 1 .
Аналогично вычисляем потенциалы v j
0 j∈J 2 :
v j
0 =cijui
0
(для i∈I 1 ) и т.д. После того как потенциалы всех пунктов найдены, строим
матрицу C1=∣∣cij−v j
0 −ui
0∣∣, i=11m, j=11n.
Очевидно, позиции матрицы C1 , отвечающие базисным элементам
плана X 0 , будут заняты нулями. Если матрица C1 не содержит
отрицательных элементов, то X 0 – оптимальный план. В противном случае
X 0 – неоптимальный план, который может быть улучшен. Тогда переходим
к выполнению однотипных итераций.
(k+1)-я итерация. Каждая итерация, кроме первой, где отсутствует
первый этап, состоит из двух этапов. Предположим, что уже проведено k
итераций (k=1,2,…), в результате которых получен план X k и
вспомогательная матрицу Ck . Цель (k+1)-й итерации - построение матрицы
Ck1 , а также либо установление оптимальности плана X k , либо
нахождение более экономичного плана X k1 .
Первый этап. Вычисляют матрицу Ck1 . Преобразвание матрицы
Ck в матрицу Ck1 состоит в следующем. Выбирают наибольший по
модулю отрицательный элемент Ck . Пусть это элемент c
k =k k0 .
Тогда вычеркивают (или выделяют) строку , в которой он содержится.
Просматривают эту строку и отыскивают множество существенных его
элементов. X k -существенными элементами называют те элементы cij
k =0 ,
которые отвечают базисным элементам плана X k , т.е. для которых xij
k0 .
Вычеркивают столбцы, которые содержат эти элементы. Далее просматривают
вычеркнутые столбцы и ищут в них новые существенные элементы, которые
лежат в строках отличных от уже вычеркнутых ранее. Если такие элементы
имеются, то вычеркивают строки, в которых они содержатся. Процесс
выделения продолжают до тех пор, пока очередное множество новых
существенных элементов не окажется пустым. Поскольку каждые строка и
7
столбец не могут быть выделены дважды, то весь процесс заканчивается не
более чем за l =m+ n – 1 шагов. Далее строят матрицу Ck1 . Для этого
величину k прибавляют ко всем элементам выделенных строк и вычитают
из элементов всех выделенных столбцов матрицы Ck . При этом все