close

Enter

Log in using OpenID

embedDownload
Mathematical Programming
Introduction:
‫البرمجة الرياضية تعرف بأنها العلم الذي يبحث في تحديد القيمة العظمى أو القيمة الصغرى لدالة محدده تسمى دالة الهدف‬
.(Objective function (
‫صناعة البالستيك‬. ٢ .‫تصميم المفاعالت الكيميائية‬. 1 : ‫تطبيقات البرمجة الرياضية‬
.‫مسائل النقل واإلنتاج‬. ٥
‫ تصميم المباني والجسور‬.4
‫ تصميم محركات الطائرات‬.3
)‫وهناك استخدامات للبرمجة الرياضية في التحليل العددي (المعادالت التفاضلية العادية غير الخطية‬
The general formula for mathematical programming :
Minimization or Maximization
Min or Max Z = f ( x1 , x2 .......xn ) 
 Objective function
Subject to (s. t.)
b1
g1 ( x 1 , x 2 ....... x n ) 


b2
g 2 ( x 1 , x 2 ....... x n ) 


.

,

,

 Constraint

. 

.
.


g n ( x 1 , x 2 ....... x n ) 
bn


Types of Mathematical Programming:
(1) Linear programming
(2) nonlinear programming
Example : ( nonlinear programming)
Min z = x1  x2
2
subject to :

 Objective function
x1  x2  3
x2  1
1
Linear Programming (LP)
Introduction
‫ وهي من األساليب األساسية والمهمة التي تساعد‬,‫تعتبر البرمجة الخطية من أكبر إنجازات منتصف القرن العشرين‬
‫ وهي احد أساليب البرمجة الرياضية وتعد مسائل البرمجة‬،‫متخذي القرار على اتخاذ قرارات صحيحة وبطريقة علمية‬
‫( ؛ ثم إن‬Non-linear ) ‫( منها وغيرالخطية‬Linear ) ‫الخطية جزءاً من مسائل البرمجة الرياضية التي تشمل الخطية‬
‫ التي تتعلق جميعها بمسائل التنظيم‬،‫ يسمى ببحوث العمليات‬،‫البرمجة الرياضية هي بدورها جزء من موضوع أكثر شمولية‬
.‫واإلدارة ومسائل النقل والزراعة والصناعة‬
‫ وذلك بهدف تعظيم الربح‬،‫كما أنها أسلوب رياضي يساعد في التخطيط واتخاذ القرار االمثل في استخدام الموارد المتاحة‬
‫وقد وفرت الماليين من األموال ومن ساعات‬،‫ وهي من النماذج المؤكدة وليست من النماذج االحتمالية‬.‫او خفض التكلفة‬
‫العمـل للعديد من الشركات والمنشآت اإلنتاجية‬
‫ ترادف في معناها كلمة تخطيط كما تشير إلى وضع المشكلة بصيغة رياضية او نموذج رياضي وحلها‬: ‫وكلمة برمجة‬
.‫باالعتماد على العالقات الخطية‬
First : Definition of a Linear Program
A function
f ( X 1 , X 2 ,.... X n ) of ( X 1, X 2 ,.... X n ) is a linear function if
and only if for some set of constants ( C1 , C2 ,....Cn )
f ( X 1 , X 2 ,.... X n ) = C1 X 1  C2 X 2  ,....Cn X n
Second : Optimization problem:
It is a mathematical technique for optimum allocation of Limited or scarce
resources, such as labor, material, machine, money energy ….etc
To achieve a specific objective ( maximize or minimize value of the objective
function)
Third: Steps linear programming:
(A) Identify the problem
(B) Construction of mathematical model
(C) Find a solution
Fourth: The general formula for linear programming model:
Linear Programming is concerned with solving just one mathematical
problem, namely maximizing or minimizing a linear function of n variables
(called the objective function) subject to m linear constraints, that is
(1))Objective function( :
Maximize or Minimize
Max or Min z  c1 x1  c2 x2  c3 x3    cn xn
(x1 , x2 , x3 , ……………. , xn) decision variables)
(2) Constraint:
٢
Subject to
a1,1 x1  a1, 2 x2  a1,3 x3    a1, n xn (  ,  ,  )b1
a2,1 x1  a2, 2 x2  a2,3 x3    a2, n xn (  ,  ,  ) b2
a3,1 x1  a3, 2 x2  a3,3 x3    a3, n xn (  , ,  ) b3
....................................................... (  , ,  ).....
am ,1 x1  am , 2 x2  am ,3 x3    am , n xn (  ,  ,  ) bm
(3) Nonnegative:
X1 , X2 , X3 , …………………. , Xn ≥ 0
-In matrix terms a linear programming model is:

Maximize or Minimize z  c x
T
Subject to


Ax  b ,

x0
Where A is an m  n matrix
 a11

 a 2,1
A   a3,1


a
 m ,1
a1, 2
a 2, 2
a 3, 2

a m, 2





 x1 
 c1 
a1,n 
 
 
 b1 

 
 c2 
 x2 
a 2,n 
b2 




x
 c 

a3,n  b   b3  , x   3  and c   3 

 






b 
 
 
a m,n 
 m
c 
x 
 n
 n
Where:
Z: represents the value of the objective function.
C: the objective function coefficients (profit or cost.).
X: the decision variables.
a: the needs of each and every one unit of resources, whether raw materials,
n: number of variables.
m: the number of restrictions.
b: the resources available .
3
(1) Maximization Problem:
Max
Z = c1X1 + c2X2 + c3X3 + ………+ cnXn
(2) Restrictions
Subject to
a1,1 x1  a1, 2 x2  a1,3 x3    a1,n xn  b1
a2,1 x1  a2, 2 x2  a2,3 x3    a2,n xn  b2
a3,1 x1  a3, 2 x2  a3,3 x3    a3,n xn  b3
.......................................................( ).....
am,1 x1  am, 2 x2  am,3 x3    am,n xn  bm
X1 , X2 , X3 , …………………. , Xn ≥ 0
(2) Minimization Problem :
Note :
maximum Z = minimum (- Z), the objective function becomes
Min
Z = c1X1 + c2X2 + c3X3 + ………+ cnXn
S.t
a1,1 x1  a1, 2 x2  a1,3 x3    a1,n xn  b1
a2,1 x1  a2, 2 x2  a2,3 x3    a2,n xn  b2
a3,1 x1  a3, 2 x2  a3,3 x3    a3,n xn  b3
.....................................................  .....
am,1 x1  am, 2 x2  am,3 x3    am,n x  bm
X1 , X2 , X3 , …………………. , Xn ≥ 0
Fifth: Examples on the formulation of a linear programming problem:
Example No. 1
The company Othazqo manufactures (chairs and tables), the price of the chair $
10, and needs to be one working hour in the Publishing Section, and one
working hour in the collection Section, the price of the table $ 40, and you need
to hours worked in the Publishing Section, and five hours of work in collection
Section, the market accommodates both producers, the time available to work
100 hours in the publishing Section, and 150 hours of work in the collection
Section, Director of the company needs to determine a production mix of chairs
and tables, whose company achieves the maximizing profit.
4
Solution
First
Objective
The objective here is Maximizing profit
Secondly Codes
number of chairs is X1
number of tables is X2
The table shows data problem:
Resources
chairs X1
tables X2
Available Time
Publishing Section
1
2
100
Collection Section
1
5
150
price
10
40
Put the data in the table above in the form of inequalities, as follows:
Objective function
Max Z=$10X1+$40X2
Constraints
1X1+2X2 ≤100
1X1+5X2 ≤ 150
X1≥ 0,X2 ≥ 0
Non negative
Example No.2:
The company general industrial production of two types of notebooks school
(writing, drawing), the time available(24 hours of the machine, 16 hours of
work), you need each unit produced books( write to 2 of the machine, and 2 of
the work) , while the needs of each unit of the books of (the drawing to 3 hours
of the machine and 1 hour of work). The price of each unit of writing books, $
12, and books drawing $ 14, note that the company could sell only 7 units from
writing books and 6 units of drawing. . Director of the company wants to
determine the quantity of production of two types that achieve the company's
the maximizing profit.
Solution
First
Objective
The objective here is Maximizing profit
Secondly
Codes
number of writing books is X1
number of drawing books is X2
٥
The table shows data problem:
Resources
writing X1
drawing X2
Available
machine
2
3
24
work
2
1
16
1 market
1
-
7
1 market
-
1
6
price
12
14
Put the data in the table above in the form of inequalities, as follows:
Max Z =$12 x1+$14 x2
Subject to:
2 x1 +3 x2 ≤ 24
2 x1+ 1 x2 ≤ 16
x1
≤7
x2 ≤6
Example No.3:
Dean of
x1≥Wants
0
x2the
≥ 0 Faculty of Administrative Sciences at the University of
Salman bin Abdul Aziz, develop a plan for number of materials for the next
course. Where the number of materials Section morning and evening section
must be at least 60 articles, and the number of products that must be provided to
the students of the Department Morning at least 30 articles, while the evening
materials section at least 20 articles. Dean also wants to reduce costs to a
minimum. If you know that the cost of material per Section Morning SR 1000
. And the cost of material per Section 800 rails evening. What is the number of
materials Section morning and evening section that you must put Dean in order
to be at a minimum cost?
Solution
First
Objective
The objective here is Minimize costs
Secondly
Codes
number of materials for morning department is X1
number of materials for the evening department X2
So the mathematical model will be as follows :
6
Min (Z)= 1000 X1 + 800 X2
Subject to:
X1+ X2 ≥ 60
X1
≥ 30
X2 ≥ 20
X1 , X2 ≥ 0
Non-negative
Exercises :
(1) Industrial company wants to determine the quantities that should be
produced from 3 different products and then limited resources (in the
following table) to maximize profit:
Resources
Product 1
Product 2
3 Product 3
Available
Workers
5
2
4
240
Raw materials
4
6
3
400
Profit
3
5
2
(2) Company produces electric tools three products A, B, and C, and the
company estimated profit for each unit are as follows 150, 120, 90,
respectively., And pass products in three steps a manufacturing, collection and
testing of quality, the following table shows the number of hours needed to
produce one unit of these products, Put the previous problem in the general
form of the linear programming?
Produces
manufacturing
collection
quality
A
2
3
1
B
3
2
0.75
C
4
2
0.75
Time available
450
370
200
7
‫‪Sixth: Canonical Form Example No.2:‬‬
‫قبل البدء باستخدام أي طريقة من طرق الحل للوصول إلى الحل األمثل (‪(Optimal solution‬‬
‫فان المشكلة يجب أن تكون بأحد الشكلين القانوني أو القياسي و سوف نبدأ بالشكل القانوني كاآلتي‪:‬‬
‫‪ -1‬دالة الهدف من نوع ‪ ) Max‬جميع القيود من نوع اصغر أو يساوي ( ≥ ) )‬
‫‪ -٢‬دالة الهدف من نوع ‪ ) Min‬جميع القيود من نوع اصغر أو يساوي (≥ ) )‬
‫‪ -3‬جميع متغيرات القرار موجبة ( ‪) Xj ≥ 0‬‬
‫‪Seventh : Standard form‬‬
‫تعتبر هذه الصيغة أفضل من السابقة ألنها تستخدم في الطريقة العامة المعتمدة في تحليل البرامج‬
‫الخطية )‪ (simplex method‬و أهم خصائص هذه الصيغة‪:‬‬
‫دالة الهدف من نوع ‪ Max‬او ‪Min‬‬
‫‪-1‬‬
‫الجانب األيمن للقيود كمية موجبة ‪bi ≥ 0‬‬
‫‪-٢‬‬
‫جميع القيود يعبر عنها بمعادالت ما عدا قيود عدم السالبية‪.‬‬
‫‪-3‬‬
‫‪-4‬‬
‫جميع المتغيرات تكون موجبة ‪Xj ≥ 0‬‬
‫في هذا الشكل يجب تغير جميع القيود التي تكون على شكل متباينات إلى شكل معادالت مساواة و ذلك‬
‫عن طريق جمع أو طرح متغير غير سالب من الجهة اليسرى لجميع القيود و كما يلي‪:‬‬
‫أ‪ -‬إذا كان القيد من نوع ( ≥ ) اصغر أو يساوي فيتم إضافة المتغير الموجب إلى الجانب األيسر‬
‫من القيد و يسمى بالمتغير الراكد ‪ Slake Variable‬و هو يمثل النقص في الجانب األيسر للقيد‬
‫مقارنة بما هو متوفر للجانب األيمن ‪.‬‬
‫‪a11 x1  a12 x2  b1  a11 x1  a12 x2  s1  b1‬‬
‫ب‪ -‬اذا كان القيد من نوع ( ≤ ) اكبر او يساوي يتم طرح المتغير الموجب من الجانب االيسر و‬
‫تسمى بالمتغيرات الفائضة ‪ Surplus Variable‬و هي تمثل الزيادة في الجانب االيسر على‬
‫الجانب االيمن ‪.‬‬
‫‪a11 x1  a12 x2  b1  a11 x1  a12 x2  s1  b1‬‬
‫‪Eighth: The solution to the linear programming problems:‬‬
‫‪First: Some terminology solving linear programming problems :‬‬
‫) ‪(1) Feasible Solution (permissible): X=(X1,X2….Xn‬‬
‫تحقق كافة القيود الواردة في المسألة‬
‫‪(2) Basic feasible solution (B.F.S):‬‬
‫يسمى الحل المقبول حل أساسي مقبول إذا كان عدد المتغيرات الموجبة فيه ال يتجاوز عدد القيود‪.‬‬
‫‪8‬‬
(3) Non degenerate B.F.S:
.‫ من المتغيرات الموجبة‬m ‫يكون الحل األساسي المقبول حال غير مجزاء إذا احتوت بالضبط على‬
(4) Optimal Solution:
‫هو الحل (أي الذي يحقق كافة القيود) إضافة إلى ذلك يجعل قيمة دالة الهدف في نهايتها العظمي أو‬
.‫نهايتها الصغرى‬
Secondly ::Methods to solve a linear programming problem:
(1) Graphical Method
(2) Simplex Method
(3) The Dual Method
GRAPHIC SOLUTION OF LP PROPLEMS
Introduction
‫تعتبر طريقة الرسم البياني طريقة سهلة وبسيطة وواضحة في معالجة مشاكل البرمجة الخطية خاصة‬
‫تلك المشاكل التي ال يزيد فيها عدد المتغيرات عن اثنين والتي تحتوي على عدد بسيط من القيود كما‬
‫تفيد طريقة الرسم البياني كمقدمة لدراسة طرق وأساليب أخرى أكثر تعقيدا في حل مشاكل البرمجة‬
‫الخطية مثل السمبلكس‬
And when you follow the graph method, you must follow these steps:
1.Draw the X-axis and Y (the positive part of each)
x2
the positive part
of each
x1
The point of origin
0=1‫ =س‬x1
0=2‫ =س‬x2
1.Specify two points for each straight (equation)
2. Drawing lines expressing the equations
3. Determine the feasible ( possibilities) available
9
x1
1.
4.Set point within the area of the feasible available that give the optimal
results (the maximization or minimization)
Example (1)
Find the optimal solution for the following LP model by using graphical:
Objective function Max z=$10X1+$40X
S.t
1X1+2X2 ≤100
1X1+5X2 ≤ 150
Non negative
X1≥ 0,X2 ≥ 0
Solution:
(1) Transfer restrictions to equal as follows
The straight first
x1+2x2=100
The straight second
x1+5x2=150
- determine of two points for each straight :
Straight 2
X2
X1
30
0
0
150
Straight 1
X2
50
0
X1
0
100
11
x2
)50= x2, 0=x1(
50
Straight 1
100 = 2X2+x1
25
)X1=100 ,x2 =0(
Feasible
region
x1
(0,0)
The point of origin
50
100
)30= x2, 0=x1(
30
20
Feasible
region
10
(0,0)
50
)X1=150 ,x2 =0(
100
Can be drawn straight first and the straight second)
11
150
X2
straight first
100=2X2+X1
50
D
30
straight second
150=5X2+X1
C
16.6
10
(0 , 0)
1
A
50
66.6
B
X1
100
150
The joint solution, an area ( A B C D ) shaded
The objective function is tested at these points, ( A B C D )
)Extreme Points(:
Points (C)
Point to the representation of the intersection of the straight 1 and the straight 2.
x1+2x2=100
x1+5x2=150
Previous solving equations using any method (deletion of compensation,
matrices, determinants, etc. or using a calculator)
using a calculator:
x1=200\3=66.67
x2=50\3=16.67
Point
X1
X2
Z=$10 x1+$40 x2
The result ($
B
C
100
66.7
0
16.7
0 ×40 + 100 ×10
16.7 ×40 +66.7 ×10
1000
1335
D
0
30
30 ×40 +0 ×10
1200
1٢
Example 2
Find the optimal solution for Example (2) (school books and booklets draw)
way the graph
Max Z =$12 x1+$14 x2
Subject to:
2 x1 +3 x2 ≤ 24
2 x1+ 1 x2 ≤ 16
x1
≤7
x2 ≤6
x1≥ 0
x 2≥ 0
Solution:
The same steps as in the first example:
Straight 4
4 ‫لمستقيم‬
X2=6
Straight 3
3 ‫لمستقيم‬
X1=7
X2
X1
6
__
Straight 1
Straight 2
2X1 +X2 = 16
2X1 +3X2 =24
X2
X1
X2
X1
7
16
0
8
__
0
8
0
0
‫تاغعععع‬
12
‫ععععععع‬
‫ععععععع‬
‫ععععععع‬
X2
Straight 2
16
2x1+x2=16
Straight 3
X1=7
Straight 4
X2=6
8
6
Y2
Y1
Y3
4
Straight 1
2x1+3x2=24
Y4
Y0
2
4
6
The joint solution, an area (Y2 Y3 Y4) shaded
Find Extreme Points (Y2 Y3 Y4 ) :
13
Y5 7
8
X1
12
Point (Y4) represents the intersection of 2 straight and the 3 straight:
2x1+x2= 16
x1 = 7
2(7) +x2 = 16
x2 =٢
x2 = 16 -14
Point (Y2 ) represents the intersection of 2 straight and the 4straight:
2x1+3x2= 24
x2=6
Use a calculator
x1 =3
x2 = 6
Point (Y3) represents the intersection of 1 straight and the 2straight
2 x1+ 3x2 = 24
2 x1+ x2= 16
Use a calculator
So
x1 =6
x2 =4
Max z = $12X1 + $14X2
Point
Y2
Y3
Y4
X1
X2
3
6
6
4
7
2
Z=$12x1+$14x2
6×14 +3 ×12
The result $
4×14 +6 ×12
2×14 +7 ×12
128
112
120
highest return at the point Y3, must produce ( 6 writing books, 4 draw) to
achieve a return of $ 128
Example 2
Find the optimal solution
Min Z = 5X + 2Y
s.t. 2X + 5Y > 10
4X - Y > 12
X+ Y> 4
Solution:
X, Y > 0
The same steps as in the first example:
14
Straight 2
Straight 3
Straight 1
4 X - Y = 12
X+ Y= 4
2X + 5Y=10
Y
X
Y
X
Y
X
4
0
-12
0
2
0
4
0
3
0
0
‫ععععععع‬
5
‫ععععععع‬
‫ععععععع‬
‫عععع‬
Y
The
solutions
4X - Y > 12
5
X+Y > 4
4
3
2X + 5Y > 10
2
1
X
1
2
3
4
5
6
Find Extreme Points (Y2 Y3 Y4 ) :
Point B
X+ Y = 4
, 4X - Y = 12
Use a calculator X = 16/5
Y
Point
A
B
0
16/5
Y = 4/5
X
6
4/5
Z= 5X + 2Y
6×14 +3 ×12
The result $
5(16/5) + 2(4/5)
17.6 min
30
The objective function Z = 5X + 2Y = 5(16/5) + 2(4/5) = 88/5= 17.6
We find that the optimal solution is:
X = 16/5
Y = 4/5
Z = 88/5
1٥
Exercise:
(1) Find a solution following a linear programming problem using the graph
method:
Maximize
Z = 3x + 2y
subject to:
2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x≥0,y≥0
SX4RERE
Coordinates (x,y)
Objective value(Z)
C
G
H
F
(0,14)
(3,12)
(6,6)
(8,0)
28
33
30
24
(2) Find a solution following a linear programming problem using the graph
method:
16
1/--pages
Report inappropriate content