home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 22 / CD_ASCQ_22_0695.iso / win / educ / rtkspad / lp_multi.sp_ / lp_multi (.txt)
Microsoft Windows Help File Content  |  1995-05-08  |  19KB  |  267 lines
  1. R-Tek Scratchpad
  2. Version   1.00
  3. TSPadDatad
  4. TPictured
  5. TCommentTextd
  6. TLogFontd
  7. Times New Roman
  8. densed BT
  9. Linear Programming
  10. nnnnnnnnnnnnnnnnnn]
  11. TCommentTextd
  12. Sometimes there are multiple solutions to a linear programming problem.G
  13. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  14. TCommentsd
  15. TCommentTextd
  16. objective function
  17. nnnnnnnnnnnnnnnnnn]
  18. TCommentTextd
  19. maximize:    
  20. nnnnnnnnn]
  21. TExpressiond
  22. z:2*x[1]+x[2]-2*x[3]-2*x[4]
  23. TCommentTextd
  24. constraints
  25. nnnnnnnnnnn]
  26. TCommentTextd
  27. subject to:
  28. nnnnnnnnnnn]
  29. TExpressiond
  30. 2*x[1]+x[2]-2*x[4]
  31. TExpressiond
  32. x[2]+2*x[3]+4*x[4]
  33. TExpressiond
  34. x[1]-2*x[2]+x[4]
  35. TCommentTextd
  36. non-negativity constraints (often not explicitly stated)8
  37. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  38. TExpressiond
  39. TExpressiond
  40. TExpressiond
  41. TExpressiond
  42. TEndCommentsd
  43. TCommentTextd
  44. The scratchpad requires that you translate the above problem into a form it understands.X
  45. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  46. TExpressiond
  47. c:M000100072@1@-2@-2@0@0@0@
  48. TCommentTextd
  49. coefficients of the objective function,
  50. last three are for slacks (optional)L
  51. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  52. TExpressiond
  53. A:M000300042@1@0@-2@0@1@2@4@1@-2@0@1@%
  54. TCommentTextd
  55. coefficients of the constraints
  56. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  57. TExpressiond
  58. r:M000300011@1@-1@
  59. TCommentTextd
  60. relations of the inequality constraints.
  61. 1 for less than or equal
  62. 0 for equal
  63. -1 for greater than or equalj
  64. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  65. TCommentTextd
  66. You should note that each r element is
  67. the same as the initial slack variable 
  68. coefficient (for positive b)k
  69. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  70. TExpressiond
  71. b:M0003000150@50@20@
  72. TCommentTextd
  73. constants of the constraints
  74. nnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  75. TCommentTextd
  76. This completes the translation of the problem into the necessary form.
  77. Next, set up the variables that will contain the solution.
  78. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  79. TExpressiond
  80. x:zmat(1,1)
  81. TCommentTextd
  82. it is only important that tableau and x are matrices, 
  83. since their size will be adjusted as necessarye
  84. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  85. TExpressiond
  86. tableau:x    
  87. THardPageBreakd
  88. TExpressiond
  89. lpmax(c,A,r,b,x,tableau)
  90. TCommentTextd
  91. objective function maximum
  92. nnnnnnnnnnnnnnnnnnnnnnnnnn]
  93. TCommentTextd
  94. lpmax solves the linear programming maximization problem.  You can see that the first 
  95. four parameters define the problem and the last two return information about the solution z.
  96. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  97. TExpressiond
  98. TExpressiond
  99. tableau
  100. TCommentTextd
  101. Examine the final row of the tableau, which is the simplex criteria row.  The fact that there are
  102. no negatives indicates we are at an optimal solution for a maximization problem. x1, x2, and the second
  103. slack variable (x6) are in the solution so we expect to see zeros in these columns.  column 3 indicates 
  104. that if we increase the coefficient of x3 in the objective function by more than 2, we would force x3 
  105. into the solution vector.
  106. Of more interest are the zeros in columns 4 and 7, not currently in the solution. These indicates that
  107. any tiny increase, no matter how small, in the coefficient of x4 or x7 in the objective function will force
  108. x4 or x7 into the solution vector.  This tells us that there are other solution vectors for this problem, 
  109. indeed infinitely many solution vectors that are linear combinations of the one we know about
  110. and the ones we now know must exist. Let's show this by first finding the other solution vectors.
  111. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnzznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnzz]
  112. TExpressiond
  113. x_new:zmat(1,1)
  114. TCommentTextd
  115. the new solution will be returned in this vector0
  116. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  117. TExpressiond
  118. tableau_new:x_new
  119. TExpressiond
  120. c_new:c
  121. TExpressiond
  122. c_new[4]:c[4]+1/1000000
  123. TCommentTextd
  124. or any other small increment
  125. nnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  126. TExpressiond
  127. z:lpmax(c_new,A,r,b,x_new,tableau_new)&
  128. TExpressiond
  129. x_new
  130. TExpressiond
  131. tableau_new
  132. THardPageBreakd
  133. TCommentTextd
  134. See how x4 was forced into the solution vector, while the
  135. objective function and its optimimun value were hardly effected.z
  136. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  137. TCommentTextd
  138. This problem has a couple more solution vectors (see if you can find them using the
  139. perturbation technique, ie add or subtract a small amount from the coefficents with zeros
  140. in the simplex criteria row of tableau and keep track of new solutions)
  141. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  142. TCommentTextd
  143. The general solution then can be any linear combination of the solution vectors,
  144. as in:W
  145. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnn]
  146. TExpressiond
  147. f1:1/4
  148. TExpressiond
  149. f2:1/4
  150. TExpressiond
  151. f3:1/4
  152. TExpressiond
  153. f4:1/4
  154. TCommentTextd
  155. You can make these fractions whatever you want so long as they total one.I
  156. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  157. TExpressiond
  158. solution1:M0004000124@2@0@0@
  159. TExpressiond
  160. solution2:M0004000175/2@0@0@25/2@!
  161. TExpressiond
  162. solution3:M0004000130@10@0@10@
  163. TExpressiond
  164. solution4:M0004000125@0@0@0@
  165. TExpressiond
  166. x_linear_combination:f1*solution1+f2*solution2+f3*solution3+f4*solution4H
  167. TExpressiond
  168. c:submat(c,1,1,1,4)
  169. TCommentTextd
  170. chop off slack coefficients if used 
  171. (only nonzero for perturbation technique anyway)U
  172. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  173. TExpressiond
  174. z_linear_combination:c*x_linear_combination+
  175. TCommentTextd
  176. As an alternate method of calculating the other optimum solution vectors, let's begin by using the 
  177. final tableau and our knowledge of the simplex method to introduce x4 into the simplex tableau.  
  178. We examine each row and calculate the ratio of the final columm element to the 4th column element.  
  179. We then choose the row with the minimum such positive ratio and perform a Gauss-Jordan 
  180. elimination based on that rows 4th column element.
  181. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  182. TCommentTextd
  183. Let's recall the tableau corresponding to solution1 for easy reference:G
  184. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  185. TCommentTextd
  186. ignore row 1 since 4th element is negative*
  187. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  188. TCommentTextd
  189. start with
  190. nnnnnnnnnn]
  191. TExpressiond
  192. 48/((24/5))
  193. TExpressiond
  194. tableau
  195. TExpressiond
  196. solution1    
  197. TCommentTextd
  198. ignore row 3 since 4th element is negative*
  199. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  200. THardPageBreakd
  201. TCommentTextd
  202. We see that the second row has the minimum positive ratio,  so we now pivot on the 2, 4 th
  203. element of the tableau to introduce x4 into the solution (eliminating the second slack variable
  204. from the solution in the process.)
  205. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  206. TExpressiond
  207. 10/((1/3))
  208. TCommentTextd
  209. new solution
  210. nnnnnnnnnnnn]
  211. TCommentTextd
  212. ignore row 2 since 7th 
  213. element  is negative,
  214. nnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnn]
  215. TExpressiond
  216. solution3    
  217. TExpressiond
  218. pivot(tableau,2,4)
  219. TCommentTextd
  220. ignore row 3 since 7th 
  221. element  is negative,
  222. nnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnn]
  223. TCommentTextd
  224. We see that the first row has the minimum positive ratio,  so we now pivot on the 1, 7 th
  225. element of the tableau to introduce x7 into the solution (eliminating x2 from the solution 
  226. in the process.)
  227. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnn]
  228. TCommentTextd
  229. new solution
  230. nnnnnnnnnnnn]
  231. TExpressiond
  232. solution4    
  233. TExpressiond
  234. tableau:pivot(tableau,1,7)
  235. TCommentTextd
  236. solution2 is not reachable in a single pivot from the tableau corresponding to solution1,
  237. but is reachable with one additional pivot from the tableau immediately above.
  238. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]
  239. TCommentTextd
  240. new solution
  241. nnnnnnnnnnnn]
  242. TExpressiond
  243. pivot(tableau,2,4)
  244. TExpressiond
  245. solution2    
  246. TCommentTextd
  247. Inspection of this tableau shows us that we have now obtained the same solution vectors 
  248. by pivoting that we calculated above by the perturbation method.
  249. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]][
  250. TPrinterDimensionsd
  251. TSPadInitDatad
  252. TLogFontd
  253. Times New Roman
  254. densed BT
  255. TLogFontd
  256. Arial
  257. TLogFontd
  258. Arial
  259. TLogFontd
  260. Symbol
  261. TLogFontd
  262. Symbol
  263. TNumberFormatDatad
  264. TGraphSetupDatad
  265. TPageSetupDatad
  266. R-Tek Scratchpad Example File LP_MULTI
  267.