Транспортная задача по критерию времени

-- Образуем список из ненулевых элементов текущей строки, и

проверяем его длину.

(if (length [ plan !! ((counter-1)*colCount + m) |

m ← [0‥colCount-1],

let curRow = rowMass !! (counter-1),

let curCol = colMass !! m,

((fromJust ◊ lookup (curRow, curCol) plan) ≠ 0) ||

((curRow ≡ i ) ∧ (curCol ≡ j))]) > 1

then findCycle i j colCount (counter + 1) plan

-- Если в строке не больше одного ненулевего элемента, то

удаляем строку.

else findCycle i j colCount 1 [ plan !! ((n-1)*colCount + (m-1))

|

n ← [1‥rowCount],

m ← [1‥colCount],

n ≠ counter])

else

-- Образуем список из ненулевых элементов текущего столбца, и

проверяем его длину.

(if (length [ plan !! (n*colCount + (counter - rowCount) - 1)

|

n ← [0‥rowCount-1],

let curRow = rowMass !! n,

let curCol = colMass !! (counter - rowCount - 1) ,

((fromJust ◊ lookup (curRow, curCol) plan) ≠ 0) ||

((curRow ≡ i) ∧ (curCol ≡ j))]) > 1

then findCycle i j colCount (counter + 1) plan

-- Если в солбце не больше одного ненулевего элемента, то

удаляем столбец.

else findCycle i j (colCount - 1) 1 [ plan !! ((n-1)*colCount +

(m-1)) |

n ← [1‥rowCount],

m ← [1‥colCount],

m ≠ (counter - rowCount)]))

listToArrayList :: [a] → Int → [((Int, Int), a)]

listToArrayList t colCount = [((i, j), (t !!((i-1)*colCount + j - 1))) |

i ← [1‥((length t) `div` colCount)], j ← [1‥colCount]]

16

-- | Функция рассчитывает потенциалы для опорного плана basePlan и матрицы

временных затрат t.

-- Возвращает пару списков: первый содержит вектор U, второй - V.

potentials :: [[Int]] → [Float] → ([(Int, Int)], [(Int, Int)]) → ([(Int,

Int)], [(Int, Int)])

potentials t basePlan pt =

let rC = (length t)

cC = (length ◊ head t)

in if ((length ◊ fst pt) ≥ rC) ∧ ((length ◊ snd pt) ≥ cC)

then pt

else potentials t basePlan

((fst pt) ⊕ [(n, (snd el) - t !! n !! (fst el) ) |

el ← snd pt,

n ← [0‥rC-1],

((last ◊ take ((fst el)+1) ◊ drop (n*cC) basePlan) ≠ 0.0) ∧

((lookup n ◊ fst pt) ≡ Nothing) ],

(snd pt) ⊕ [(m, (snd el) + t !! (fst el) !! m) |

m ← [0‥cC-1],

el ← fst pt,

((last ◊ take (m+1) ◊ drop ((fst el)*cC) basePlan) ≠ 0.0) ∧

((lookup m ◊ snd pt) ≡ Nothing) ])

-- | Функция проверяет модель и (если нужно) добавляет фиктивный пункт

потребления или производства.

checkForClosing :: [Int] → [Int] → ([Int], [Int])

checkForClosing _ [] = error "checkForClosing: Can't process an empty list!"

checkForClosing [] _ = error "checkForClosing: Can't process an empty list!"

checkForClosing a b

| (sum a) ≡ (sum b) = (a, b)

| (sum a) > (sum b) = (a, b ⊕ [sum a - sum b])

| otherwise = (a ⊕ [sum b - sum a], b)

getAddedVector :: [Int] → [Int] → Int

getAddedVector _ [] = error "getAddedVector: Can't process an empty list!"

getAddedVector [] _ = error "getAddedVector: Can't process an empty list!"

getAddedVector a b

| (sum a) < (sum b) = 1

| (sum a) > (sum b) = 2

| otherwise = 3

-- | Функция, реализующая метод северозападного угла, для построения опорного

плана.

northWesternCorner :: [Int] → [Int] → Int → [Int]

northWesternCorner [] _ _ = error "northWesternCorner: Can't process an empty

list!"

northWesternCorner _ [] _ = error "northWesternCorner: Can't process an empty

list!"

northWesternCorner a b c

| c > ((length a) * (length b)) = []

| otherwise = [me] ⊕ northWesternCorner

((take ((c - 1) `div` (length b)) a) ⊕ [ca - me] ⊕ (drop (((c - 1)

`div` (length b)) + 1) a))

((take ((c - 1) `mod` (length b)) b) ⊕ [cb - me] ⊕ (drop (((c - 1)

`mod` (length b)) + 1) b))

(c + 1)

where

ca = a !! ((c - 1) `div` (length b))

cb = b !! ((c - 1) `mod` (length b))

me = min ca cb

-- | Функция, преобразующая вырожденный план в невырожденный.

makeNonDegeneratePlan :: [Int] → Int → [Float]

makeNonDegeneratePlan basePlan cC = [

if (i < ((length basePlan) `div` cC) - 1) ∧ (j > 0) &&

((basePlan !! (i*cC + j)) ≡ 0) ∧ ((basePlan !! ((i + 1)*cC + (j - 1))) ≡

0) &&

((basePlan !! (i*cC + (j - 1))) ≠ 0) ∧ ((basePlan !! ((i + 1)*cC + j)) ≠

0)

17

then 0.000001

else fromInteger ◊ toInteger (basePlan !! (i*cC + j)) |

i ← [0‥((length basePlan) `div` cC)-1], j ← [0‥cC-1] ]

-- | Функция, строящая цепочку из элементов подматрицы текущего плана, которая

содержит цикл.

--

getCycle :: Int -- ↑ i - строка элемента, вводимого в цепочку

→ Int -- ↑ j - столбец элемента, вводимого в цепочку

→ Int -- ↑ сС - количество столбцов подматрицы

→ [((Int, Int), Float)] -- ↑ cycle - подматрица, содержащая цикл

→ [((Int, Int), Float)] -- ↑ возвращается цепочка из не

использованных на текущей

-- и предыдущих итерациях положительных

элементов

getCycle i j cC cycle =

let rC = ((length cycle) `div` cC) - 1

-- Ниже обнуляем текущий элемент цепочки в подматрице (чтобы не обращать больше

на него внимания).

mCycle = [ (if (i ≠ n+1) ∨ (j ≠ m+1)

then cycle !! (n*cC + m)

else (fst (cycle !! (n*cC + m)), 0.0)) |

n ← [0‥rC], m ← [0‥cC-1]]

-- Ищем индекс ненулевого элемента в той же строке, в которой находится вводимый

в цепочку элемент.

id = (findIndex (>0) [ snd (mCycle !! ((i-1)*cC + m)) | m ← [0‥cC-

1] ])

-- Проверка на отсутствие элементов, который можно ввести в цепочку

in if (length ◊ filter (>0) ◊ snd ◊ unzip mCycle) ≡ 0

then [cycle !! ((i-1)*cC + j - 1)]

else (if id ≠ Nothing

then [cycle !! ((i-1)*cC + j - 1)] ⊕ (getCycle i ((fromJust id)+1)

cC mCycle)

else let idi = findIndex (>0) [ snd (mCycle !! (n*cC + j-1)) | n ←

[0‥rC]]

in if idi ≠ Nothing

then ([cycle !! ((i-1)*cC + j-1)] ⊕ (getCycle ((fromJust idi)

+1) j cC mCycle))

else error "getCycle: no non-zero elements in this row or

coloumn!")

18

7. Руководство пользователя

7.1. Системные требования

Процессор: Pentium I или аналогичный AMD, 400 MHz и выше.

ОЗУ: 64 Мб и более.

ОС: Windows 98, 2000, ХР.

7.2. Описание возможностей

Данная программа  предназначена для решения транспортной задачи по

критерию времени  вариантом метода потенциалов, при  дополнительных

условиях, вводимых последовательно в процесс решения, а также

дооптимизации полученного решения по критерию стоимости.

Производится  оптимизация транспортных перевозок, тем самым

сокращаются время  перевозок и издержки.

В программе  есть "Инженерный" режим работы, с помощью которого

можно просмотреть  все этапы вычисления. Этот режим  предназначен для

специалистов  в данной области.

19

7.3. Основное окно программы

7.4. Главное меню программы

Главное меню программы  содержит пункты ｫФайлｻ, ｫРежимｻ,

ｫПомощьｻ.

В пункте ｫФайлｻ находится подпункт ｫВыходｻ, который используется

для завершения работы программы.

В пункте ｫРежимｻ находятся подпункты ｫОбычныйｻ и

ｫИнженерныйｻ.

20

ｫОбычныйｻ - основной режим, в котором представлены результаты

работы программы.

ｫИнженерныйｻ - режим проверки этапов вычисления. Предназначен для

специалистов.

В пункте ｫПомощьｻ находится подпункт ｫО программеｻ, при выборе

которого выводится  окно с информацией о программе.

7.5. Использование

Для начала работы с программой запустите файл program.exe.

7.5.1. Ввод данных и  результаты работы

Укажите в первом окне количество пунктов производства.

Затем нажмите  кнопку «OK».

В следующем  окне укажите количество пунктов  потребления. Также

нажмите кнопку «ОК».

Затем перед  вами появится окно (см. рисунок ниже) ввода названий

пунктов производства и количества производимого ими продукта. Укажите

названия производителей и количество продукта, которое они  производят.

Затем нажмите  кнопку «Продолжить» в этом окне.

Перед Вами появится аналогичное окно, только теперь Вам  нужно

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

Нажмите кнопку «Продолжить».

21

Теперь Вы увидите  новое окно. Здесь нужно ввести в первой колонке

стоимость доставки от производителя, имя которого указано  вверху окна

программы, в  пункты потребления, которые указаны слева, а во второй колонке