一般线性规划数学模型.doc

一般线性规划问题1. 线性规划的条件：1 决策变量有没有-必须有2 目标函数和约束条件是不是决策变量的线性表达式-必须是3 决策变量非负条件是否满足-必须满足4 目标函数是否表现出极大化或极小化-必须表现2. 线性规划的表达式 目标函数： 约束条件：.非负性约束：问题重述某储蓄所每天的营业时间是上午9时到下午5时。根据经验，每天不同时间段所需要的服务员数量如表17所示。储蓄所可以雇用全时和半时两类服务员。全时服务员每天报酬100元，从上午9时到下午5时工作，但中午12时到下午2时之间必须安排1h的午餐时间。储蓄所每天可以雇用不超过3名的半时服务员，每个半小时服务员必须连续工作4h，报酬40元。（1）问该储蓄所应如何雇用全时和半时两类服务员。（2）如果不能雇用半时服务员，每天至少增加多少费用。（3）如果雇用半时服务员的数量没有限制，每天可以减少多少费用？表16 每天不同时间段所需要的服务员数量时间段/时9-1010-1111-1212-1313-1414-1515-1616-17服务员数量/人43465688附表为储蓄所每天每个时段所需的服务员数量，建立数学模型，解决如下问题：对储蓄所的雇用选择数学模型进行分析，特别说明怎么样建立一个能够说明全时服务员雇用人数、半时服务员雇用人数及储蓄所支付工资最少的方案，并阐明这样建立模型的理由。基本假设（1）服务员在工作期间，无因事而有请假、半退等情况；（2）在12-14时间段，全时服务员能够做到分段休息的安排，以保证储蓄所在这个时间段的营业；（3）每个服务员都具备着良好的服务能力，保证每个人做到各司其职，效率良好。【符号约定】 ：储蓄所支付服务员最小工资数；x1：12-13时间段全时服务员仍在工作的人数；x2：13-14时间段全时服务员仍在工作的人数；y1：9点半时服务员开始工作的人数；y2：10点半时服务员开始工作的人数；y3：11点半时服务员开始工作的人数；y4：12点半时服务员开始工作的人数；y5：13点半时服务员开始工作的人数；问题分析问题提出要说明全时服务员要雇用多少人，半时服务员又要雇用多少人，在满足储蓄所日常正常经营下，使得储蓄所支付最少服务员的工资，使自己有最大的净利润。因此在此问题上，我们建立起数学中最常见的线性规划的模型，并利用MATLAB或者LINGO等数学软件，帮助我们快速解题。我们在数学模型搭建过程中，假设剔除掉影响变量的不可控因素，比如，在工作期间，某服务员由于家里出事，急忙请假等，这些不可控因素直接导致整个模型架难以搭起，所以进行合理化假设。这样，我们整个线性规划模型搭建起来。模型的建立与求解问题一根据每天不同时间段所需要的服务员数量，列出所有变量的不等式关系。=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5;x1+x2+y14;x1+x2+y1+y23;x1+x2+y1+y2+y34;x1+y1+y2+y3+y46;x2+y2+y3+y4+y55;x1+x2+y3+y4+y56;x1+x2+y4+y58;x1+x2+y58;y1+y2+y3+y4+y53; 从而将实际问题模型转化成数学中求解线性规划问题的模型。通过MATLAB软件中的linprog函数，求出使储蓄所获得最大净利润时所有变量的值(由于解决的是实际问题，所以求出的变量值(人数)必须是整数，所以用linprog函数时需要改成整形函数，即intlinprog)。从而得到招聘的一种方案。即 12-13时间段全时服务员仍在工作的人数x1为4人； 13-14时间段全时服务员仍在工作的人数x2为3人； 9点半时服务员开始工作的人数y1为0人； 10点半时服务员开始工作的人数y2为0人； 11点半时服务员开始工作的人数y3为2人； 12点半时服务员开始工作的人数y4为0人； 13点半时服务员开始工作的人数y5为1人。所以这种方案储蓄所的每天总花费为820元。或者通过LINGO软件进行不等式求解，得到另一种招聘方案： 12-13时间段全时服务员仍在工作的人数x1为4人； 13-14时间段全时服务员仍在工作的人数x2为3人； 9点半时服务员开始工作的人数y1为0人； 10点半时服务员开始工作的人数y2为2人； 11点半时服务员开始工作的人数y3为0人； 12点半时服务员开始工作的人数y4为0人； 13点半时服务员开始工作的人数y5为1人。这种方案储蓄所的每天总花费也为820元。（2）问题二 问题二的处理方式和问题一一样。首先列出变量的关系式： min=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5; x1+x2+y14; x1+x2+y1+y23; x1+x2+y1+y2+y34; x1+y1+y2+y3+y46; x2+y2+y3+y4+y55; x1+x2+y3+y4+y56; x1+x2+y4+y58; x1+x2+y58; y1=0; y2=0; y3=0; y4=0; y5=0;利用MATLAB软件中的linprog函数进行处理。得到不能雇用半时服务员的雇用的最佳方案。即 12-13时间段全时服务员仍在工作的人数x1为6人； 13-14时间段全时服务员仍在工作的人数x2为5人； 9点半时服务员开始工作的人数y1为0人； 10点半时服务员开始工作的人数y2为0人； 11点半时服务员开始工作的人数y3为0人； 12点半时服务员开始工作的人数y4为0人； 13点半时服务员开始工作的人数y5为0人。此时储蓄所每天所需付给服务员的总金额为1100元，所以每天增加了280元的开支。或者利用LINGO软件对关系式进行处理，得到的雇用方案和上述方案相同。 （3）问题三 利用与问题一、问题二相同的方法，列出关系式： min=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5; x1+x2+y14; x1+x2+y1+y23; x1+x2+y1+y2+y34; x1+y1+y2+y3+y46; x2+y2+y3+y4+y55; x1+x2+y3+y4+y56; x1+x2+y4+y58; x1+x2+y58; 利用MATLAB软件中的linprog函数进行处理。得到雇用半时服务员的数量没有限制时的最佳雇佣方案： 12-13时间段全时服务员仍在工作的人数x1为0人； 13-14时间段全时服务员仍在工作的人数x2为0人； 9点半时服务员开始工作的人数y1为4人； 10点半时服务员开始工作的人数y2为0人； 11点半时服务员开始工作的人数y3为2人； 12点半时服务员开始工作的人数y4为0人； 13点半时服务员开始工作的人数y5为8人。 此时储蓄所每天所需付给服务员的总金额为540元，减少了280元的开支。同理利用LINGO软件对关系式进行处理得到另一种雇用方法： 12-13时间段全时服务员仍在工作的人数x1为0人； 13-14时间段全时服务员仍在工作的人数x2为0人； 9点半时服务员开始工作的人数y1为6人； 10点半时服务员开始工作的人数y2为0人； 11点半时服务员开始工作的人数y3为0人； 12点半时服务员开始工作的人数y4为0人； 13点半时服务员开始工作的人数y5为8人。 此时储蓄所每天所需付给服务员的总金额为540元，也减少了280元的开支。 Matlab代码：【1】f=100;100;40;40;40;40;40A=1 1 1 0 0 0 0;1 1 1 1 0 0 0;1 1 1 1 1 0 0;1 0 1 1 1 1 0;0 1 0 1 1 1 1;1 1 0 0 1 1 1;1 1 0 0 0 1 1;1 1 0 0 0 0 1;0 0 -1 -1 -1 -1 -1B=4;3;4;6;5;6;8;8;-3lb=zeros(7,1)x,fval=intlinprog(f,1,2,-A,-B,lb)【2】f=100;100A=1 1;1 1;1 1;1 0;0 1;1 1;1 1;1 1B=4;3;4;6;5;6;8;8lb=zeros(2,1)x,fval=intlinprog(f,1,2,-A,-B,lb)【3】f=100;100;40;40;40;40;40A=1 1 1 0 0 0 0;1 1 1 1 0 0 0;1 1 1 1 1 0 0;1 0 1 1 1 1 0;0 1 0 1 1 1 1;1 1 0 0 1 1 1;1 1 0 0 0 1 1;1 1 0 0 0 0 1B=4;3;4;6;5;6;8;8lb=zeros(7,1)x,fval=intlinprog(f,1,2,-A,-B,lb)Lingo代码：model1:min=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5;x1+x2+y1=4;x1+x2+y1+y2=3;x1+x2+y1+y2+y3=4;x1+y1+y2+y3+y4=6;x2+y2+y3+y4+y5=5;x1+x2+y3+y4+y5=6;x1+x2+y4+y5=8;x1+x2+y5=8;y1+y2+y3+y4+y5=4;x1+x2+y1+y2=3;x1+x2+y1+y2+y3=4;x1+y1+y2+y3+y4=6;x2+y2+y3+y4+y5=5;x1+x2+y3+y4+y5=6;x1+x2+y4+y5=8;x1+x2+y5=8;y1=0;y2=0;y3=0;y4=0;y5=0;gin(x1);gin(x2);gin(y1);gin(y2);gin(y3);gin(y4);gin(y5);endmodel3:min=100*x1+100*x2+40