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

В общем случае проверка результатов, полученных после  выполнения

очередной итерации, осуществляется следующим образом:

1) вычисляются  значения Lk1

1 =Lkk1⋅k1 и Lk1

2 =Σ

i=1

m

Σj

=1

n

cij⋅xij

 k1 ,

где Lk1

1 , Lk1

2 - значения целевой функции на текущей итерации,

вычисленные разными  способами;

Lk - значение целевой функции на предыдущей итерации

итерации;

k1 - количество товара разгружаемой перевозки;

k1 - минимальное отрицательное значение матрицы Ck1 ;

xij

 k1 - элементы плана перевозок, полученного на текущей итерации;

сij - элементы матрицы материальных затрат (временных).

2) Если Lk1

1 =Lk1

2  , то программа приступает к выполнению

следующей итерации. В противном случае программа  выдает сообщение об

ошибке.

Также в программе  есть «инженерный режим», используя  который можно

посмотреть  результаты вычислений после каждой итерации.

9

5. Алгоритм решения  задачи.

1. Проверка  выполнения условия баланса.

2. Если условие  баланса не выполняется, то  вводим фиктивный пункт

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

3. Построение  опорного плана.

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

5. Поиск наибольшего  времени перевозок среди существующих  в

опорном плане.

6. Блокировка  элементов матрицы временных  затрат, которые больше

максимального времени перевозок, найденного на 4-м  или 10-м этапе.

7. Вычисление  потенциалов.

8. Вычисление оценочной матрицы.

9. Построение  нового плана по полученной  оценочной матрице. Во время

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

плана.

10. Выполнение  следующих итераций метода потенциалов.  Получение

оптимального  плана.

11. Если в  полученном решении существуют  перевозки на

заблокированных на 5-м этапе местах, то происходит переход к 11 этапу. Иначе

осуществляется  поиск наибольшего времени среди  существующих в

полученном  плане перевозок и переход  к 5-му этапу.

12. Полученный план дооптимизируется по критерию стоимости.

10

6. Листинг фрагмента  программы, реализующего  алгоритм решения

задачи

module Prog where

import GHC.Ptr

import Maybe

import BaseOperations

import Foreign.C

import Foreign.Marshal.Array

foreign export ccall "getplan" getPlan :: CInt → CInt → CInt → Ptr CInt → IO

(Ptr CFloat)

getPlan :: CInt → CInt → CInt → Ptr CInt → IO (Ptr CFloat)

getPlan rC cC eC ptr

= do

aData ← peekArray (fromIntegral eC) ptr

let rCount = fromIntegral rC

cCount = fromIntegral cC

cData = map fromIntegral aData

a = take rCount cData

b = take cCount ◊ drop rCount cData

tT = take (rCount*cCount) ◊ drop (rCount+cCount) cData

cT = drop (rCount*cCount+rCount+cCount) cData

t = [[ tT !! (i*cCount + j) |

j ← [0‥cCount-1] ] |

i ← [0‥rCount-1] ]

c = [[ cT !! (i*cCount + j) |

j ← [0‥cCount-1] ] |

i ← [0‥rCount-1] ]

-- Проверка баланса и добавление фиктивного пункта

mx = checkForClosing a b

aV = getAddedVector a b

mColCount = if aV ≡ 2

then (cCount + 1)

else cCount

mRowCount = if aV ≡ 1

then (rCount + 1)

else rCount

-- Строим опорнный план

basePlan = northWesternCorner (fst mx) (snd mx) 1

prd = 2 * sum [ t !! i !! j | i ← [0‥rCount-1], j ← [0‥cCount-1]]

maxi = maximum [ t !! i !! j |

i ← [0‥rCount-1], j ← [0‥cCount-1], (basePlan !! (i*cCount + j))

≠ 0]

-- Избавляемся от вырожденности.

lNDPlan = makeNonDegeneratePlan basePlan mColCount

-- Находим оптимальный план по критерию времени.

ans = addConditions lNDPlan t mRowCount mColCount rCount cCount aV maxi

[]

optimPlan = last ◊ fst ◊ fst ◊ last ◊ init ans

-- Находим максимальноое время перевозки

maxT = maximum [ t !! ((fst ◊ fst el) - 1) !! ((snd ◊ fst el) - 1)|

el ← optimPlan,

(snd el ≥ 0.9) &&

(((aV ≡ 1 ) ∧ ((fst ◊ fst el) ≠ mRowCount)) ||

((aV ≡ 2 ) ∧ ((snd ◊ fst el) ≠ mColCount)) ||

(aV ≡ 3 )) ]

cM = 2 * sum [ c !! i !! j | i ← [0‥rCount-1], j ← [0‥cCount-1]]

-- Блокируем

c1 = [[(case aV of

1 → if i ≡ mRowCount - 1

then cM

else (if (t !! i !! j) > maxT

11

then cM

else c !! i !! j)

2 → if j ≡ mColCount - 1

then cM

else (if (t !! i !! j) > maxT

then cM

else (c !! i !! j))

3 → (if (t !! i !! j) > maxT

then cM

else (c !! i !! j))) |

j ← [0‥mColCount-1] ] |

i ← [0‥mRowCount-1] ]

nonDPlan = listToArrayList lNDPlan mColCount

-- Потенциалы и оценочная матрица

rt = potentials c1 (map snd optimPlan) ([(0,0)],[])

c0 = [[ (c1 !! i !! j) - ((fromJust ◊ lookup j ◊ snd rt) - (fromJust ◊

lookup i ◊ fst rt)) |

j ← [0‥mColCount-1] ] |

i ← [0‥mRowCount-1] ]

fstSum = sum ◊ zipWith (*) (mkNonClsdPlan optimPlan mColCount aV) ◊

concat c

-- Находим план, дооптимизированный по стоимости.

pl = if null [ minimum i | i ← c0, (minimum i) < 0 ]

then (([optimPlan,optimPlan], [c1,c0]),([maxT,maxT],[fstSum,fstSum])

)

else

let newStepsPlan = fst ◊ mkNewPlan c0 optimPlan mRowCount mColCount

sndSum = sum ◊ zipWith (*) (mkNonClsdPlan newStepsPlan mColCount

aV) ◊ concat c

maximm = maximum [ t !! i !! j |

i ← [0‥rCount-1], j ← [0‥cCount-1],

(snd (newStepsPlan !! (i*cCount + j))) ≠ 0]

in (potentialsMethod t (mkNonClsdPlan2 c1 aV) ([maxT,maxT,maximm],

[fstSum,sndSum,sndSum])

mColCount aV False [optimPlan,optimPlan,newStepsPlan]

[c1,c0])

parameters = [mRowCount, mColCount, 1 + length ans] ⊕ [ length ◊ fst ◊

fst el | el ← ans ]

⊕ [fromIntegral ◊ length ◊ fst ◊ fst pl]

pr ← newArray ([ fromIntegral i | i ← parameters ]

⊕ (concat [[ fromRational ◊ toRational el |

el ← map snd (concat ◊ fst ◊ fst et)] ++

(map fromIntegral ◊ concat ◊ concat ◊ snd ◊ fst et) |

et ← ans])

⊕ ( [ fromRational ◊ toRational el |

el ← map snd (concat ◊ fst ◊ fst pl)] ++

(map fromIntegral ◊ concat ◊ concat ◊ snd ◊ fst pl))

---et ← ans])

⊕ (map fromIntegral ◊ concat [fst ◊ snd et | et ← ans])

⊕ (map fromIntegral ◊ concat [snd ◊ snd et | et ← ans])

⊕ (map fromIntegral ◊ fst ◊ snd pl)

⊕ (map fromIntegral ◊ snd ◊ snd pl))

return pr

module BaseOperations where

import List

import Maybe

type Plan = [((Int, Int), Float)]

type Ansset = (([Plan],[[[Int]]]),([Int],[Int]))

addConditions :: [Float] → [[Int]] → Int → Int → Int → Int → Int → Int →

[Ansset] → [Ansset]

addConditions plan t mRC mCC rC cC aV maxi dec = (

12

-- blok - Значение, которым будем блокировать перевозки.

let blok = 5 * sum [ t !! i !! j | i ← [0‥rC-1], j ← [0‥cC-1]]