Scribd
Upload
108 views5 pages

Mid Exam

The document outlines the application of the dual simplex method and the simplex algorithm to solve linear programming problems. It includes specific examples of maximizing and minimizing objective functions, along with constraints and the formulation of a balanced transportation problem for a bank's check processing. The document provides detailed steps and calculations for reaching optimal solutions and formulating the transportation problem without solving it.

Uploaded by

9966853977
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
108 views5 pages

Mid Exam

The document outlines the application of the dual simplex method and the simplex algorithm to solve linear programming problems. It includes specific examples of maximizing and minimizing objective functions, along with constraints and the formulation of a balanced transportation problem for a bank's check processing. The document provides detailed steps and calculations for reaching optimal solutions and formulating the transportation problem without solving it.

Uploaded by

9966853977
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 5

111-00-2350

Vamsi Krishna

1 - Use the dual simplex method to solve the following LP: Max Z = -2X1 - X3 s.t. X1 + X2 X3 >= 5 X1 - 2X2 + 4X3 >=8 X1, X2, X3 >=0 Solution: Min A= 1 1 -2 1 -2 0 -1 4 -1 5 8 0

A Transpose= 1 -1 5 Min W=5Y1+8Y2 SUBJECT TO: Y1+Y2<=-2 Y1-2Y2<=0 -Y1+4Y2<=-1 Y1, Y2>=0 STACK VALUE X1,X2 Y1 1 1 -1 -5 Y2 1 -2 4 -8 X1 0 0 0 0 X2 0 0 0 0

1 -2 4 8

1 0 -1 0

-2

W 0 0 0 1 -2 0 -1 0 -2/1 0 -1/4

111-00-2350 -8 is the most negative value

Vamsi Krishna

As -2 is the least value make the row R1 with the most negative value 0 and perform the pivot operation R1R1 2R1+R2R2 Y1 1 3 -5 3 Y2 1 0 0 0 X1 0 0 0 0 -4R1+R3R3 8R1+R4R4 X2 0 0 0 0 W 0 0 0 1 -2 0 7 -16

Optimal solution is reached as the last row is non- negative. X1=0 AND X2=0 The maximum value of -16 at (0,0)

2 Use the simplex algorithm to find the optimal solution to the following LP: Min Z = -4X1 + X2 s.t. 3X1 + X2 <= 6 - X1 + 2X2 <=0 X1, X2 >= 0 Converting above inequalities into equations by adding slack variables

111-00-2350 3X1 + X2 +s1= 6 - X1 + 2X2 +s2=0 Z=-4x1+x2+s1+s2 Where x1, x2, s1, s2>=0 Z+4x1-x2-s1-s2=0

Vamsi Krishna

Since our objective is minimize the z, entering variable will correspond with most positive coefficient in the objective function. The starting simplex table will be X1 z S1 S2 4 3 -1 X2 -1 1 2 S1 0 1 0 S2 0 0 1 6 0 solution

From the above table entering variable =x2 Leaving variable ratio: S1=6 /1=6 s2=0

Since the entries are not zero, variable can leave.

3 - A bank has two sites at which checks are processed. Site 1 can process 10,000 checks per day, and site 2 can process 6000 checks per day. The bank processes three types of checks: vendor, salary, and personal. The processing cost per check depends on the site (table below). Each day 5000 checks of each type must be processed. Formulate a balanced transportation problem to minimize the daily cost of processing checks. Only complete formulation needs to be submitted. Do not solve.

111-00-2350 Site1 Vendor checks Salary checks Personal checks 5 cents 4 cents 2 cents Site2 3 cents 4 cents 5 cents

Vamsi Krishna

Solution: Let X1=Vendor checks X2=Salary checks X3=Personal checks Site1 =s1, site2=s2

Site1 day Vendor checks Salary checks Personal checks Demands 10000 5 cents 4 cents 2 cents 6000

Site2

Checks per

3 cents 4 cents 5 cents

5000 5000 5000

Therefore Formulation is 5x1+4x2+2x3<=10000 3x1+4x1+5x3<=6000 5s1+3s2<=5000

111-00-2350 4s1+4s2<=5000 2s1+5s2<=5000 X1, x2, x3, s1, s2 >=0

Vamsi Krishna

You might also like