Cody

Problem 45500. Maximize the production in a plant within equipment capacity

Solution 3613165

Submitted on 10 Nov 2020 by cokakola
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.
Solve This Problem View on Solution Map

Test Suite

Test Status Code Input and Output
1   Pass
filetext = fileread('max_production.m') assert(isempty(strfind(filetext, 'rand'))) assert(isempty(strfind(filetext, 'fileread'))) assert(isempty(strfind(filetext, 'assert'))) assert(isempty(strfind(filetext, 'echo')))

filetext = 'function y = max_production(P) y=0; N=max(max(P(:,[1 2]))); PN=size(P,1); A=zeros(PN+N-1,PN); % Wege+Nodes x Wege (jeder Weg hat limitierte Kapazität -> jeweils eine Bedingung // an jeder Node müssen gleichviele Eingangs und Ausgangskapazität (Gleichheit ergibt eine Zeilen) b=ones(PN+N-1,1); % Spaltenvektor, Wege+Nodes x 1 c=zeros(1,PN); % Zeilenvektor, 1 x Wege for k=1:PN % die Gleichungen für die Wegekapazität A(k,k)=1; b(k)=P(k,3); end % Input=Output-Node n=1; ind_in =find(P(:,2)==N); ind_out=find(P(:,1)==1); A(PN+n,ind_in)=1; A(PN+n,ind_out)=-1; b(PN+n)=0.01; % 0 kleine Störung gegen Entartung c(ind_in)=1; % Alles was am ende bei der letzten Node rauskommt c(ind_out)=1; % Noch alles was vorne reingeht dazutun for n=2:N-1 % die Gleichungen für die Nodes ind_in =find(P(:,2)==n); ind_out=find(P(:,1)==n); A(PN+n,ind_in)=1; A(PN+n,ind_out)=-1; b(PN+n)=0.01; % % 0 kleine Störung gegen Entartung end %[m,n]=size(A); %disp([' rang und dimension: ',num2str(rank(A)),',',num2str(m),',',num2str(n)]); copt=simplex1(A,b,c); % Eigentlich muss A noch linear unabhängig gemacht werden. y=round(copt/2); % weil die input und output-kapazität zusammengenommen wurde // Die Störung in b macht runden nötig (evtl floor) function cnull=simplex1(A,b,c) % input A (mxn) n<m % input b (m), mit b>=0, Spaltenvektor % input c (n) % Zeilenvektor % follows the script of Martin Grötschel % but simplified, only default handling [m,n]=size(A); % I.1 S. 137 D=[A,eye(m)]; c=[c,zeros(1,m)]; B=n+1:n+m; % Spaltenindizes einer Basis (triviale Basis) N=1:n; AB=D(:,B); AN=D(:,N); cB=c(:,B); % zeilenvektor, ohne transponiert cN=c(:,N); ABinv=inv(D(:,B)); % S 126 Aquer=ABinv*AN; bquer=ABinv*b; cquer=cN-cB*ABinv*AN; cnull=cB*bquer; xy=AB\b; % mldivide, \ Solve systems of linear equations Ax = B for x. x = A\B x=xy(1:n); y=xy(n+1:m); while any(cquer>0) % II.1 S.126 Optimalitätsprüfung % II.2 S.127 Pivotspalte [~,s]=max(cquer); % wähle eine Spalte, bei der cquer maximal ist % II.4 S.127 minimum_lambda positiv=(Aquer(:,s)>0); % nur die Elemente mit Aquer>0. Lambdamin=min(bquer(positiv)./Aquer(positiv,s)); % II.5 S.127 Pivotzeile ind=find(bquer./Aquer(:,s)==Lambdamin); r=ind(1); % optimale Verfahren sind später zu implementieren % II.6 S.127 Pivotoperation/Basistausch Btmp=B(r); Ntmp=N(s); B(r)=Ntmp; N(s)=Btmp; %E=eye(m); E(:,r)=-Aquer(:,s); E(r,r)=-1/Aquer(r,s); %ABprimeinv=E*ABinv; % II.7 S.127 Update (die Methoden sind didaktisch, und nicht numerisch optimal) % updata Aquer Aqqrs=1/Aquer(r,s); Aqq=Aquer-Aquer(:,s)*Aquer(r,:)*Aqqrs; Aqq(r,:)= Aqqrs*Aquer(r,:); % überschreibe Zeile Aqq(:,s)=-Aqqrs*Aquer(:,s); % überschreibe Spalte (achtung VZ) Aqq(r,s)=Aqqrs; % überschreibe PivotElement % updata bquer bqq=bquer-Aquer(:,s)*bquer(r)*Aqqrs; bqq(r)=bquer(r)*Aqqrs; % überschreibe PivotElement % updata cquer cqq=cquer-Aquer(r,:)*cquer(s)*Aqqrs; cqq(s)=-cquer(s)*Aqqrs; % überschreibe PivotElement % updata cnull cnullq=cnull+cquer(s)*bquer(r)*Aqqrs; % update die variablen Aquer=Aqq; bquer=bqq; cquer=cqq; cnull=cnullq; end %goto II.2 end end %This code written by profile_id 7164325 '
2   Pass
P = [1 2 10; 1 3 6; 2 3 15; 2 4 5; 3 4 10; 3 5 3; 4 5 8]; assert(isequal(max_production(P),11))
3   Pass
P = [4 8 57; 2 6 92; 2 7 97; 6 8 39; 3 8 25; ... 2 8 50; 6 8 18; 1 2 25; 1 3 94; 1 4 35; ... 1 5 67; 5 8 29; 7 8 87; ]; assert(isequal(max_production(P),114))
4   Pass
P = [1 2 1; 2 3 5]; assert(isequal(max_production(P),1))
5   Pass
P = [7 8 85; 4 5 7; 6 7 49; 3 10 70; 6 9 13; ... 5 8 77; 7 9 27; 8 9 57; 2 3 1; 9 10 59; ... 8 9 55; 8 10 19; 9 10 92; 2 9 11; 6 9 67; ... 1 2 88; 1 4 65; 1 6 71; ]; assert(isequal(max_production(P),90))
6   Pass
P = [3 7 83; 2 8 19; 5 6 58; 6 9 65; 5 6 12; ... 4 5 88; 4 9 75; 9 10 54; 3 7 81; 4 9 57; ... 5 10 72; 6 10 19; 6 10 13; 7 9 85; 9 10 95; ... 1 2 37; 1 3 88; 1 4 71; 8 10 8; ]; assert(isequal(max_production(P),164))
7   Pass
P = [12 15 73; 13 17 45; 11 14 14; 4 5 99; 2 11 1; ... 5 13 3; 2 15 57; 7 11 15; 12 16 44; 4 7 65; ... 16 17 20; 4 9 53; 12 13 40; 14 15 48; 9 17 77; ... 1 2 21; 1 3 14; 1 4 71; 1 6 61; 1 8 4; ... 1 10 4; 1 12 2; 3 17 41; 6 17 42; 8 17 91; ... 10 17 92; 15 17 33; ]; assert(isequal(max_production(P),155))
8   Pass
P = [17 38 41; 25 30 72; 11 26 54; 17 34 32; 36 37 21; ... 3 30 18; 16 24 10; 35 38 19; 10 22 24; 34 36 99; ... 22 34 82; 32 38 99; 24 32 54; 12 34 85; 24 38 84; ... 12 17 40; 5 9 9; 6 23 79; 26 38 77; 19 24 14; ... 29 32 98; 35 37 94; 22 25 20; 22 37 59; 24 36 28; ... 11 36 41; 22 33 65; 19 31 66; 6 8 49; 3 10 1; ... 14 15 53; 26 27 60; 19 22 7; 18 39 64; 14 20 8; ... 31 34 47; 7 31 68; 34 37 15; 19 30 66; 25 29 62; ... 16 37 46; 36 38 68; 37 39 31; 3 10 68; 36 38 34; ... 22 31 77; 23 34 53; 18 37 33; 38 39 100; 16 18 47; ... 27 36 1; 35 36 55; 19 32 52; 12 15 36; 13 25 56; ... 1 2 69; 1 3 16; 1 4 55; 1 5 37; 1 6 27; ... 1 7 80; 1 11 17; 1 12 5; 1 13 6; 1 14 34; ... 1 16 33; 1 19 69; 1 21 36; 1 28 85; 1 35 67; ... 2 39 42; 4 39 65; 8 39 75; 9 39 40; 15 39 32; ... 20 39 25; 21 39 58; 28 39 79; 30 39 47; 33 39 85]; assert(isequal(max_production(P),521))
9   Pass
P = [6 7 31; 4 6 5; 2 4 99; 3 5 29; 6 7 60; ... 5 6 31; 6 7 34; 6 7 100; 3 6 98; 3 7 89; ... 3 7 16; 5 7 79; 5 6 97; 5 7 21; 2 4 7; ... 2 4 47; 2 6 74; 5 7 64; 3 6 96; 6 7 25; ... 3 4 42; 3 7 57; 4 6 47; 5 7 99; 3 4 78; ... 3 7 7; 4 5 22; 2 4 13; 6 7 55; 6 7 43; ... 5 6 37; 4 6 12; 2 7 75; 4 5 14; 5 6 16; ... 6 7 61; 2 5 97; 3 6 78; 2 5 69; 3 4 17; ... 3 7 15; 4 5 87; 4 6 72; 4 6 73; 4 5 8; ... 6 7 49; 6 7 23; 3 5 99; 6 7 92; 5 7 15; ... 5 6 21; 6 7 54; 3 4 38; 6 7 19; 4 5 70; ... 4 5 30; 5 6 67; 5 7 71; 4 5 11; 4 6 34; ... 5 7 39; 3 4 6; 3 5 77; 5 6 24; 4 7 76; ... 3 7 59; 2 3 65; 6 7 21; 6 7 62; 2 6 64; ... 3 4 86; 4 5 34; 2 7 1; 6 7 66; 6 7 39; ... 5 7 65; 2 5 75; 3 7 7; 6 7 9; 5 7 51; ... 2 5 77; 2 4 25; 3 7 31; 3 7 77; 4 6 10; ... 6 7 47; 2 5 62; 3 6 3; 6 7 47; 3 7 17; ... 3 6 37; 6 7 86; 4 6 99; 3 6 19; 4 7 25; ... 1 2 68; ]; assert(isequal(max_production(P),68))
10   Pass
P = [7 8 54; 6 8 26; 5 12 88; 6 9 96; 3 6 92; ... 9 11 22; 9 11 47; 5 6 28; 5 11 4; 12 13 83; ... 1 2 2; 1 3 85; 1 4 97; 1 5 45; 1 7 21; ... 1 10 33; 2 13 88; 4 13 33; 8 13 75; 10 13 88; ... 11 13 46; ]; assert(isequal(max_production(P),206))
11   Pass
P = [7 21 22; 25 32 3; 26 40 47; 6 15 8; 9 10 89; ... 22 30 83; 38 39 24; 30 37 87; 4 10 47; 25 31 77; ... 24 25 38; 20 38 22; 26 36 27; 30 37 89; 15 23 70; ... 26 31 22; 39 40 56; 4 17 45; 13 38 30; 4 12 25; ... 10 35 40; 19 38 1; 2 12 40; 35 36 63; 5 15 15; ... 29 34 28; 34 39 91; 26 31 4; 37 40 2; 26 38 15; ... 38 40 94; 25 27 54; 21 29 40; 15 30 18; 24 40 42; ... 17 26 51; 25 27 43; 27 28 53; 38 39 28; 33 40 39; ... 4 12 35; 35 40 73; 36 40 52; 21 27 72; 25 38 23; ... 12 38 87; 8 9 72; 29 33 85; 1 2 27; 1 3 90; ... 1 4 82; 1 5 99; 1 6 59; 1 7 92; 1 8 1; ... 1 11 13; 1 13 97; 1 14 52; 1 16 6; 1 18 83; ... 1 19 74; 1 20 48; 1 22 54; 1 24 2; 3 40 5; ... 11 40 51; 14 40 64; 16 40 88; 18 40 63; 23 40 67; ... 28 40 78; 31 40 19; 32 40 40; ]; assert(isequal(max_production(P),351))
12   Pass
P = [11 12 99; 6 10 54; 13 14 84; 13 14 60; 2 13 56; ... 7 8 6; 5 9 8; 2 5 99; 4 8 93; 12 13 30; ... 9 10 12; 11 13 8; 6 12 44; 10 12 11; 3 11 59; ... 3 10 79; 2 9 80; 5 6 48; 8 11 23; 4 5 55; ... 12 14 2; 7 9 99; 9 14 75; 7 13 50; 6 7 42; ... 7 13 25; 3 5 14; 11 13 46; 5 12 71; 9 13 10; ... 2 13 26; 5 11 51; 3 8 47; 6 13 54; 13 14 67; ... 8 10 84; 7 8 61; 6 8 8; 11 14 97; 10 13 44; ... 5 6 24; 11 13 25; 6 12 46; 2 7 53; 6 10 50; ... 6 13 57; 13 14 53; 12 13 46; 12 13 12; 5 14 87; ... 10 14 84; 3 14 48; 2 6 98; 8 11 23; 13 14 67; ... 13 14 9; 11 12 92; 7 9 97; 4 9 13; 8 14 36; ... 2 7 20; 9 12 23; 3 12 43; 4 8 17; 3 10 51; ... 3 10 58; 3 6 35; 6 7 75; 5 14 81; 10 11 62; ... 3 13 39; 6 14 3; 13 14 26; 9 14 64; 5 13 57; ... 13 14 22; 5 13 21; 8 9 98; 2 14 80; 1 2 39; ... 1 3 95; 1 4 36; ]; assert(isequal(max_production(P),170))
13   Pass
P = [8 22 11; 22 25 95; 13 25 20; 31 38 80; 9 17 12; ... 12 21 11; 22 28 50; 38 40 9; 7 23 94; 10 36 52; ... 24 25 12; 32 38 30; 28 37 66; 22 23 93; 17 24 37; ... 30 37 57; 22 34 70; 6 40 44; 27 28 81; 3 39 92; ... 38 41 98; 34 36 66; 18 19 72; 31 32 51; 28 41 7; ... 6 8 93; 9 31 84; 8 33 72; 14 18 24; 19 21 93; ... 4 7 84; 10 36 68; 11 17 100; 35 41 21; 19 33 56; ... 25 29 49; 20 28 98; 19 26 2; 39 40 13; 30 31 75; ... 32 33 28; 26 29 41; 34 35 66; 16 32 14; 8 12 66; ... 15 22 36; 27 34 61; 14 38 77; 35 40 62; 33 41 36; ... 12 20 92; 23 35 36; 17 25 25; 5 40 13; 36 37 16; ... 29 35 76; 27 39 37; 2 26 1; 28 41 83; 37 38 60; ... 40 41 57; 16 39 83; 26 38 89; 23 38 53; 40 41 12; ... 23 26 60; 25 35 86; 15 27 6; 25 33 5; 12 41 85; ... 26 39 3; 12 22 2; 24 26 25; 22 31 52; 30 31 20; ... 21 30 68; 29 37 5; 40 41 45; 12 18 52; 9 38 98; ... 4 14 8; 37 38 100; 14 35 26; 35 40 94; 32 35 59; ... 29 32 75; 36 40 67; 29 35 52; 28 29 22; 4 26 72; ... 25 27 44; 10 39 80; 15 35 21; 28 37 23; 5 10 54; ... 17 29 43; 39 40 71; 23 33 100; 39 41 90; 1 2 29; ... 1 3 27; 1 4 46; 1 5 19; 1 6 46; 1 9 12; ... 1 11 83; 1 13 99; 1 15 71; 1 16 84; ]; assert(isequal(max_production(P),401))
14   Pass
P = [5 8 43; 7 18 63; 15 18 77; 8 14 16; 2 11 29; ... 16 18 42; 4 11 11; 10 12 35; 7 17 18; 4 13 23; ... 13 18 12; 7 16 79; 8 16 32; 10 18 74; 5 8 80; ... 3 14 14; 13 15 75; 17 18 32; 9 14 93; 11 12 49; ... 6 11 50; 14 16 55; 13 16 18; 17 18 75; 13 17 60; ... 11 12 32; 4 12 62; 16 17 95; 13 17 57; 11 16 11; ... 7 9 43; 4 17 37; 9 13 73; 9 12 30; 13 17 45; ... 4 5 24; 8 16 22; 15 16 75; 8 16 71; 6 9 20; ... 15 18 3; 15 18 91; 4 8 97; 8 15 45; 11 15 100; ... 6 17 29; 9 12 45; 4 18 73; 13 16 40; 15 18 88; ... 1 2 55; 1 3 63; 1 4 50; 1 6 53; 1 7 31; ... 1 10 85; 12 18 29; ]; assert(isequal(max_production(P),262))
15   Pass
P = [9 11 51; 7 10 43; 2 10 62; 8 9 98; 5 10 94; ... 4 8 76; 10 11 33; 4 5 69; 10 11 1; 3 7 87; ... 7 9 42; 3 4 2; 9 10 70; 8 11 96; 7 9 89; ... 5 6 96; 7 9 20; 9 10 75; 6 11 2; 9 10 78; ... 1 2 63; 1 3 10; ]; assert(isequal(max_production(P),44))

Suggested Problems

More from this Author19

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!