青島某旅游公司五一長假準備推出旅游兩日游套餐。旅游項目選擇以下 7 種組合(見表 1)：

旅游公司計劃在上述 7 種景點組合中選擇 3 種組成二日游套餐。 由于疫情期間，為了預防人的聚集，各景點對旅游團人數有一定限制， 每兩天該旅行社到各景點組合的人數配額限制，且不同的景點組合每 個游客給旅游公司帶來的收益不同(見表 1)。根據公司的條件，公司 計劃每兩天最多安排 2100 人的旅游計劃。

如果景點 1 是必選項，且以收益最大為目標，應該推出哪幾種二日游套餐，每種套餐各有多少人？

旅游期間要配備旅游車。由于疫情期間人與人的間距要求，每輛車最多搭載旅客 26 人，并要求接待旅游人數不低于 2000人。如果在需求車輛數最小的前提下收益最大，應該推出哪幾種二日游套餐，每種套餐各多少人？

不再把景點 1 作為必選項，考慮到有些景觀差異性較小，以及景點距離太大費用較大，因此在設計旅游套餐時增加規定：第2、3、6 這 3 類景區必須且只需選擇一個，第 6 和第 7 不能同時選取，第1 和第 4 不能同時選取，并要求總接待人數不低于1200。在這種要求下，按照在車輛最少的前提下收益最高的目標，旅游套餐的選擇方案應如何制定？

---

反思：不算很難的一次測試，但是自己還是拉了胯，總感覺自己想出的模型已經天衣無縫了，一度在懷疑是優化軟件的問題，但實際上還是可以優化的，歸根結底還是自己太菜了，吸取到的教訓就是以后建模能盡量多開變量就不要少開，不要弄那些花里胡哨的化簡來減少變量的數量

模型分析：結合下料問題以及學生選課問題這兩個模型，不難確定如下變量：

a[ i ] ：景區 i 的收益單價

b[ i ] ：景區 i 的人數限制

y[ j?] ：選擇套餐 j 的人數

w[ j ] ：套餐 j 的收益單價

x[ j ] ：套餐 j 需要車的數量（第二問第三問需要用到）

第一問

在讀懂題目后不難想到，可以直接暴力枚舉出所有的可行方案生成套餐，因為第一問中約束了景區 1?是必選的，那么剩下的 6 個景區內需要選出 2 個，共 C( 6 , 2 ) = 15 種方案，到此為止不難寫出第一問的程序了（約束條件直接看代碼吧，懶得另寫了）

最大收益：264600

sets: t1/1..7/:a,b; t2/1..15/:w,y; endsets max=@sum(t2:y*w); @sum(t2:y)<=2100; y(1)+y(2)+y(3)+y(4)+y(5)<=b(2); y(1)+y(6)+y(7)+y(8)+y(9)<=b(3); y(2)+y(6)+y(10)+y(11)+y(12)<=b(4); y(3)+y(7)+y(10)+y(13)+y(14)<=b(5); y(4)+y(8)+y(11)+y(13)+y(15)<=b(6); y(5)+y(9)+y(12)+y(14)+y(15)<=b(7); @for(t2:@gin(y)); data: b=2500,900,600,400,550,1100,650; a=36,36,40,48,40,50,56; w=112,120,112,122,128,124,116,126,132,124,134,140,126,132,142; @text()=@table(y); enddata

第二問

第二問的話有兩個目標函數，但其實可以分解成兩個小問題，因為題目已經標明了兩個目標函數的先后順序了，在第一問的基礎上加上約束變量?就可以求出最小的車輛數了

最小車輛：77

sets: t1/1..7/:a,b; t2/1..15/:w,y,x; endsets min=@sum(t2:x); @sum(t2:y)<=2100; @sum(t2:y)>=2000; @sum(t2:y)<=b(1); y(1)+y(2)+y(3)+y(4)+y(5)<=b(2); y(1)+y(6)+y(7)+y(8)+y(9)<=b(3); y(2)+y(6)+y(10)+y(11)+y(12)<=b(4); y(3)+y(7)+y(10)+y(13)+y(14)<=b(5); y(4)+y(8)+y(11)+y(13)+y(15)<=b(6); y(5)+y(9)+y(12)+y(14)+y(15)<=b(7); @for(t2:@gin(y)); @for(t2:@gin(x)); @for(t2:26*x>=y); data: b=2500,900,600,400,550,1100,650; a=36,36,40,48,40,50,56; w=112,120,112,122,128,124,116,126,132,124,134,140,126,132,142; @text()=@table(y); enddata

到此已經求出了最小車輛數是 77 輛，接下來利用車輛的約束再求最大收益就好了

最大收益：253760

sets: t1/1..7/:a,b; t2/1..15/:w,y,x; endsets max=@sum(t2:y*w); @sum(t2:y)<=2100; @sum(t2:y)>=2000; @sum(t2:y)<=b(1); y(1)+y(2)+y(3)+y(4)+y(5)<=b(2); y(1)+y(6)+y(7)+y(8)+y(9)<=b(3); y(2)+y(6)+y(10)+y(11)+y(12)<=b(4); y(3)+y(7)+y(10)+y(13)+y(14)<=b(5); y(4)+y(8)+y(11)+y(13)+y(15)<=b(6); y(5)+y(9)+y(12)+y(14)+y(15)<=b(7); @for(t2:@gin(y)); @for(t2:@gin(x)); @for(t2:26*x>=y); @sum(t2:x)=77; data: b=2500,900,600,400,550,1100,650; a=36,36,40,48,40,50,56; w=112,120,112,122,128,124,116,126,132,124,134,140,126,132,142; @text()=@table(y); enddata

第三問

第三問其實就是第二問的一個小變形，區別就在于套餐的選擇換了一些約束，針對這些約束不難編程求出可行方案以及收益單價，這里用C++實現的

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int b[]={0,2500,900,600,400,550,1100,650};int a[]={0,36,36,40,48,40,50,56};bool check(int i,int j,int k) {vector<int>node;node.push_back(i);node.push_back(j);node.push_back(k);int cnt=0;for(int t=0;t<3;t++)//2,3,6有且只有一個 {if(node[t]==2||node[t]==3||node[t]==6)cnt++;}if(cnt!=1)return false;cnt=0;for(int t=0;t<3;t++)//6,7至多有一個 {if(node[t]==6||node[t]==7)cnt++;}if(cnt==2)return false;cnt=0;for(int t=0;t<3;t++)//1,4至多有一個 {if(node[t]==1||node[t]==4)cnt++;}if(cnt==2)return false; return true; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false); int n=7;int mmax=0;vector<string>ans;int cnt=1;for(int i=1;i<=7;i++)for(int j=i+1;j<=7;j++)for(int k=j+1;k<=7;k++){if(!check(i,j,k))continue;cout<<cnt<<' '<<i<<' '<<j<<' '<<k<<' '<<a[i]+a[j]+a[k]<<endl;cnt++;}return 0; }

到這里可以求出共有 12 種套餐，且具體的選擇方案以及單價都可以求出來，接下來套入第二問的模型中去，就可以直接求出最小車輛，從而求出最大利潤了

最小車輛：47

sets: t1/1..7/:a,b; t2/1..12/:w,y,x; endsets min=@sum(t2:x); @sum(t2:y)<=2100; @sum(t2:y)>=1200; y(1)+y(2)+y(3)+y(4)+y(5)<=b(1); y(1)+y(2)+y(6)+y(7)+y(8)<=b(2); y(3)+y(4)+y(9)+y(10)+y(11)<=b(3); y(6)+y(7)+y(9)+y(10)+y(12)<=b(4); y(1)+y(3)+y(5)+y(6)+y(8)+y(9)+y(11)+y(12)<=b(5); y(5)+y(12)<=b(6); y(2)+y(4)+y(7)+y(8)+y(10)+y(11)<=b(7); @for(t2:@gin(y)); @for(t2:@gin(x)); @for(t2:26*x>=y); data: b=2500,900,600,400,550,1100,650; a=36,36,40,48,40,50,56; w=112,128,116,132,126,124,140,132,128,144,136,138; @text()=@table(y); enddata

最大收益：159692

sets: t1/1..7/:a,b; t2/1..12/:w,y,x; endsets max=@sum(t2:y*w); @sum(t2:y)<=2100; @sum(t2:y)>=1200; y(1)+y(2)+y(3)+y(4)+y(5)<=b(1); y(1)+y(2)+y(6)+y(7)+y(8)<=b(2); y(3)+y(4)+y(9)+y(10)+y(11)<=b(3); y(6)+y(7)+y(9)+y(10)+y(12)<=b(4); y(1)+y(3)+y(5)+y(6)+y(8)+y(9)+y(11)+y(12)<=b(5); y(5)+y(12)<=b(6); y(2)+y(4)+y(7)+y(8)+y(10)+y(11)<=b(7); @for(t2:@gin(y)); @for(t2:@gin(x)); @for(t2:26*x>=y); @sum(t2:x)=47; data: b=2500,900,600,400,550,1100,650; a=36,36,40,48,40,50,56; w=112,128,116,132,126,124,140,132,128,144,136,138; @text()=@table(y); enddata

?

總結

以上是生活随笔為你收集整理的2020.5.27 线性规划测试(Lingo实现)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。