Автор работы: Пользователь скрыл имя, 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
д) удельные стоимости могут быть назначены из диапазона 2≤cij≤38 ;
е) значения времени перевозок могут быть назначены из диапазона
1≤tij≤35 .
2. Обоснование математической модели
Имеется m пунктов производства ( A1 , A2 , ... , Am ) и n пунктов
потребления ( B1 , B2 ,... , Bn ). В пункте Ai производится ai единиц
продукта ( i=11m ), а в пункте B j потребляется b j единиц этого же
продукта ( j=11n ).
Пусть
сij - стоимость доставки из i -го пункта производства в j -ый пункт
потребления (элементы матрицы C );
tij - время, которое требуется для перевозки продукта из i -го пункта
производства в j -ый пункт потребления (элементы матрицы T );
xij - количество единиц продукта, которое нужно перевезти из i -го
пункта производства в j -ый пункт потребления (элементы матрицы X ).
Необходимо получить такие значения переменных xij ( i=11m ,
j=11n )(то есть составить такой план перевозок), что выполнялись бы
следующие условия:
Σj
=1
n
xij=ai , i=11m; (1)
Σi
=1
m
xij=b j , j=11n (2)
- и целевая функция T=max
xij0
tij ,i=11m , j=11n достигала бы минимума.
Условие (1) означает, что из каждого пункта производства должен быть
вывезен весь продукт. Условие (2) означает, что потребности каждого пункта
потребления в этом продукте должны быть удовлетворены.
Целевая функция T=max
xij0
tij ,i=11m , j=11nmin указывает на то,
что нам необходимо минимизировать время самой длительной ненулевой
перевозки.
Условия (1) и (2) можно объединить и представить в виде
Σi
=1
m
ai=Σ
j =1
n
b j . (3)
4
Условие (3) называется условием баланса и означает, что объем
производства должен быть равен объему потребления. Если данное условие не
выполняется, то транспортная модель в этом случае называется открытой и
транспортная задача не разрешима. Для того, чтобы все-таки решить такую
задачу, её приводят к закрытой модели введением фиктивного пункта
производства Am1 с объемом производства am1=Σ
j =1
n
b j−Σ
i=1
m
ai (если
Σi
=1
m
aiΣ
j=1
n
b j ) или фиктивного пункта потребления Bn1 с объемом
потребления bn1=Σ
i=1
m
ai−Σ
j=1
n
b j (если Σ
i =1
m
aiΣ
j =1
n
b j ). В первом случае
транспортные издержки и временные затраты сm1, j и tm1, j принимают
равными M , где M≫cij и M≫tij ,i=11m, j=11n . Во втором случае
транспортные издержки и временные затраты сi ,n1 и ti ,n1 также
принимают равными M , где M≫cij и M≫tij ,i=11m, j=11n . В