Linear Programming

‫البرمجة الخطية‬

‫‪Linear Programming‬‬

‫تقدمت وسائل التحليل الرياضي للمشاكل الدارية والقتصادية تقدما كبيرا‬ ‫وتعتبر البرمجة الخطية إحدى هذه الوسائل وقد استخدمة كلمة‬ ‫‪ Programming‬كأداه تهدف إلى استغلل الموارد المتاحة للمنشاة من قوة‬ ‫عاملة ومواد أولية الخ لتحقيق اكبر عائد ممكن‪.‬‬ ‫وتهدف البرمجة الخطية إلى الجابة باسلوب التحليل الرياضي على بعض‬ ‫السئلة وحل المشاكل بما يحقق اكبر ربح ممكن أو اقل تكلفة ممكنة في ظل‬ ‫القيود والمحددات القائمة‪.‬‬ ‫وعموماُ فان أداء أي عمل بأفضل الوسائل يعني في حد ذاته البحث عن‬ ‫الحدود الدنيا أو القصوى‪ .‬فعندما تتعلق المشكلة بالتكاليف فان الهدف عادة‬ ‫يكون الوصول إلى الحد الدنى وإذا تعلق المر بالرباح فان الهدف يكون هو‬ ‫الوصول إلى الحد القصى‪.‬‬

‫صياغة المشكلة‪:‬‬ ‫المشكلت المثلية غالبا ما تاتي في صورة كلمية‪ .‬وتحدد طريقة الحل في‬ ‫تصوير المشكلة في شكل نموذج رياضي يعبر عن المشكلة‪ ،‬ومن ثم يحل هذا‬ ‫النموذج بالساليب المختلفة‪ .‬ويمكن اتباع الخطواط التالية في بناء النموذج‬ ‫الرياضي‪.‬‬ ‫‪1‬‬

‫‪)1‬حدد الكميات التي تحتاج الى قيم مثلى‪ .‬وعرفها كمتغيرات لتاخذ‬ ‫الرموز ‪x1, x2, …, xn‬‬ ‫‪)2‬عرف هدف المشكلة وغبر عنه رياضيا باستخدام المتغيرات ‪.‬‬ ‫‪)3‬حدد ومثل القيود في صورة متباينات وذلك باستخدام المتغيرات‪.‬‬ ‫‪)4‬اضف الى النموذج الرياضي شرط عدم السالبية( ان جميع‬ ‫المتغيرات يجب ان تكون اكبر من او تساوي الصفر)‪.‬‬

‫مثال ‪:1‬‬ ‫يقوم جزار بعمل شطائر اللحم بتكوين من لحم بقري ولحم ماعز‪ .‬يحتوي لحم‬ ‫الب قر على ‪ 80%‬ل حم و ‪ 20%‬دهون ويكلف ‪ 24‬جن يه ل كل كيلو في ح ين ان‬ ‫لحم الماعز على ‪ 68%‬لحم و ‪ 32%‬دهون ويكلف ‪ 18‬جنيه لكل كيلو‪ .‬ماهي‬ ‫كم ية الل حم من كل نوع ي جب ان ي ستخدمها الم حل في كل كيلو من شطائر‬ ‫اللحسم اذا علمست انسه يجسب تخفيسض التكاليسف والمحافظسة علي نسسبة الدهون‪.‬‬ ‫بحيث ليذيد عن ‪25%‬؟‬

‫الحل‪:‬‬ ‫المتغيرات‪:‬‬ ‫نفرض ان وزن لحم البقر المستخدم في الكيلو = ‪X‬‬ ‫‪2‬‬

‫نفرض ان وزن لحم الماعز المستخدم في الكيلو = ‪Y‬‬

‫دالة الهدف‪:‬‬ ‫تصغير‬

‫‪Min Z = 24X + 18Y‬‬

‫القيود‪:‬‬ ‫الق يد الول‪ :‬يحتوي كل كيلو علي ‪ X 0.20‬من الدهون من ل حم الب قر و‬ ‫‪ 0.32Y‬من الدهون من ل حم الما عز وي جب ال تز يد الدهون في الشطيرة‬ ‫عن ‪. 0.25‬‬ ‫‪0.20 X + 0.32 Y ≤ 0.25‬‬ ‫القيد الثاني‪ :‬وي جب ان يكون وزن لحم الب قر و لحم الما عز مجتمعين في‬ ‫كل كيلو من الشطائر هو كيلو واحد‪.‬‬ ‫‪X+Y=1‬‬

‫القيد الثالث‪ :‬قيد عدم السالبية‬ ‫‪Y≥0‬و ‪X≥0‬‬

‫النموذج الرياضي‪:‬‬ ‫تصغير‬ ‫علم َا بان‪:‬‬

‫‪Min Z = 24X + 18Y‬‬

‫‪X + 0.32 Y ≤ 0.25 0.20‬‬ ‫‪X+Y=1‬‬ ‫‪Y≥0‬و ‪X≥0‬‬ ‫‪3‬‬

‫الحل البياني للمثال رقم ‪1‬‬ ‫للحصول علي السم الباني الممثل للمشكلة يتم اتباع الخطوات التالية‪:‬‬ ‫‪.1‬رسم محوري العمودي ‪ X‬والراسي ‪ Y‬كا هو موضح بالرسم التالي‬

‫>‬ ‫‪.2‬رسم القيود كما يلي‪:‬‬ ‫القيد الول ‪:‬‬ ‫بفرض ان ‪ X= 0‬نجد ان ‪ Y = 0.78‬نحصل على النقطة ((‪0.78 ,0‬‬ ‫بفرض ان ‪ Y = 0‬نجد ان ‪ X = 1.25‬نحصل على النقطة ((‪0 ,1.25‬‬ ‫نوقع النقتطين ((‪ 0.78 ,0‬و ((‪ 0 ,1.25‬علي الرسم‪.‬‬

‫القيد الثاني ‪:‬‬ ‫بفرض ان ‪ X= 0‬نجد ان ‪ Y = 1‬نحصل على النقطة ((‪1 ,0‬‬ ‫بفرض ان ‪ Y = 0‬نجد ان ‪ X = 1‬نحصل على النقطة ((‪0 ,1‬‬ ‫نوقع النقتطين ((‪ 1 ,0‬و ((‪ 0 ,1‬علي الرسم‪.‬‬ ‫بحل المعادلتين‪:‬‬

‫‪4‬‬

0.20 X + 0.32 Y ≤ 0.25 ‫ و‬X + Y = 1

5

‫نحصل على‪:‬‬ ‫‪X* = 7/12 , Y* = 5/12‬‬ ‫‪ Z = 24 )7/12) + 18) 5/12)= 21‬نجد ان ‪ Z‬بالتعويض في‬ ‫مما بعني ان المحال يجب ان يستخدم ‪7/12‬من لحم البقر والباقي ‪5/12‬‬ ‫من لحم الماعز وذلك يحقق اقل تكلفة والتي تساوي ‪ 21‬جنيه للكيلو‪.‬‬

‫مثال ‪2‬‬ ‫حل البرمجة الخطية التالية باستخدام طريقة الرسم البياني‬ ‫صغر ‪Min z = 5X + 2Y‬‬ ‫‪s.t.‬‬ ‫‪2X + 5Y > 10‬‬ ‫‪4X - Y > 12‬‬ ‫‪X+ Y> 4‬‬ ‫‪X, Y > 0‬‬ ‫رسم القيود‪:‬‬

‫القيد الول‪:‬‬

‫‪4X - Y > 12‬‬ ‫‪6‬‬

‫بفرض ان ‪ ,Y = 0‬نجد ان ‪ X = 5‬وعندما نفرض ان ‪ X = 0‬نجد ان‬ ‫‪Y=2‬‬ ‫اذا وصل النقتطين (‪ ) 0,5‬و (‪)2,0‬‬

‫القيد الثاني‪:‬‬

‫‪X+Y > 4‬‬

‫بفرض ان ‪ ,Y = 0‬نجد ان ‪ X = 3‬وعندما نفرض ان ‪ X = 0‬نجد ان‬ ‫‪ Y = -12‬والتي ليست على الرسم لذلك لذلك نفرض ان ‪ X = 5‬نجد ان‬ ‫‪Y=8‬‬ ‫اذا وصل النقتطين (‪ ) 3,0‬و (‪)5,8‬‬ ‫القيد الثالث‪X + Y > 4 :‬‬ ‫بفرض ان ‪ ,Y = 0‬نجد ان ‪ X = 4‬وعندما نفرض ان ‪ X = 0‬نجد ان‬ ‫‪Y=4‬‬ ‫إذا وصل النقتطين (‪ ) 0,4‬و (‪)4,0‬‬

‫‪Y‬‬ ‫منطقة الحلول‬ ‫‪4X - Y > 12‬‬

‫‪5‬‬

‫‪X+Y > 4‬‬

‫‪4‬‬ ‫‪3‬‬

‫‪7‬‬

‫‪2‬‬

‫‪2X + 5Y > 10‬‬

‫‪1‬‬ ‫‪X‬‬ ‫‪6‬‬

‫‪5‬‬

‫‪4‬‬

‫‪3‬‬

‫‪2‬‬

‫‪1‬‬

‫رسم دالة الهدف‪:‬‬ ‫افرض ان دالة الهدف تساوي أي رقم اختياري وليكن ‪20‬‬

‫اذا ‪,5X + 2Y = 20‬‬ ‫عندما ‪ ,X = 0‬اذاُ ‪Y = 10‬‬ ‫وعندما ‪ ,Y= 0‬اذا ‪.X = 4‬‬ ‫وصل النقتطين (‪ )4,0‬و (‪.)0,10‬‬ ‫حرك دالة الهدف في اتجاة تصغير القيمة حتى تصل إلى أخر نقطة في منطقة‬ ‫بأخر قيدين‪.‬‬ ‫المحددة ‪Min‬‬ ‫الحلول‪z = 5X‬‬ ‫‪+ 2Y‬‬

‫‪Y‬‬

‫‪4X - Y > 12‬‬

‫‪5‬‬

‫‪X+Y > 4‬‬

‫‪4‬‬ ‫‪8‬‬

‫‪3‬‬

‫‪2X + 5Y > 10‬‬

‫‪2‬‬ ‫‪1‬‬

‫‪X‬‬ ‫‪6‬‬

‫‪5‬‬

‫‪4‬‬

‫‪3‬‬

‫‪2‬‬

‫‪1‬‬

‫حل نقط التقاطع للقيود الحاكمة التي يقع عليها الحل‬ ‫‪X+ Y = 4‬‬

‫‪4X - Y = 12 ,‬‬ ‫بحل المعادلتين السابقتين نجد ان‪:‬‬

‫‪.5X = 16 or X = 16/5‬‬ ‫بالتعويض في‬

‫‪X+Y=4‬‬ ‫‪9‬‬

‫نجد ان ‪Y = 4/5‬‬

10

‫بالتعويض في دالة الهدف كما يلي‪:‬‬ ‫‪.z = 5X + 2Y = 5(16/5) + 2(4/5) = 88/5‬‬ ‫نجد ان الحل المثل هو‪:‬‬ ‫‪X = 16/5; Y = 4/5; z = 88/5‬‬

‫كما هو موضح بالرسم التالي‬

‫‪Min z = 5X + 2Y‬‬ ‫‪4X - Y> 12‬‬

‫‪5‬‬

‫‪X+Y > 4‬‬

‫‪4‬‬ ‫‪2X + 5Y > 10‬‬

‫‪3‬‬

‫‪Optimal:‬‬ ‫‪X = 16/5‬‬ ‫‪Y = 4/5‬‬

‫‪2‬‬ ‫‪6‬‬

‫‪4‬‬

‫‪5‬‬

‫‪11‬‬

‫‪3‬‬

‫‪2‬‬

‫‪1‬‬

‫البرمجة الخطية‬ ‫باستخدام طريقة السمبلكس‬ ‫‪Linear Porogramming Using Simplex Method‬‬

‫نظرا لن طريقة الحل بالرسم البياني ل تصلح لكثر من اثنين او ثلث‬ ‫متغيرات وكذلك لو نظرنا الي المشكلت الواقعية نجد ان معظم المشكلت‬ ‫فسي الواقسع العملي تحتوي على العديسد مسن المتغيرات ممسا يصسعب اسستخدام‬ ‫الطرق البيانية في الحل‪ .‬ومن ثم استلزم وجود طرق اخري للتعامل مع مثل‬ ‫هذة المشكلت‪ .‬ومسن بيسن هذه الطرق والتسي تصسلح للتعامسل مسع مشكلت‬ ‫البرمجة الخطية طريقة السمبلكس ‪ .Simplex Method‬بالضافة لصلحية‬ ‫هذة الطريقسة للتعامسل مسع المشكلت ذات المتغيرات كثيرة العدد فانسه يوجسد‬ ‫الكثير من برامج الحاسب اللي التي تعمل وفق هذه الطلريقة والتي يمكن ان‬ ‫ت ستخدم ل حل مشا كل البرم جة الخط ية ذات البعاد ال كبيرة ( عدد كبير من‬ ‫المتغيرات وعدد كبير من القيود) والتى تعطي حلول في اوقات صغيرة جدا‬ ‫وتجيب علي كثير من التسائلت ومن اشهر تلك التسائلت ما يعرف ب ماذا‬ ‫لو ‪ .what if qustions‬وفيما يلي سوف نعرض الخطوات الرئيسية لطريقة‬ ‫السمبلكس‪.‬‬

‫‪12‬‬

‫طريقة السمبلكس‬ ‫وفي ما يلي يم كن اتباع الخطوات التال ية للو صول الى ال حل الم ثل من خلل‬ ‫استخدام طريقة السمبلكس‪.‬‬ ‫‪.1‬حدد اعلى قيمسة سسالبة فسي الصسف السسفلي مسن جدول السسمبلكس‬ ‫باسستثناء العمود الخيسر‪ ,‬ويطلق على العمود الذي تظهسر فيسه هذة‬ ‫القيمة عمود العمل‪ .‬في حالة تساوي اكثر من قيمة اختار احداهما‪.‬‬ ‫‪.2‬كون نسبا من خلل قسمة القيم الموجبة في عمود العمل علي القيم‬ ‫المناظرة لها في اخر عمود وذلك باستثناء اخر صف‪ .‬وان لم يوجد‬ ‫قيم موجبة في عمود العمل فان المشكلة ليس لها حل‪.‬‬ ‫‪.3‬اختار العنصسر الذي ينتمسي الي عمود العمسل والذي له اقسل نسسبة‬ ‫(يسمى العنصلر المحوري)‬ ‫‪.4‬اسستخدم العمليات الوليسة لتحويسل العنصسر المحوري الى واحسد‬ ‫صحيح وبقي العمود اصفار‪.‬‬ ‫‪.5‬استبدل المتغير ‪ x‬في صف المحور والعمود الول بالمتغير ‪ x‬في‬ ‫الصف الول وعمود المحور (عمود المتغيرات الساسية)‪.‬‬ ‫‪.6‬كرر الخطوات مسن ‪ 5-1‬حتسى تحصسل على جدول ليسس بسه اعداد‬ ‫سالبة في الصف الخير باستثناء العمود الخير‪.‬‬

‫‪13‬‬

‫‪.7‬نحصل على الحل المثل من خلل تخصيص كل في العمود الخير‬ ‫والمتغير المناظر له في العمود الول ‪ .‬وباقي المتغيرات تاخذ قيمة‬ ‫صسفر‪ .‬والقيمسة المثلي للهدف ‪ *z‬هسي العدد الموجود فسي الصسف‬ ‫الخير والعمود الخير وذلك في حالة التعظييم‪ .‬والقيمة السالبة لهذا‬ ‫العدد في حالة التصغيير‪.‬‬

‫مثال ‪3‬‬ ‫تعظيم‬ ‫علم َا بان‪:‬‬

‫‪Max Z = x1 + 9x2 + x3‬‬

‫‪x1 + 2x2 + 3 x3 ≤ 9‬‬ ‫‪3 x1 + 2x2 + 2 x3 ≤ 15‬‬ ‫‪x1 , x2 , x3 ≥ 0‬‬

‫الحل‪:‬‬ ‫تحويل المتباينات الي الصيغة القياسية كما يالي‪:‬‬ ‫‪Max Z = x1 + 9x2 + x3+ x4 + x5‬‬ ‫علم َا بان‪:‬‬

‫‪=9‬‬

‫‪x1 + 2x2 + 3 x3 + x4‬‬

‫‪3 x1 + 2x2 + 2 x3 + x5 = 15‬‬ ‫‪x1 , x2 , x3, x4 , x5 ≥ 0‬‬ ‫تكوين جدول السمبلكس من الصيغة القياسية كما يالي‪:‬‬ ‫‪14‬‬

‫‪x5‬‬

‫‪x4‬‬

‫‪x3‬‬

‫‪x2‬‬

‫‪x1‬‬

‫‪0‬‬

‫‪0‬‬

‫‪1‬‬

‫‪9‬‬

‫‪1‬‬

‫‪9‬‬

‫‪0‬‬

‫‪1‬‬

‫‪3‬‬

‫*‪2‬‬

‫‪1‬‬

‫‪0‬‬

‫‪x4‬‬

‫‪15‬‬

‫‪1‬‬

‫‪0‬‬

‫‪2‬‬

‫‪2‬‬

‫‪3‬‬

‫‪0‬‬

‫‪x5‬‬

‫‪0‬‬

‫‪0‬‬

‫‪0‬‬

‫‪1-‬‬

‫‪9-‬‬

‫‪1-‬‬

‫‪zj-cj‬‬

‫لحساب الصف الخير من الجدول السابق يمكن تطبيف مايلي‪:‬‬ ‫‪ =Zj‬حاصل ضرب قيم العمود الثا ني في القيم المناظرة ل ها في با قي العمدة‬ ‫ثم جمع حاصل الضرب لجميع قيم العمود‪.‬‬ ‫‪ = zj-cj‬القيم المحسوبة سابقا – القيمة المناظرة للعمود في الصف الول‪.‬‬ ‫اختيار العمود المحوري يكون العمود ‪ x2‬نظرا لنه صاحب اكبر قيمة‬ ‫اختيار الصسف المحوري بقسسمة جميسع قيسم العمود الخيسر على قيسم العمود‬ ‫المحوري الموجبة وذلك لتكوين النسب كمايلي‪15/2 , 9/2 :‬‬ ‫اختيار اقل نسبة ليكون وهي ‪ 9/2‬والتي تنتمي الي العنصر ‪ 2‬الموضح ب *‬ ‫في الجدول السابق‬ ‫انشاء الجدول التالي باستخدام العمليات الولية بتطبيق الخطوة ‪ 4‬و ‪ 5‬لنحصل‬ ‫على الجدول التالي‪:‬‬ ‫‪x5‬‬

‫‪x4‬‬

‫‪x2‬‬

‫‪x3‬‬

‫‪15‬‬

‫‪x1‬‬

‫‪0‬‬

‫‪0‬‬

‫‪1‬‬

‫‪9‬‬

‫‪1‬‬

‫‪9/2‬‬

‫‪0‬‬

‫‪1/2‬‬

‫‪3/2‬‬

‫‪1‬‬

‫‪1/2‬‬

‫‪9‬‬

‫‪x2‬‬

‫‪6‬‬

‫‪1‬‬

‫‪1-‬‬

‫‪1-‬‬

‫‪0‬‬

‫‪2‬‬

‫‪0‬‬

‫‪x5‬‬

‫‪81/2‬‬

‫‪0‬‬

‫‪9/2‬‬

‫‪25/2‬‬

‫‪0‬‬

‫‪7/2‬‬

‫‪zj-cj‬‬

‫نظرا لن الصف الخير في الجدول السابق كله قيم موجبة فانه يدل على اننا‬ ‫قد وصلنا الى الحل المثل وهو كما يلي‪:‬‬ ‫‪x*2 = 9/2 , x*1 = x*3= x*4= x*5 = 0 ,‬‬ ‫وذلك يعطي ربح اجمالي ‪ 81/2‬جنيه‪.‬‬

‫‪16‬‬

‫تطبيق على الحاسب اللي‬ ‫‪Computer Applications‬‬

‫تخطيط النتاج لمنتج واحد‬ ‫تلقى أحد مصانع السيارات طلبا بستة أتوبيسات ذات الدورين‪ ،‬على أن بقوم‬ ‫بتسليم اثنين في كل مرة خلل الثلثة اشهر التالية‪ .‬يتم تسليم التوبيسات‬ ‫للعميل في نهاية نفس شهر التجميع ‪ ،‬أو تخزينه لدى الشركة بتكلفة ‪3000‬‬ ‫دولر في الشهر لكل أتوبيس لتوريدها خلل الشهر التالي ‪ .‬ل يوجد مخزون‬ ‫حالي لدى الصانع من هذه التوبيسات‪ .‬ول يرغب في وجود مخزون في نهاية‬ ‫المدة بعد استكمال العرض‪.‬‬

‫الشهر‬ ‫‪1‬‬

‫‪2‬‬

‫‪3‬‬

‫الطاقة النتاجية العادية بالوحدة‬

‫‪10‬‬

‫‪20‬‬

‫‪30‬‬

‫الطاقة النتاجية الضافية بالوحدة‬

‫‪20‬‬

‫‪20‬‬

‫‪20‬‬

‫تكلفة النتاج العادية ‪1000‬‬ ‫دولر للوحدة‬

‫‪35‬‬

‫‪43‬‬

‫‪40‬‬

‫تكلفة النتاج الضافية ‪1000‬‬ ‫دولر للوحدة‬

‫‪39‬‬

‫‪47‬‬

‫‪45‬‬

‫‪17‬‬

‫للتعامل مع مثل هذه المشكلة يمكن بناء نموذج البرمجة الخطية التالي كما يلي‪:‬‬ ‫نفرض أن ‪ Xij‬يمثل عدد الوحدات المطلوب إنتاجها في الشهر ‪i‬‬ ‫لتوريدها في الشهر ‪ j‬بالطاقة العادية‪.‬‬ ‫نفرض أن ‪ Yij‬يمثل عدد الوحدات المطلوب إنتاجها في الشهر ‪i‬‬ ‫لتوريدها في الشهر ‪ j‬بالطاقة الضافية‪.‬‬

‫النموذج الرياضي لتخطيط النتاج لمنتج واحد‬ ‫دالة الهدف‪:‬‬ ‫الوصول إلى خطة إنتاج للتوبيسات المتعاقد عليها بأقل تكلفة ( تكلفة تصنيع‬ ‫‪ +.‬تكلفة تخزين ) ممكنة‬ ‫‪Min Z = 35 X11 +)35+3) X12 +)35+6) X13 +43 X22 +)43+3) X23‬‬ ‫‪+ 40 X33 + 39Y11 +)39+3) Y12 + )39+6) Y13 +47 Y22+‬‬ ‫‪)47+3) Y23 +45Y33‬‬ ‫‪Min Z = )35 X11 + 38 X12+ 41 X13+ 43 X22+ 46 X23 +40 X33) +‬‬ ‫)‪)39Y11 + 42Y12 + 45 Y13 +47 Y22+ 50 Y23 +45 Y33‬‬

‫قيود الطاقات النتاجية العادية‬ ‫الشهر الول‬

‫‪<= 10‬‬

‫الشهر الثاني‬

‫‪<= 20‬‬

‫‪X11 + X12+ X13‬‬ ‫‪X22+ X23‬‬ ‫‪18‬‬

‫‪X33 <= 30‬‬

‫الشهر الثالث‬

‫قيود الطاقات النتاجية الضافية‬ ‫‪<= 20‬‬

‫الشهر الول‬

‫‪Y11 + Y12 + Y13‬‬

‫‪<= 20‬‬

‫الشهر الثاني‬

‫‪Y22+ Y23‬‬

‫‪Y33 <= 20‬‬

‫الشهر الثالث‬ ‫قيود التوريد‬ ‫الشهر الول‬

‫‪>= 20‬‬

‫الشهر الثاني‬

‫‪>= 20‬‬

‫الشهر الثالث‬

‫‪X11 + Y11‬‬ ‫‪X12+Y12+ X22 + Y22‬‬

‫‪X13 + Y13 +X23 + Y23 + X33 + Y33 >= 20‬‬

‫قيود عدم السلبية‬ ‫‪>= 0‬‬

‫‪X11, X12, X13, X22, X23, X33, Y11, Y12, Y13, Y22, Y23, Y33‬‬

‫جميع الكميات اكبر من أو تساوي الصفر ( يقوم الحاسب بوضع هذا القيد)‬

‫‪19‬‬

‫حل النموذج الرياضي‬ ‫وباستخدام الحاسب اللي يمكن أن يحل هذا النموذج الرياضي للحصول على‬ ‫الخطضة النتاجيضة التضي تحقضق اقضل تكلفضة ممكنضة فضي ظضل القيود المفروضضة‬ ‫كالتالي‪:‬‬ ‫‪X11 = 10 , Y11 = 10 , Y12 = 10 , X22 = 10 , X33 = 20‬‬ ‫بتكلفة إجمالية ( ‪ 2390‬ألف دولر)‬ ‫ويمكن تلخيص خطة النتاج فيما يلي‪:‬‬ ‫إنتاج عدد ثلثون سياراة في الشهر الول للوفاء بتوريد الشهر الول‬ ‫وتخزين ‪10‬سيارات للشهر الثاني وذلك على النحو التالي‪:‬‬ ‫عدد ‪ 10‬سيارات بالطاقة العادية‪،‬‬ ‫عدد ‪ 20‬سيارة بالطاقة الضافية‪.‬‬ ‫إنتاج ‪10‬سيارات في الشهر الثاني بالطاقة العادية‪.‬‬ ‫إنتاج عدد ‪ 20‬سيارة في الشهر الثالث بالطاقة العادية‪.‬‬

‫‪20‬‬

‫مشاكل التخصيص‬ ‫‪Assignment Problems‬‬ ‫تتض من مشكلة التخ صيص جدولة العامل ين فردا فردا و من المفترض ان يكون‬ ‫عدد العامليسن مسساويا عدد العمال ويجسب ضمان هذا الشرط بإضافسة عامليسن‬ ‫وهمييسن او عمسل إضافيسة عنسد الحاجسة مسن اجسل المحافظسة على هذا الشرط‪.‬‬ ‫ويكون الزمسن (التكاليسف ‪cij )....‬اللزم للعامسل رقسم ‪ i‬لتمام العمسل رقسم ‪j‬‬ ‫معروفا ومسن ثسم يكون الهدف هسو تخصسيص العمال على العمال بحيسث تتسم‬ ‫إجمالي العمال في اقل وقت ممكن‪.‬‬

‫العمال‬ ‫‪n‬‬

‫‪...‬‬

‫‪3‬‬

‫‪2‬‬

‫‪1‬‬

‫‪C1n‬‬

‫‪...‬‬

‫‪C13‬‬

‫‪C12‬‬

‫‪C11‬‬

‫‪1‬‬

‫‪C2n‬‬

‫‪...‬‬

‫‪C23‬‬

‫‪C22‬‬

‫‪C21‬‬

‫‪2‬‬

‫‪C3n‬‬

‫‪...‬‬

‫‪C33‬‬

‫‪C32‬‬

‫‪C31‬‬

‫‪3‬‬

‫‪...‬‬

‫‪...‬‬

‫‪...‬‬

‫‪...‬‬

‫‪...‬‬

‫‪...‬‬

‫‪Cnn‬‬

‫‪...‬‬

‫‪Cn3‬‬

‫‪Cn2‬‬

‫‪Cn1‬‬

‫‪n‬‬

‫‪21‬‬

‫العمال‬

‫خطوات الحل‪:‬‬ ‫‪.1‬اطرح اقل قيمة في كل صف من كل القيم في هذا الصف‬ ‫‪.2‬اطرح اقل قيمة في كل عمود من كل القيم في هذا العمود‪.‬‬ ‫‪.3‬حدد اذا ما كان يو جد عدد ‪ n‬من ال صفار بح يث ل يو جد صفريين‬ ‫في نفس العمود او الصف‪.‬‬ ‫‪.4‬غسط كسل الصسفار فسي المصسفوفة بأقسل عدد مسن الخطوط الرئسسية‬ ‫والعرض ية بح يث يغ طي ال خط كل العمود او ال صف وبح يث يكون‬ ‫عدد الخطوط اقل من ‪ n‬وان يكون عدد ممكن من الخطوط‪.‬‬ ‫‪.5‬اطرح اقل عدد غير مغطى من القيم الغير مغطاة وأيضا أضف هذا‬ ‫للعدد إلى القيم المغطاة بخطيين متقاطعين (راسي وافقي)‬ ‫‪.6‬اختار عدد ‪ n‬مسن الصسفار بحيسث ل صسفريين فسي نفسس العمود او‬ ‫الصف وبذلك يكون تخصيص العمال الي العمال عندهم‪.‬‬ ‫‪.7‬احسسب إجمالي الوقست عسن طريسق جمسع جميسع القيسم محسل تلك‬ ‫الصفار‪.‬‬

‫‪22‬‬

‫مثال‪:‬‬ ‫ماكينة‬ ‫‪V‬‬

‫‪IV‬‬

‫‪III‬‬

‫‪II‬‬

‫‪I‬‬

‫‪10‬‬

‫‪25‬‬

‫‪25‬‬

‫‪10‬‬

‫‪15‬‬

‫‪A‬‬

‫‪2‬‬

‫‪20‬‬

‫‪10‬‬

‫‪8‬‬

‫‪1‬‬

‫‪B‬‬

‫‪10‬‬

‫‪20‬‬

‫‪17‬‬

‫‪9‬‬

‫‪8‬‬

‫‪C‬‬

‫‪15‬‬

‫‪27‬‬

‫‪25‬‬

‫‪10‬‬

‫‪14‬‬

‫‪D‬‬

‫‪12‬‬

‫‪27‬‬

‫‪25‬‬

‫‪8‬‬

‫‪10‬‬

‫‪E‬‬

‫عامل‬

‫الحل‪:‬‬ ‫بطرح ا قل قي مة في كل صف من كل الق يم في هذا ال صف نح صل عل‬ ‫المصفوفة التالية‪:‬‬ ‫ماكينة‬ ‫‪V‬‬

‫‪IV‬‬

‫‪III‬‬

‫‪II‬‬

‫‪I‬‬

‫‪0‬‬

‫‪15‬‬

‫‪15‬‬

‫‪0‬‬

‫‪5‬‬

‫‪A‬‬

‫‪1‬‬

‫‪19‬‬

‫‪9‬‬

‫‪7‬‬

‫‪0‬‬

‫‪B‬‬

‫‪2‬‬

‫‪12‬‬

‫‪9‬‬

‫‪1‬‬

‫‪0‬‬

‫‪C‬‬

‫‪5‬‬

‫‪17‬‬

‫‪15‬‬

‫‪0‬‬

‫‪4‬‬

‫‪D‬‬

‫‪4‬‬

‫‪19‬‬

‫‪17‬‬

‫‪0‬‬

‫‪2‬‬

‫‪E‬‬

‫عامل‬

‫بطرح ا قل قي مة في كل عمود من كل الق يم في هذا العمود نح صل عل‬ ‫المصفوفة التالية‪:‬‬

‫‪23‬‬

‫ماكينة‬ ‫‪V‬‬

‫‪IV‬‬

‫‪III‬‬

‫‪II‬‬

‫‪I‬‬

‫‪0‬‬

‫‪3‬‬

‫‪6‬‬

‫‪0‬‬

‫‪5‬‬

‫‪A‬‬

‫‪1‬‬

‫‪7‬‬

‫‪0‬‬

‫‪7‬‬

‫‪0‬‬

‫‪B‬‬

‫‪2‬‬

‫‪0‬‬

‫‪0‬‬

‫‪1‬‬

‫‪0‬‬

‫‪C‬‬

‫‪5‬‬

‫‪5‬‬

‫‪6‬‬

‫‪0‬‬

‫‪4‬‬

‫‪D‬‬

‫‪4‬‬

‫‪7‬‬

‫‪8‬‬

‫‪0‬‬

‫‪2‬‬

‫‪E‬‬

‫عامل‬

‫نل حظ ا نه ليو جد عدد ‪ n‬من ال صفار وغ ير مشتر كة في صف او عمود لذا‬ ‫يجسب تغطيسة كسل الصسفار فسي المصسفوفة بأقسل عدد مسن الخطوط الرئيسسية‬ ‫والعرضيسة بحيسث يغطسي الخسط كسل العمود او الصسف وبحيسث يكون عدد‬ ‫الخطوط اقل من ‪ n‬وان يكون عدد ممكن من الخطوط انظر المصفوفة التالية‪:‬‬ ‫ماكينة‬ ‫‪V‬‬

‫‪IV‬‬

‫‪III‬‬

‫‪II‬‬

‫‪I‬‬

‫‪0‬‬

‫‪3‬‬

‫‪6‬‬

‫‪0‬‬

‫‪5‬‬

‫‪A‬‬

‫‪1‬‬

‫‪7‬‬

‫‪0‬‬

‫‪7‬‬

‫‪0‬‬

‫‪B‬‬

‫‪2‬‬

‫‪0‬‬

‫‪0‬‬

‫‪1‬‬

‫‪0‬‬

‫‪C‬‬

‫‪5‬‬

‫‪5‬‬

‫‪6‬‬

‫‪0‬‬

‫‪4‬‬

‫‪D‬‬

‫‪4‬‬

‫‪7‬‬

‫‪8‬‬

‫‪0‬‬

‫‪2‬‬

‫‪E‬‬

‫عامل‬

‫نب حث عن ا قل قي مة غي مغطاة و هي (‪ )2‬اطرح ها من الق يم الغ ير مغطاة‬ ‫وأيضسا أضسف هذا للعدد (‪ )2‬إلى القيسم المغطاة بخطييسن متقاطعيسن (راسسي‬ ‫وافقي) فنحصل علي المصفوفة التالية‪:‬‬ ‫‪24‬‬

‫ماكينة‬ ‫‪V‬‬

‫‪IV‬‬

‫‪III‬‬

‫‪II‬‬

‫‪I‬‬

‫‪0‬‬

‫‪3‬‬

‫‪6‬‬

‫‪2‬‬

‫‪5‬‬

‫‪A‬‬

‫‪1‬‬

‫‪7‬‬

‫‪0‬‬

‫‪9‬‬

‫‪0‬‬

‫‪B‬‬

‫‪2‬‬

‫‪0‬‬

‫‪0‬‬

‫‪3‬‬

‫‪0‬‬

‫‪C‬‬

‫‪3‬‬

‫‪3‬‬

‫‪4‬‬

‫‪0‬‬

‫‪2‬‬

‫‪D‬‬

‫‪2‬‬

‫‪5‬‬

‫‪6‬‬

‫‪0‬‬

‫‪0‬‬

‫‪E‬‬

‫عامل‬

‫بالنظسر الي المصسفوفة السسابقة نجسد انسه يوجسد عدد ‪ n‬مسن الصسفار بحيسث ل‬ ‫صفريين في ن فس العمود او الصف وبذلك يكون تخ صيص العمال الي العمالة‬ ‫عندهم‪ .‬انظر المصفوفة التالية‪:‬‬ ‫ماكينة‬ ‫‪V‬‬

‫‪IV‬‬

‫‪III‬‬

‫‪II‬‬

‫‪I‬‬

‫‪0‬‬

‫‪3‬‬

‫‪6‬‬

‫‪2‬‬

‫‪5‬‬

‫‪A‬‬

‫‪1‬‬

‫‪7‬‬

‫‪0‬‬

‫‪9‬‬

‫‪0‬‬

‫‪B‬‬

‫‪2‬‬

‫‪0‬‬

‫‪0‬‬

‫‪3‬‬

‫‪0‬‬

‫‪C‬‬

‫‪3‬‬

‫‪3‬‬

‫‪4‬‬

‫‪0‬‬

‫‪2‬‬

‫‪D‬‬

‫‪2‬‬

‫‪5‬‬

‫‪6‬‬

‫‪0‬‬

‫‪0‬‬

‫‪E‬‬

‫عامل‬

‫احسب إجمالي الوقت عن طريق جمع جميع القيم محل تلك الصفار كما يلي‪:‬‬ ‫إجمالي اقل التكلفة = ‪A V + B III+ C IV + D II +E I‬‬ ‫‪= 10 +10 +20 +10 + 10‬‬

‫‪25‬‬

‫= ‪60‬‬ ‫تلخيص الحل‪:‬‬ ‫يتم تخصيص العامل ‪ A‬علي الماكينة ‪V‬‬ ‫و يتم تخصيص العامل ‪ B‬علي الماكينة ‪III‬‬ ‫و يتم تخصيص العامل ‪ C‬علي الماكينة ‪IV‬‬ ‫و يتم تخصيص العامل ‪ D‬علي الماكينة ‪II‬‬ ‫و يتم تخصيص العامل ‪ A‬علي الماكينة ‪I‬‬ ‫بإجمالي اقل التكلفة = ‪ 60‬جنية‪.‬‬

‫‪26‬‬

‫تمارين علي البرمجة الخطية‬ ‫تمرين ‪:1‬‬

‫شركه تقدم بإنتاج نوعين من هياكل الدرجات النوع ألاول الفاخر والثاني والتي‬ ‫يتم إنتاجها باستخدام نوعين من المواد الخام وهي اللومونيوم والحديد وكان‬ ‫ربح الوحدة من الهياكل الفاخرة يقدم بمقدار ‪10‬ج ‪ ،‬والثاني لهياكل الدراجات‬ ‫المحترفين بقدر ‪15‬ج‪.‬‬ ‫اللومونيوم‬

‫الحديد‬

‫الهياكل الفاخرة‬

‫‪2‬‬

‫‪3‬‬

‫لهياكل الدراجات‬

‫‪4‬‬

‫‪2‬‬

‫المحترفين‬ ‫ما هو عدد الهياكل التي يجب على الشركة انتاجها علماً بان إجمالي اللومنيوم‬ ‫المستخدم في السبوع ل يتعدى ‪ 100‬كجم وان إجمالي الحديد الصلب المستخدم‬ ‫في السبوع ‪80‬‬

‫كجم وذلك لتعظيم ربح الشركة‪ .‬كون النموذج الرياضي‬

‫للمشكلة‬ ‫الحل‬ ‫‪------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪27‬‬

‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫تمرين ‪:2‬‬

‫‪28‬‬

‫استخدم طريقة الرسم البياني لحل المشكلة بالتمرين السابق‬ ‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪29‬‬

‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪------------------------------------------------------------------‬‬‫تمرين ‪:3‬‬ ‫استخدم طريقة السمبلكس لحل المشكلة التالية‪:‬‬ ‫‪30‬‬

Max Z = 3x1 + 9x2 + x3

‫تعظيم‬

x1 + 2x2 + 3 x3 ≤ 18

:‫علم َا بان‬

6 x1 + 4x2 + 4 x3 ≤ 30 x1 , x2 , x3 ≥ 0 -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------31

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

32

‫تمرين ‪:4‬‬ ‫استخدم طريقة الرسم البياني لحل المشكلة بالتمرين السابق‬ ‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪33‬‬

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------34

‫تمارين علي مشاكل التخصيص‬ ‫تمرين ‪1‬‬ ‫احسب أحسن تخصيص للعمالة على مجموعة الماكينات والذي يحقق اقل تكلف‬ ‫طبقا للمعلومات المتوفرة في المصفوفة التالية‪:‬‬ ‫ماكينة‬ ‫‪M5‬‬

‫‪M4‬‬

‫‪M3‬‬

‫‪M2‬‬

‫‪M1‬‬

‫‪10‬‬

‫‪25‬‬

‫‪25‬‬

‫‪10‬‬

‫‪15‬‬

‫‪E1‬‬

‫‪15‬‬

‫‪27‬‬

‫‪25‬‬

‫‪10‬‬

‫‪14‬‬

‫‪E2‬‬

‫‪10‬‬

‫‪20‬‬

‫‪17‬‬

‫‪9‬‬

‫‪8‬‬

‫‪E3‬‬

‫‪2‬‬

‫‪20‬‬

‫‪10‬‬

‫‪8‬‬

‫‪1‬‬

‫‪E4‬‬

‫‪12‬‬

‫‪27‬‬

‫‪25‬‬

‫‪8‬‬

‫‪10‬‬

‫‪E5‬‬

‫عامل‬

‫الحل‪:‬‬ ‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪35‬‬

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

36

‫تمرين ‪2‬‬ ‫احسب أحسن تخصيص المقاولون على مجموعة المشروعات والذي يحقق اقل‬ ‫تكاليف طبقا للمعلومات المتوفرة في المصفوفة التالية‪:‬‬ ‫مشروع‬ ‫‪P5‬‬

‫‪P4‬‬

‫‪P3‬‬

‫‪P2‬‬

‫‪P1‬‬

‫‪10‬‬

‫‪25‬‬

‫‪25‬‬

‫‪10‬‬

‫‪15‬‬

‫‪C1‬‬

‫‪15‬‬

‫‪27‬‬

‫‪25‬‬

‫‪10‬‬

‫‪14‬‬

‫‪C2‬‬

‫‪10‬‬

‫‪20‬‬

‫‪17‬‬

‫‪9‬‬

‫‪8‬‬

‫‪C3‬‬

‫‪2‬‬

‫‪20‬‬

‫‪10‬‬

‫‪8‬‬

‫‪1‬‬

‫‪C4‬‬

‫‪12‬‬

‫‪27‬‬

‫‪25‬‬

‫‪8‬‬

‫‪10‬‬

‫‪C5‬‬

‫مقاول‬

‫الحل‪:‬‬ ‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪-------------------------------------------------------------------------‬‬‫‪37‬‬

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

38