Автор работы: Пользователь скрыл имя, 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
существенные элементы матрицы Ck остаются равными нулю, а кроме того,
в нуль превращается и элемент c .
Если все элементы матрицы Ck1 окажутся неотрицательными, то
X k – оптимальный план, и на этом процесс заканчивается. В противном
случае переходят ко второму этапу.
Второй этап. Цель этого этапа – построить более экономичный план
X k1 . Выбирают наибольший по модулю отрицательный элемент матрицы
Ck1 . Пусть это элемент ci0 j0
k1=k10 . Строят цепочку из
положительных элементов плана, которая замыкается на xi0 j0 . После того,
как цепочка построена, в ней находят минимальный нечетный по порядку
следования элемент:
k1= min
0≤S
xi j1
k .
Прибавляют k1 ко всем четным элементам (по порядку следования)
цепочки и к элементу xi0 j0 и вычитают k1 из всех нечетных элементов.
Остальные элементы X k оставляют без изменения.
Новый план X k1 построен. Он является базисным, так как число его
ненулевых элементов не изменилось.
Пусть Lk – транспортные издержки, отвечающие плану X k . Тогда
новое значение целевой функции, отвечающее плану X k1 , находят по
соотношению Lk1=Lkk1⋅k1
Так как k10 и k10 , то Lk1Lk . Поэтому X k1 –
улучшенный опорный план.
Затем производят аналогично (k+2)-ю итерацию.
3.3. Вариант метода потенциалов, при дополнительных условиях,
вводимых последовательно в процессе решения задачи
Описание алгоритма.
1-й этап.
Шаг 1. Имеется опорный план X0 и матрица временных затрат T . В
матрице T=∣∣tij∣∣ отмечаем все элементы, соответствующие xij0 плана X0 ,
и находим среди них наибольший, который обозначим t' , т.е. t'=max {tij} для
всех xij0 .
Шаг 2. Все элементы матрицы T , которым соответствуют tij≥t'
блокируем, то есть заменяем реальные значения tij на произвольно большое
число M >>max{tij}. Получим матрицу T 1 .
Шаг 3. Для матрицы T 1 ищем, используя метод потенциалов,
оптимальное решение X опт
1 , минимизирующее функцию T=Σ
i =1
m
Σj
=1
n
tij⋅xij .
8
i-й этап (i >1).
Шаг 1. Если в найденном на предыдущем этапе опорном плане X опт
i−1
есть ненулевые перевозки, которые соответствуют заблокированным
элементам матрицы T1 , то решение найденное на предыдущем, (i-1)-ом,
этапе является оптимальным. Иначе в матрице Ti−1=∣∣tij∣∣ отмечаем все
элементы, соответствующие xij0 плана X опт
i−1 , и находим среди них
наибольший, который обозначим t' , т.е. t'=max {tij} для всех xij0 .
Шаг 2. Все элементы матрицы T i−1 , которым соответствуют tij≥t'
блокируем, то есть заменяем реальные значения tij на произвольно большое
число M >>max{tij}. Получим матрицу Ti .
Шаг 3. Для матрицы T i ищем, используя метод потенциалов,
оптимальное решение X опт
i , минимизирующее функцию T=Σ
i =1
m
Σj
=1
n
tij⋅xij .
4. Проверка достоверности полученных результатов.