Linear Programming In Mathcad On The Example Of Solving The Transportation

І Н Ф О Р М А Ц ІЙ Н І Т Е Х Н О Л О Г ІЇ УДК 004.67 LINEAR PROGRAMMING IN MATHCAD ON TH E EXAMPLE OF SOLVING TH E TR ANSPORTATION PROBLEM V. Ovcharuk, N. Vovkodav, T. Kryvets N ational University o f F ood Technologies І. Ovcharuk K yiv State M aritim e A cadem y Key words: Linear programming MathCAD Engineering calculations Article history: Received 18.02.2015 Received in revised form 15.03.2015 Accepted 27.04.2015 Corresponding author: ABSTRACT This article presents the basic theoretical information, as well as a sample of solving transportation problem using classical methods and Mathcad software environment. Classical methods for solving linear programming problems require large amounts of mathematical calculations. Now it is common to use the newest information technologies, such as Mathcad math processor, in such cases. This development will contribute to better training of highly qualified specialists in the area of engineering calculations. V. Ovcharuk Email: Ovcharuk2004@ukr.net ЛІНІЙНЕ ПРОГРАМУВАННЯ В MATHCAD НА ПРИКЛАДІ РОЗВ’ЯЗАННЯ ТРАН СПО РТН О Ї ЗАДАЧІ В.О. Овчарук, Н.І. Вовкодав, Т.О. Кривець Н аціональний університ ет харчових технологій І.В. Овчарук К иївська держ авна академія водного т ранспорт у У ст ат ті наведено приклад р о з в ’я зання т ранспорт ної задачі класичними м ет одами та у програм ном у середовищ і M athcad. К ласичні мет оди р о з в ’я зання задач лінійного програмування вимагаю т ь великої кількост і м ат ем ат ичних розрахунків, т ому доцільно в т аких випадках заст осовуват и новіт ні інф ормаційні технології, наприклад, м ат ем ат ичний процесор M athcad. Д а н а розроб ка сприятиме більш якісній підгот овці висококвалі ф ікованих спеціаліст ів у галузі інж енерних розрахунків. Ключові слова: лінійне програмування, M athCad, інж енерні розрахунки. Problem formulation. T h e tr a n sp o r ta tio n p r o b le m h a s a n im p o r ta n t p la c e in lin e a r p r o g r a m m in g a n d is w id e ly u s e d in th e tr a n sp o r ta tio n a n d in d u str y . It a ls o c a n b e u s e d in s o m e p r a c tic a l s itu a tio n s c o n n e c te d w ith r e s o u r c e s m a n a g e m e n t, c r e a tin g o f r e p la c e m e n t s c h e d u le , a p p o in tm e n t o f e m p lo y e e s , e tc . It is o f s p e c ia l 110 Наукові праці НУХТ 2015. Том 21, 4

IN F O R M A T IO N T E C H N O L O G Y im p o rta n c e fo r o rg a n iz a tio n o f ra tio n a l s u p p ly o f im p o rta n t c a rg o e s a s m u c h a s fo r o p tim a l p la n n in g o f c a rg o tra ffic a n d w o rk o f d iffe re n t ty p e s o f tra n s p o rt. In re c e n t y e a r s d if fe r e n t fa c ilitie s f o r e n g in e e r in g a n d s c ie n tif ic c a lc u la tio n s h a v e a p p e a re d . T hat e n a b le s p ro g ra m m in g becom es sp e c ia lis ts to s o lv e la n g u a g e s , ju s t n e c e ssa ry to po sed u s in g m a s te r such p ro b le m s u su al w ith o u t p e rfe c t m a th e m a tic a l s o ftw a re p ro d u c ts n o ta tio n . as k n o w in g of H o w ev er, it s y s te m s of a u to m a te d e n g in e e rin g a n d e c o n o m ic c a lc u la tio n s E x c e l a n d M a th C a d . Review of previous studies. le m s S o m e a s p e c ts o f s o lv in g lin e a r p ro g ra m m in g p r o b (in c lu d in g th e tr a n s p o r ta tio n p ro b le m ) in e n g in e e rin g c a lc u la tio n s u s in g M S E x c e l w e r e d e s c r ib e d in [1 , 2 , 3 ]. H o w e v e r , m e th o d s o f s o lv in g o p tim iz a tio n a n d lin e a r p r o g ra m m in g p ro b le m s u s in g m o d e r n c o m p u te r te c h n o lo g ie s , in p a r tic u la r m a th e m a tic a l p r o c e s s o r M a th C a d , a r e n o t d e v e lo p e d e n o u g h . I n U k r a in e s u c h s c ie n tis ts w o r k o v e r th is p r o b le m : М .А . М а r ty n e n k o , Т .О . К r y v e ts , Y a .B . P e tr iv s k ii a n d o th e rs . Purpose of the article is to p r o p o s e m e th o d s o f s o lv in g th e lin e a r p r o g r a m m in g tra n s p o rta tio n p ro b le m , a s th e m o s t p o p u la r p ro b le m in e c o n o m ic c a lc u la tio n s a n d a v e ry im p o rta n t c h a p te r in p re p a rin g o f b a c h e lo rs in th e area o f k n o w le d g e “ E c o n o m y a n d b u s in e s s ” , u s in g m a th e m a tic a l p r o c e s s o r M a th C a d . Main material description . I n p o i n t s А 1, А 2 . A m t h e r e a r e h o m o g e n e o u s r a w m a t e r i a l s o r g o o d s t h a t a r e n e e d e d t o b e t r a n s f e r r e d i n t o p o i n t s o f c o n s u m p t i o n В 1, В 2 . В п . R e s e r v e s o f s u p p l y p o i n t s a n d n e e d s o f c o n s u m p t i o n p o i n t s a r e k n o w n s e t v a l u e s : A ( a 1, a 2 . a m), B ( b h b 2 . b n) . T r a n s p o r t a t i o n c o s t s f r o m e a c h s u p p l y p o in t to e a c h p o in t o f c o n s u m p tio n a r e c h a r a c te r iz e d b y a m a tr ix : ( cC11 c12 ' c21 c22 ' cin " c0i n ( c ) c31 c32 ' cm1 cm 2 ' T hen, fro m th e e c o n o m ic p o in t o f v ie w c3n cmn J th e p ro b le m is p o s e d as fo llo w s : tra n s p o rta tio n o f ra w m a te ria ls o r g o o d s fro m s u p p ly p o in ts to c o n s u m p tio n p o in ts s h o u ld b e p la n n e d so th a t d e m a n d s o f a ll th e c o n s u m e r s a r e c o m p le te ly s a tis f ie d , a ll th e reserv es are ta k e n out and, at th e sam e tim e , to ta l cost of a ll th e t r a n s p o r ta tio n s is th e lo w e s t p o s s ib le . T o c o n s tru c t m a th e m a tic a l m o d e l o f th e p ro b le m , w e d e n o te q u a n tity o f u n its o f ra w m a te ria l o r g o o d s , th a t a re p la n n e d to b e tra n s p o rte d fro m і - th s u p p ly p o in t A , to j- th p o i n t o f c o n s u m p t i o n B j , a s Xy. A f t e r t h a t w e o b t a i n t h e f o l l o w i n g l i n e a r p ro g ra m m in g p ro b le m : m n L c j x j i 1 j 1 m in (1 ) m x ij b j i i j 1 .n (2 ) n X j a, i 1 .n j i Scientific Works o f NUFT 2015. Volume 21, Issue 4 111

І Н Ф О Р М А Ц ІЙ Н І Т Е Х Н О Л О Г ІЇ Xj 0 i 1.n, j 1.n . (3) Definition 1. Plan of the transportation problem (1)— (3) is a set of values x Xj (i 1.n, j 1.n) that satisfies conditions (2)—(3). Definition 2. Optimal plan of the transportation problem (1)— (3) is the plan x* (xij*) (i 1. n, j 1. n), that satisfies condition (1). Theorem 1. For the transportation problem to be solved it is necessary and sufficient to satisfy the balance condition m n I a I bj . i 1 j 1 An algorithm of the method of potentials is based on fairness of the following theorem: Theorem 2. If for some reference plan X (xij), (i 1.n, j 1.n) of the transportation problem exist such numbers a, 3 that Pj - a , Cj for Xj 0 i Pj - a i * cj for Xj 0, then X ( x j is the optimal plan of the transportation problem. Definition 3. Numbers a h рг- are called potentials of supply and consumption points respectively. Remark. If for the transportation problem (1)—(3) balance conditions are not satisfied, then we have an opened model of the transportation problem. In this case, we take an additional, fictitious supply (consumption) point with the quantity of reserves (needs) enough to satisfy the balance conditions. Transportation costs from this supply (consumption) point are equal to zero. After finding the solution, we discard the artificial components from the optimal plan. To find the optimal plan of the transportation problem, we explore corresponding mathematical model using the method of potentials and built-in Mathcad functions. Cost m atrix Suppliers Consumers "2 8 4 8 3" "120 " "30" 3 2 5 2 6 30 90 6 5 8 7 4 40 80 3 4 4 2 1 60 20 30 4 5 As X ai X bj 250, then the problem is balanced. i 1 j 1 Using the north-west corner method we find an acceptable reference plan. Table 1. Suppliers 1 А1 112 B1 2 2 30 B2 3 8 Consumers B3 4 4 B4 5 B5 8 3 90 Наукові праці НУХТ 2015. Том 21, 4 6 Inventories 7 120 90 0

IN F O R M A T IO N T E C H N O L O G Y 1 2 3 A2 3 2 6 A3 3 A4 D emand for resources 30 0 4 5 30 2 6 6 5 8 7 4 4 40 4 10 2 20 30 80 50 10 0 20 0 30 90 0 ( 1 .1 ) ( 1 .2 ) 5 C o ntinued table 1 7 30 0 40 0 1 60 50 30 0 250 25 m in ( 3 0 ,1 2 0 ) 3 0 m in ( 9 0 ,9 0 ) 9 0 ( 2 .3 ) m i n ( 8 0 ,3 0 ) 3 0 ( 3 .3 ) m in ( 5 0 ,4 0 ) 4 0 ( 4 .3 ) m in ( 1 0 ,6 0 ) 10 ( 4 .4 ) m in ( 2 0 ,5 0 ) 2 0 ( 4 .5 ) m in ( 3 0 ,9 0 ) 3 0 T h e r e f e r e n c e p la n is o b ta in e d . T h e f o llo w in g tr a n s p o r ta tio n c o s ts c o r r e s p o n d to th is p la n : F 3 0 2 9 0 8 3 0 5 4 0 8 1 0 4 2 0 2 3 0 -1 13 6 0 T h e o b ta in e d r e f e r e n c e p l a n is n o t th e o p tim a l o n e . F o r its o p tim iz a tio n w e u s e th e m e th o d o f p o te n tia ls . T o d e te rm in e p o te n tia ls o f s u p p lie rs a n d c o n s u m e rs w e c o n s tru c t a s y s te m o f e q u a tio n s f o r f illin g c e lls o f th e ta b le 2 . c j - - u vj ux v1 2 ux v2 8 u2 v3 5 u3 v3 u4 v3 u4 v4 8 v5 1 u4 T h is u n d e f in e d s y s te m Mj 0 Vj 2 - 0 2 u2 5 - 4 1 v2 8 - 0 8 u3 8 - 4 4 v3 4 - 0 4 u4 0 v4 2 - 0 2 4 v5 1- 0 1 2 h a s 7 e q u a tio n s a n d 9 u n k n o w n s , th e re fo re w e g iv e a n a r b i t r a r y v a l u e t o o n e o f t h e p o t e n t i a l s i n o r d e r t o s o l v e it. V a l u e s o f p o t e n t i a l s a r e p re s e n te d in ta b le 2. Table 2. Suppliers 1 A1 B1 2 2 30 B2 3 8 90 160 Consumers B3 4 4 0 30 B4 5 B5 8 -6 3 6 -2 Scientific Works o f NUFT 2015. Volume 21, Issue 4 Inventories u 7 8 0 0 113

ін ф о р м а ц ій н і 1 3 2 ТЕХН ОЛО ГИ 4 5 30 10 5 2 1 8 7 40 4 10 -1 2 20 30 3 2 0 6 0 -1 7 30 5 7 4 4 Needs 0 0 0 0 0 Vl 2 8 4 2 1 А2 А3 А4 3 N e x t, w e e v a lu a te fre e c e lls C o ntinued table 2 7 8 6 6 0 -4 4 1 0 1 1 4 0 0 ut vj - ctj. A 21 1 2 - 3 0 A 13 0 4 - 4 0 A 22 1 - 8 - 2 7 A 14 0 2 - 8 - 6 A 24 1 2 - 2 1 A 15 0 1 - 3 - 2 A 25 1 1 - 6 - 4 A 31 4 2 - 6 0 A 32 4 8 - 5 7 A 41 0 2 - 3 - 1 A 34 4 2 - 7 - 1 A 42 0 8 - 4 4 A 35 4 1 - 4 1 m a x ( A 0 ) ? — w e c h o o s e ( 2 , 2 ) , A 22 7 0 , m i n ( 9 0 ,3 0 ) 3 0 V a lu e s in c e lls h a v e c h a n g e d . Table 3. А1 А2 А3 А4 B1 в2 2 8 30 3 60 6 3 2 B3 4 30 5 30 5 0 8 4 40 4 B4 10 щ Vj 2 Uj v 2 8 щ 0 v1 2 u 1 v3 4 u2 2 - 8 -6 v2 8 u 2 v2 2 u3 8 - 4 4 v3 4 u 3 v3 8 u4 0 v4 2 - 0 2 u 4 v3 4 v5 1- 0 1 u 4 v4 2 u 4 v5 1 114 Наукові праці НУХТ 2015. Том 21, 4 8 B5 3 2 6 7 4 2 20 30 1