This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report r6l17
Overview 4q3b3c
& View Integer & Goal as PDF for free.
More details 26j3b
- Words: 802
- Pages: 9
Integer and Goal Programming
Linear Programming Extensions • Integer Programming • Linear, integer solutions
• Goal Programming • Linear, multiple objectives
• Nonlinear Programming • Nonlinear objective and/or constraints
Three Types of Integer Programming Problems 1. Pure integer programming problems •
All variables integer.
1. Mixed-integer programming problems •
Some variables integer.
1. Zero-one integer programming problems •
All variables either 0 or 1.
Integer Programming Techniques • Gomory’s Cutting Plane Method • Branch and Bound Method
Goal Programming Versus Linear Programming • Multiple Goals (instead of one goal) • Deviational Variables Minimized (instead of maximizing profit or minimizing cost of LP) • “Satisficing” (instead of optimizing) • Deviational Variables are Real (and replace slack variables)
Harrison Electric Company Goal Programming Original Problem Max : 7 X 1 + 6 X 2 Subject to:: 2 X 1 + 3 X 2 ≤ 12 6 X 1 + 5 X 2 ≤ 30 Problem with goal of Profit = 30 − Min : d1 Subject to::
7 X1 + 6 X 2 + d1− −d1+ = 30 2 X1 + 3 X 2 ≤ 12 6 X1 + 5 X 2 ≤ 30
Initial Goal Programming Tableau Cj
0
0 P1 P2 0 P4 0
0 P3 0
Pivot Column
Solution x1 x2 d1- d2- d3- d4- d1+ d2+ d3+ d4+ Quantity Mix P1
d1-
7
6
1
0
0
0 -1 0
0
0
30
P2
d2-
2
3
0
1
0
0
0 -1 0
0
12
0
d3-
6
5
0
0
1
0
0
0 -1 0
30
P4
d4-
0
1
0
0
0
1
0
0
0 -1
7
Zj 0 1 0 { P4 Cj - Zj 0 -1 0
0
0
1
0
0
0 -1
7
0
0
0
0
0
0 -1
0 { Zj P3 Cj - Zj 0 Zj 2 { P2 Cj - Zj -2
0
0
0
0
0
0
0
0
0
0 3
0 0 0 1
0 0
0 0
0 0 1 0 -1 0
0 0
0
0
0
0
1
0
0
1
0
0
0 -1 0
0
0
3
0
0
0
0
0
0
0
-3 0
7 6 { Zj P1 Cj - Zj -7 -6
1
0
0 1 2
Second Goal Programming Tableau Cj
0
0 P1 P2 0 P4 0
0 P3 0
Pivot Column
Solution x x d - d - d - d - d + d + d + d + 1 2 1 2 3 4 1 2 3 4 Quantity Mix P1
x1
1 6/7 1/7 0
0
0 -1/7 0
0
0
30/7
P2
d2-
0 9/7 -2/7 1
0
0 +2/7 -1 0
0
24/7
0
d3-
0 -1/7 -6/7 0
1
0 6/7 0 -1 0
30/7
P4
d4-
0
1
0
0
0
1
0
0
0 -1
7
Zj 0 1 0 { P4 Cj - Zj 0 -1 0
0
0
1
0
0
0 -1
7
0
0
0
0
0
0 +1
0 { Zj P3 Cj - Zj 0
0
0
0
0
0
0
0
0
0 0
0
0
0
0
0
1
0
Z 0 9/7 -2/7 1 P2 { j Cj - Zj 0 -9/7 +2/7 0
0
0 2/7 -1 0
0 24/7
0
0 -2/7 +1 0
0
0 { Zj P1 Cj - Zj 0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
Final Solution to Harrison Electric’s Goal Programming Cj
0
0 P1 P2 0 P4 0
0 P3 0
Solution x x d - d - d - d - d + d + d + d + 1 2 1 2 3 4 1 2 3 4 Quantity Mix P1
d2+
8/5 0
0 -1 3/5 0
0
1 -3/5 0
6
P2
x2
6/5 1
0
0 1/5 0
0
0 -1/5 0
6
0
d1+
1/5 0 -1 0 6/5 0
1
0 -6/5 0
6
P4
d4+
-6/5 0
0
0 -1/5 1
0
0 1/5 -1
1
Zj -6/5 0 { P4 Cj - Zj 6/5 0
0
0 -1/5 1
0
0 1/5 -1
1
0
0 1/5 0
0
0 -1/5 -1
0
0
0
0
0
0
0
0
0 0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0 { Zj P3 Cj - Zj 0 Zj 0 { P2 Cj - Zj 0
0 0
0
0
1
0
0
0
0
0
0
0 { Zj P1 Cj - Zj 0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0 0 0
Linear Programming Extensions • Integer Programming • Linear, integer solutions
• Goal Programming • Linear, multiple objectives
• Nonlinear Programming • Nonlinear objective and/or constraints
Three Types of Integer Programming Problems 1. Pure integer programming problems •
All variables integer.
1. Mixed-integer programming problems •
Some variables integer.
1. Zero-one integer programming problems •
All variables either 0 or 1.
Integer Programming Techniques • Gomory’s Cutting Plane Method • Branch and Bound Method
Goal Programming Versus Linear Programming • Multiple Goals (instead of one goal) • Deviational Variables Minimized (instead of maximizing profit or minimizing cost of LP) • “Satisficing” (instead of optimizing) • Deviational Variables are Real (and replace slack variables)
Harrison Electric Company Goal Programming Original Problem Max : 7 X 1 + 6 X 2 Subject to:: 2 X 1 + 3 X 2 ≤ 12 6 X 1 + 5 X 2 ≤ 30 Problem with goal of Profit = 30 − Min : d1 Subject to::
7 X1 + 6 X 2 + d1− −d1+ = 30 2 X1 + 3 X 2 ≤ 12 6 X1 + 5 X 2 ≤ 30
Initial Goal Programming Tableau Cj
0
0 P1 P2 0 P4 0
0 P3 0
Pivot Column
Solution x1 x2 d1- d2- d3- d4- d1+ d2+ d3+ d4+ Quantity Mix P1
d1-
7
6
1
0
0
0 -1 0
0
0
30
P2
d2-
2
3
0
1
0
0
0 -1 0
0
12
0
d3-
6
5
0
0
1
0
0
0 -1 0
30
P4
d4-
0
1
0
0
0
1
0
0
0 -1
7
Zj 0 1 0 { P4 Cj - Zj 0 -1 0
0
0
1
0
0
0 -1
7
0
0
0
0
0
0 -1
0 { Zj P3 Cj - Zj 0 Zj 2 { P2 Cj - Zj -2
0
0
0
0
0
0
0
0
0
0 3
0 0 0 1
0 0
0 0
0 0 1 0 -1 0
0 0
0
0
0
0
1
0
0
1
0
0
0 -1 0
0
0
3
0
0
0
0
0
0
0
-3 0
7 6 { Zj P1 Cj - Zj -7 -6
1
0
0 1 2
Second Goal Programming Tableau Cj
0
0 P1 P2 0 P4 0
0 P3 0
Pivot Column
Solution x x d - d - d - d - d + d + d + d + 1 2 1 2 3 4 1 2 3 4 Quantity Mix P1
x1
1 6/7 1/7 0
0
0 -1/7 0
0
0
30/7
P2
d2-
0 9/7 -2/7 1
0
0 +2/7 -1 0
0
24/7
0
d3-
0 -1/7 -6/7 0
1
0 6/7 0 -1 0
30/7
P4
d4-
0
1
0
0
0
1
0
0
0 -1
7
Zj 0 1 0 { P4 Cj - Zj 0 -1 0
0
0
1
0
0
0 -1
7
0
0
0
0
0
0 +1
0 { Zj P3 Cj - Zj 0
0
0
0
0
0
0
0
0
0 0
0
0
0
0
0
1
0
Z 0 9/7 -2/7 1 P2 { j Cj - Zj 0 -9/7 +2/7 0
0
0 2/7 -1 0
0 24/7
0
0 -2/7 +1 0
0
0 { Zj P1 Cj - Zj 0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
Final Solution to Harrison Electric’s Goal Programming Cj
0
0 P1 P2 0 P4 0
0 P3 0
Solution x x d - d - d - d - d + d + d + d + 1 2 1 2 3 4 1 2 3 4 Quantity Mix P1
d2+
8/5 0
0 -1 3/5 0
0
1 -3/5 0
6
P2
x2
6/5 1
0
0 1/5 0
0
0 -1/5 0
6
0
d1+
1/5 0 -1 0 6/5 0
1
0 -6/5 0
6
P4
d4+
-6/5 0
0
0 -1/5 1
0
0 1/5 -1
1
Zj -6/5 0 { P4 Cj - Zj 6/5 0
0
0 -1/5 1
0
0 1/5 -1
1
0
0 1/5 0
0
0 -1/5 -1
0
0
0
0
0
0
0
0
0 0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0 { Zj P3 Cj - Zj 0 Zj 0 { P2 Cj - Zj 0
0 0
0
0
1
0
0
0
0
0
0
0 { Zj P1 Cj - Zj 0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0 0 0
Related Documents 171j1w
February 2023 0
Integer Programing q3b33
April 2023 0
Integer Games Handout 1j4761
December 2019 22
Goal Congruence 6d1c5d
October 2019 51
Greatest And Least Integer Functions n3a2
November 2019 25
Goal Model 3u6g3r
October 2019 46More Documents from "Vinit Modi" e1a1t
February 2023 0
No-ox-id A-special 'electrical Grade' 4w6r6k
November 2022 0
Road Safety 201r33
April 2022 0
Monograph Magazine 681w49
November 2019 210
October 2020 0
