Nije meni, i ne znam nista sa ovim da radim pa ne mogu pomoci covjeku koji je Elektrotehnicki Fakulet i trazi mi da mu pomognem sa sledecim sastavom, pa ako moze neko da mu pomogne moze, ako ne nista, potrebno je covjeku do utorka koliko bilo da ne dobije 0. Hvala svima na pomoci koji mogu.
Evo ovako ide problem.
Write a program to implement the Primal Dual Algorithm for solving linear
programming problems using the Condensed Table Algorithm. Be sure to
print all intermediate tables so you can check your output. You may direct
your output to the display unit or to a file. You may take your input from
the keyboard or from a file. Be sure to clearly specify which method is
being used. Your input should be in a form that closely mirrors the original
problem. You will need to be able to accept greater than or less than
symbols and even equality constraints. If time permits, you should also
ask whether or not an integer solution is required. If so, you can output
the non-integer solution as well as the integer solution.
Be sure to clearly document your program. Use the problems from class to
test your program. Your program should handle at most a 10 by 10
matrix. It should be easy to modify your program to handle larger problem
sets. You should echo the input so the user can verify that what was
accepted matched the problem intended to be solved.
Due Date: On or before Tuesday, December 3, 2002.
The Primal-Dual Algorithm
Used for mixed systems
1. Replace equality constraints with two inequalities, one ≥ & one ≤.
2. Convert all ≥ constraints to ≤ by multiplying by –1.
3. If necessary, convert the objective function to a maximization objective function.
4. Set up the m*n condensed table, using a slack variable for each
constraint.
5. Determine a possible pivot element, Sp=apq, by the Simplex Algorithm. Let θp be the smallest row ratio. Compute
S = |amq * θp|.
6. Determine a possible pivot element, Dp=apq, by the Dual Simplex Algorithm. Let θq be the largest (smallest absolute value) ratio. Compute
D = |apn * θq|
7. Choose the pivot element to be the one which generates the larger of the two values S and D.
8. Pivot using the Condensed Table Algorithm.
9. Repeat Steps 5-8 until the table is optimal and feasible or until a
new pivot cannot be determined.
The Condensed Table Algorithm
1. Replace the pivot element with its reciprocal.
2. Divide the remained entries of the pivot row by the pivot element.
3. Divide the remained entries of the pivot
column by the negative of the pivot element.
4. For the remaining entries, subtract from the corresponding
position in the old table, the product of the old value in that same row,
pivot column
and the new in that same column, pivot row, i.e.
newaij = oldaij – oldaik * newahj
where k = pivot column and h = pivot row.
5. Interchange the integer above the pivot column with the integer to the left of the pivot row. All others remain unchanged.