Scribd
Upload
73 views3 pages

Soal

The document discusses several linear programming and network optimization problems. It first provides two linear programming problems with objective functions to maximize and minimize subject to constraints. It then solves the problems to find the optimal solution values. The document also presents several network optimization problems involving nodes and routes, and applies Djikstra's, Prim's and Kruskal's algorithms to find minimum spanning trees and total weights.

Uploaded by

Muhammad Farhan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
73 views3 pages

Soal

The document discusses several linear programming and network optimization problems. It first provides two linear programming problems with objective functions to maximize and minimize subject to constraints. It then solves the problems to find the optimal solution values. The document also presents several network optimization problems involving nodes and routes, and applies Djikstra's, Prim's and Kruskal's algorithms to find minimum spanning trees and total weights.

Uploaded by

Muhammad Farhan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Linear Programming

1. Consider the following set of constraints:

Step 1

(a) Maximize z = 3x1 − x2 + 3x3 + 4x4

(b) Minimize z = 5x1 − 4x2 + 6x3 - 8x4

3 -1 3 4 0 0 0
Solution Values Rasio
0 40 1 2 2 4 1 0 0 10
0 8 2 -1 1 2 0 1 0 4
0 10 4 -2 1 -1 0 0 1 -10
0 0 0 0 0 0 0
3 -1 3 4 0 0 0
Key element = -1

Step 2
[ ] [ ]
[ ] [ ]
[ ] [ ]
[ ] [ ]
[ ] [ ]
[ ] [ ]
[ ] [ ]
[ ] [ ]

3 -1 3 4 0 0 0
Solution Values Rasio
0 0 -15 10 -2 8 1 0 -4 0
0 -12 -6 3 -1 4 0 1 -2 2
4 -10 -4 2 -1 1 0 0 -1 2,5
-16 8 -4 4 0 0 -4
19 -9 7 0 0 0 4

Step 3

—
-1 0 1 0

[ ] [ ]
[ ] [ ]

[ ] [ ]

[ ] [ ]

[ ] [ ]

[ ] [ ]

[ ] [ ]

[ ] [ ]

3 -1 3 4 0 0 0
Solution Values Rasio
1
0 1 0 10
0
-12 -12 -1 1 4
4
-10 0 0 -10

1 2 0

2 1 0

(a) Maximize z = 3x1 − x2 + 3x3 + 4x4 = 0 - 0 - 30 + 0 = -30

(b) Minimize z = 5x1 − 4x2 + 6x3 - 8x4 = 0 – 0 -60 – 0 = -60

X1 = 0

X2 = 0

X3 = -10

X4 = 0

2. Max Z = 2x1 + 20x2

Z(A) = 0 + 50 = 50

Z(B) = 10 + 0 = 10
Z(C) = 0 + 60 = 60

Z(D) = 6 + 0 =6

The Value is 60

Network Model
1. Djikstra’s algorithm

Nodes Routes Distance


1 1-2 100
2 1-4 30
3 1-3-4 40
4 1-3-5 90

2. Prim’s and Kruskal’s algorithm!

- Prim’s Algorithm

Weigh of minimum spanning tree = 54

A, D, C, E, B, F, G

- Kruskal Algorithm

14+21+5+7+3+4 =54

You might also like