Исследование операций. Lab3. Транспортные задачи

Транспортные задачи:

Номер по списку равен 15. Следовательно нужно решить следующие задачи:

Задание:

5.19.Решите следующую задачу как задачу транспортного типа и симплекс методом:

1	0	2	4
3	5	4	6
1	2	3	10
3	5	12

Для решения этой задачи транспортным методом была составлена программа на MATLAB.

Текст программы:

Файл «FindFirstDecision.m»:

function [X,NewProposal,NewDemand]=FindFirstDecision(Cost,Proposal,Demand);
%Funkciya FindFirstDecision nahodit nachalnoe bazisnoe resheniye transportnoy
%zadachi metodom naimenshey stoimosti.
%
%Obyavleniye:
%function [X,NewProposal,NewDemand]=FindFirstDecision(Cost,Proposal,Demand);
%
%Vhodniye parametri:
%Cost - matrica cen perevozok
%Proposal - stolbec predlosheniy
%Demand - Stroka sprosa
%Format vhodnih parametrov sovpadaet s formatom funkcii Transport.
%
%Vozvrashaemie znacheniya:
%V massive X vozvrashaetsa znacheniya matrici X transportnoy zadachi
%posle nahojdeniya nachalnogo resheniya. Elementi X, kotorie ne voshli v
%nachalnoe bazisnoe resheniye ravni -1. 
%Primer:
%X=
%    -1    15    -1     0
%    -1    -1    15    10
%     5    -1    -1     5
%Eto oznachaet:
%X(1,2)=15,X(1,4)=0,X(2,3)=15,X(2,4)=10,X(3,1)=5,X(3,4)=5
%V massive NewProposal vozvrashaetsa znacheniye novih predlosheniy.
%V massive NewDemand vozvrashaetsa znacheniye novogo sprosa.
%
%Smotrite takshe:
%   TransportProblem
%   Transport

[SizeY,SizeX]=size(Cost);
% Obyavleniye matrici X
% X=zeros(SizeY,SizeX);
for n=1:SizeY
    for m=1:SizeX
        X(n,m)=-1;
    end;
end;

%Massiv dla zapominaniya vicherknutih
%stolbcov
DelX=zeros(1,SizeX);
%Kolichestvo udalennihstolbcov budet hranitsya v
CountDelX=0;

% Massiv dla zapominaniya vicherknutih strok
DelY=zeros(SizeY,1);
%Kolichestvo udalennih strok budet hranitsya v
CountDelY=0;


%Poisk minimalnogo znacheniya dla metoda naimenshey stoimosti
while (1)
    %Proverka usloviya vihoda:
    % Esli ostalas lish odna nevicherknutaya stroka ili
    %stolbec, to algoritm zavershaet svoyu rabotu
    if ((CountDelX==SizeX-1)&&(CountDelY==SizeY)) 
        break;
    else
        if ((CountDelY==SizeY-1)&&(CountDelX==SizeX)) break;end;
    end;
    
    %Poisk minimalnogo elementa v poka eshe ne vicherknutom stolbce
    %ili stroke. v peremennoy MinX hranitsya koordinata po X
    %minimalnogo elementa (Nomer stolbca), a v peremennoy MinY
    %hranitsya koordinata po Yminimalnogo elementa, to est
    %nomer stroki.
    MinX=1;
    MinY=1;
    Started=1;
    for n=1:SizeX
        for m=1:SizeY
            if (DelX(n)~=1)   &&  (DelY(m)~=1)
              
                if ((Cost(m,n)<Cost(MinY,MinX)) || (Started==1)  )
                    MinY=m;
                    MinX=n;
                    Started=0;
                end;
            end;
        end;
    end;
    %Minimalnoe znacheniye=
    Min=Cost(MinY,MinX);
    
    %Vicherkivaniye sootvetstvuyushego stolbca
    %ili stroki
    if (Demand(MinX)<=Proposal(MinY))
        %znacheiye sprosa dlya v dannom stolbce
        %bolshe znacheniya predlosheniya dlya
        %dannoy stroki. Sledovatelno nushno 
        %udalit stolbec, v kotorom stoit 
        %danniy minimalniy element.
        %Dlya ego udaleniya prosto zanesem v
        %DelX(MinX) znacheniye, ravnoye 1.
        DelX(MinX)=1;
        CountDelX=CountDelX+1;
        
        %naibolsheya znacheniye, kotoroe moshet prinat
        %peremennaya X(MinY,MinX)= znacheniyu sprosa,
        %v dannom stolbce, to est znacheniyu Demond(MinX);
        X(MinY,MinX)=Demand(MinX);
    else
        %Znacheniye predlosheniya v dannoy stroke
        %menshe znacheniya sprosa dlya
        %dannogo stolbca. Sledovatelno nushno
        %udalit stroku, v kotoroy nahoditsya
        %danniy minimalniy element.
        %Dlya ego udaleniya prosto zanesem v
        %DelY(MinY) znacheniye, ravnoye 1.
        DelY(MinY)=1;
        CountDelY=CountDelY+1;
        
        % naibolsheye znacheniye, kotoroe moshet prinat
        %peremennaya X(MinX,MinY)= znacheniyu predlosheniya,
        %v dannoy stroke, to est znacheniyu Proposal(minY)
        X(MinY,MinX)=Proposal(MinY);
    end;
    
    %teper pereschitayem zhacheniye sprosa i predlosheniya dlya
    %dannogo stolbca i stroki
    Proposal(MinY)=Proposal(MinY)-X(MinY,MinX);
    Demand(MinX)=Demand(MinX)-X(MinY,MinX);
    
    %Vivod rezultatov raboti na ekranv okonchatelnoy versii
    %funkcii eti stroki dolshni bit otklucheni
    Cost;
    X;
    Proposal;
    Demand;
    DelX;
    DelY;
    CountDelX;
    CountDelY;
    
end;

%Vozvrashaem znacheniya:
NewProposal=Proposal;
NewDemand=Demand;

%
% Posetite https://urvanov.ru

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

function [X,NewProposal,NewDemand]=FindFirstDecision(Cost,Proposal,Demand);

%Funkciya FindFirstDecision nahodit nachalnoe bazisnoe resheniye transportnoy

%zadachi metodom naimenshey stoimosti.

%Obyavleniye:

%function [X,NewProposal,NewDemand]=FindFirstDecision(Cost,Proposal,Demand);

%Vhodniye parametri:

%Cost - matrica cen perevozok

%Proposal - stolbec predlosheniy

%Demand - Stroka sprosa

%Format vhodnih parametrov sovpadaet s formatom funkcii Transport.

%Vozvrashaemie znacheniya:

%V massive X vozvrashaetsa znacheniya matrici X transportnoy zadachi

%posle nahojdeniya nachalnogo resheniya. Elementi X, kotorie ne voshli v

%nachalnoe bazisnoe resheniye ravni -1.

%Primer:

%X=

% -1 15 -1 0

% -1 -1 15 10

% 5 -1 -1 5

%Eto oznachaet:

%X(1,2)=15,X(1,4)=0,X(2,3)=15,X(2,4)=10,X(3,1)=5,X(3,4)=5

%V massive NewProposal vozvrashaetsa znacheniye novih predlosheniy.

%V massive NewDemand vozvrashaetsa znacheniye novogo sprosa.

%Smotrite takshe:

% TransportProblem

% Transport

[SizeY,SizeX]=size(Cost);

% Obyavleniye matrici X

% X=zeros(SizeY,SizeX);

for n=1:SizeY

for m=1:SizeX

X(n,m)=-1;

end;

%Massiv dla zapominaniya vicherknutih

%stolbcov

DelX=zeros(1,SizeX);

%Kolichestvo udalennihstolbcov budet hranitsya v

CountDelX=0;

% Massiv dla zapominaniya vicherknutih strok

DelY=zeros(SizeY,1);

%Kolichestvo udalennih strok budet hranitsya v

CountDelY=0;

%Poisk minimalnogo znacheniya dla metoda naimenshey stoimosti

while (1)

%Proverka usloviya vihoda:

% Esli ostalas lish odna nevicherknutaya stroka ili

%stolbec, to algoritm zavershaet svoyu rabotu

if ((CountDelX==SizeX-1)&&(CountDelY==SizeY))

break;

else

if ((CountDelY==SizeY-1)&&(CountDelX==SizeX)) break;end;

end;

%Poisk minimalnogo elementa v poka eshe ne vicherknutom stolbce

%ili stroke. v peremennoy MinX hranitsya koordinata po X

%minimalnogo elementa (Nomer stolbca), a v peremennoy MinY

%hranitsya koordinata po Yminimalnogo elementa, to est

%nomer stroki.

MinX=1;

MinY=1;

Started=1;

for n=1:SizeX

for m=1:SizeY

if (DelX(n)~=1) && (DelY(m)~=1)

if ((Cost(m,n)<Cost(MinY,MinX)) || (Started==1) )

MinY=m;

MinX=n;

Started=0;

end;

%Minimalnoe znacheniye=

Min=Cost(MinY,MinX);

%Vicherkivaniye sootvetstvuyushego stolbca

%ili stroki

if (Demand(MinX)<=Proposal(MinY))

%znacheiye sprosa dlya v dannom stolbce

%bolshe znacheniya predlosheniya dlya

%dannoy stroki. Sledovatelno nushno

%udalit stolbec, v kotorom stoit

%danniy minimalniy element.

%Dlya ego udaleniya prosto zanesem v

%DelX(MinX) znacheniye, ravnoye 1.

DelX(MinX)=1;

CountDelX=CountDelX+1;

%naibolsheya znacheniye, kotoroe moshet prinat

%peremennaya X(MinY,MinX)= znacheniyu sprosa,

%v dannom stolbce, to est znacheniyu Demond(MinX);

X(MinY,MinX)=Demand(MinX);

else

%Znacheniye predlosheniya v dannoy stroke

%menshe znacheniya sprosa dlya

%dannogo stolbca. Sledovatelno nushno

%udalit stroku, v kotoroy nahoditsya

%danniy minimalniy element.

%Dlya ego udaleniya prosto zanesem v

%DelY(MinY) znacheniye, ravnoye 1.

DelY(MinY)=1;

CountDelY=CountDelY+1;

% naibolsheye znacheniye, kotoroe moshet prinat

%peremennaya X(MinX,MinY)= znacheniyu predlosheniya,

%v dannoy stroke, to est znacheniyu Proposal(minY)

X(MinY,MinX)=Proposal(MinY);

end;

%teper pereschitayem zhacheniye sprosa i predlosheniya dlya

%dannogo stolbca i stroki

Proposal(MinY)=Proposal(MinY)-X(MinY,MinX);

Demand(MinX)=Demand(MinX)-X(MinY,MinX);

%Vivod rezultatov raboti na ekranv okonchatelnoy versii

%funkcii eti stroki dolshni bit otklucheni

Cost;

Proposal;

Demand;

DelX;

DelY;

CountDelX;

CountDelY;

end;

%Vozvrashaem znacheniya:

NewProposal=Proposal;

NewDemand=Demand;

% Posetite https://urvanov.ru

Файл «TransportProblem.m»:

function [X]=TransportProblem(Cost,X,Proposal,Demand);
%Eta funkciya reshaet transportnuyu zadachu.
%
%Obyavleniye:
%function TransportProblem(Cost,X,Proposal,Demand);
%
%Vhodnie parametri:
%Cost - tablica stoimostey perevozok
%X - tablica X (smotrite help FindFirstDecision
%dlya bolshey informacii). X sodershit nachalnoe bazisnoe 
%resheniye.
%Proposal - tablica cen (znacheniye NewProposal, 
%vozvrashaemoe funkciyey FindFirstDecision)
%Demand - tablica sprosa (vozvrashaetsya funkciyey
%FindFirstDecision (NewDemand))
%
%Smotrite takje:
% FindFirstDecision
% Transport

%Opredeleniye razmerov tablici cen
[SizeY,SizeX]=size(Cost);

Noviy_Maximum=1;
while  Noviy_Maximum>0
%Obyavleniye massivov patencialov

u=zeros(SizeY,1);  %massiv potencialov strok
v=zeros(1,SizeX) ; %massiv potencialov stolbcov
for n=1:SizeY
    u(n)=NaN;
end;
for n=1:SizeX
    v(n)=NaN;
end;

    
u(1)=0;


yes=0;%peremennaya dlya proverki, vse li potenciali vichislenni

%Etot zikl prohodit vsyu tablicy Cost do teh por, poka
%ne budut vichislenni vse potenciali
while (yes==0)
yes=1;
    %sleduyushiye zikli vichislyayut potenciali
    for m=1:SizeY
        for n=1:SizeX
            if (X(m,n)>=0)
               
                if ((u(m)~=NaN)&&(not (v(n)>=0)) &&(not (v(n)<=0))   )
                    v(n)=Cost(m,n)-u(m);
                   
                else
                    if ((v(n)~=NaN))
                        u(m)=Cost(m,n)-v(n)  ;
                    
                    else
                        yes=0;
                    end
                end
            end;

%         pause;
        end;

    end;
end;


%Teper posle togo, kak potenciali bili vichislenni
%nahodim nailbolshee poposhitelnoe chislo sredi
%u(i)+v(j)-Cost(i,j) dla kashdoy iz nebazisnih pere-
%mennih. X(i,j), gde u(i)+v(j)-Cost(i,j) minimalno 
%i budet vvodimoy peremennoy
MaxX=0;MinY=0;Noviy_Maximum=0;
for m=1:SizeY
    for n=1:SizeX
        if not (X(m,n)>=0)    

           
               if   ( (u(m)+v(n)-Cost(m,n)>=Noviy_Maximum)&&(u(m)+v(n)-Cost(m,n)>0)) 
                   MaxX=n;
                   MinY=m;
              
                   Noviy_Maximum=u(m)+v(n)-Cost(MinY,MaxX);
               end;
           
        end;
    end
end
%Teper vvodimaya peremennaya naydena.
%Eto X(MinY,MaxX)

if Noviy_Maximum<=0 continue; end;

%Naidem iskluchaemuyu peremennuyu
%Dlya etogo sostavim zamknutiy cikl, v kotoriy
%budut vhodit tolko bazisniye peremenniye i vvo-
%dimaya peremennaya.

%Sozdadim massiv,gde budut perechislenni bazisniye
%peremenniye i vvodimaya peremennaya

%Cikl nachinaetsa s vvodimoy peremennoy
Cikl(1,1)=MinY;
Cikl(2,1)=MaxX;

k=2;%index sleduyushey bazisnoy peremennoy
for m=1:SizeY
    for n=1:SizeX
        if (X(m,n)>=0)
            Cikl(1,k)=m;
            Cikl(2,k)=n;
            k=k+1;
        end;
    end;
end;
%Zamknutiy cikl zakanchivaetsa na vvodimoy peremennoy
Cikl(1,k)=MinY;
Cikl(2,k)=MaxX;



%Teper neobhodimo perebrat vse perestanovki massiva Cikl
%Dlya etogo obyavim massiv indeksov:
%1,2,3,4,5...
%Eti indexi ukazivayut na elementi massiva Cikl.
%To est indexam:
%1,2,3,4,5... 
%Sootvetstvuyut:
%Cikl(:,1),Cikl(:,2),Cikl(:,3),Cikl(:,4),Cikl(:,5)...
%A indexam:
%i1,i2,i3,i4... Sootvetstvuyut
%Cikl(:,i1),Cikl(:,i2),Cikl(:,i3),Cikl(:,i4).

%nachalnaya inicializaciya massiva indeksov:
%1,2,3,4,5,6,7,8,9,10,11,12...
m=1;
for n=1:k
    Index(n)=m;
    m=m+1;
end;


%Index(k-2)=k; %dlya otladki NE VKLUCHAYTE ETU STROKU

%Teper dlya prohoshdeniya vseh vozmoshnih ciklov
%nushno izmenyat massiv indeksov sleduyushim obrazom:
%
%naprimer k=6 (razmer massiva Index=6)
%1,2,3,4,5,6
%1,2,3,5,2,6 
%1,2,3,5,3,6
%1,2,3,5,4,6
%1,2,3,5,5,6
%1,2,4,2,2,6
%1,2,4,2,3,6
%1,2,4,2,4,6
%1,2,4,2,5,6
%1,2,4,3,2,6
%...
%Sleduet zametit, chto krayniy leviy i krayniy praviy indexi
%ne uchavstvuyut, poskolku mi ishem cikl, nachinayushiysya
%i zakanchivayushiysya na vvodimoy peremennoy.

%n budet ukazivat na tekushiy obrabativaemiy (izmenyaemiy)
%element.
n=k-1; 
yes=0; %Peremennaya yes yavlyaetsya flashkom. 
            % yes=1   -  zamknutiy cikl nayden
            % yes=0   - zamknutiy cikl ne nayden
while n~=1
    %Proverka, ne poluchilsya li zamknutiy cikl.
    %Esli poluchiksya zamknutiy cikl, to vihodim iz cikla s infor-
    %maciyey o tom, chto zamknutiy cikl nayden.
    
    yes=1; %Pervonachalno predpolagaem, chto Index hranit 
                %zamknutiy cikl
%     for i=1:k
%         for j=1:k; 
%             if ((Index(i)==Index(j)) && (i~=j))  yes=0; end;
%         end;
%     end;
    for m=2:k
        yes2=0;
        if (Cikl(1,Index(m))==Cikl(1,Index(m-1)))
            yes2=1;
        end;
        if (Cikl(2,Index(m))==Cikl(2,Index(m-1)))
            yes2=1;
        end;
        if (yes2==0) %Esli ne vipolnilos ni odno iz us-
            yes=0;      %loviy,to znachit eto ne zamknutiy
        end;              %cikl          
                                        
    end;
    if (yes==1) 
        n=1;
        continue;
    end;
        
    if Index(n)<k-1
        %Uvelichivaem znacheniye Index(n), esli ono eshe ne
        %dostiglo maksimalnogo
        Index(n)=Index(n)+1; 
        n=n+1;
        %Znacheniye n ne dolshno previsit k ili bit ravnim k
        if (n>=k) n=n-1; end;
    else
        %Esli znachenie Index(n) dostiglo maksimalnogo zna-
        %cheniya to znachit neobhodimo uvelichit element, sto-
        %yashiy levee
        Index(n)=1;
        n=n-1;
    end;
end;


%Teper proizvedem proverku. Esli zamknutiy cikl ne nayden,
%to proizoshla fatalnaya oshibka.
if (yes==0)
    disp('Fatal error:')
    disp('Not closed cycle is found.');
    disp('Press any key to continue...');
    disp('Fatalnaya oshibka:');
    disp('Ne naiden zamknutiy cikl.');
    disp('Nashmite lubuyu klavishu dlya prodolsheniya... ');
    pause
end;

%Priravnyaem vvodimuyu peremennuyu phi.
%Dalee prohodim po zamknutomu ciklu i poocheredno priba-
%vlyaem i otnimaem  phi k znacheniyam bazisnih peremennih,
%nahodyashihsya v uglovih yacheykah cikla.

%i,j - indeksi matric Sub i Add, Cur tekushaya operaciya:
%0 - plibavleniye
%1 - vichitaniye
%HV - dlya opredeleniya uglovih peremennih
i=1;j=1;Cur=1;HV=0;
n=1; Sub=0; Add=0;Min=-1;
while n<=k-1

    if (Cikl(1,Index(n))==Cikl(1,Index(n+1)) && (HV~=2))
        HV=1;
        n=n+1;
        continue;   
    end;
    if (Cikl(2,Index(n))==Cikl(2,Index(n+1)) && (HV~=1))
        HV=2;
        n=n+1;
        continue
    end;
    if (Cur==1)
%         Sub(i)=X(Cikl(1,Index(n)),Cikl(2,Index(n)))
        if  (Min>X(Cikl(1,Index(n)),Cikl(2,Index(n))))
            Min=X(Cikl(1,Index(n)),Cikl(2,Index(n))); 
        end;
        if (Min==-1)
            Min=X(Cikl(1,Index(n)),Cikl(2,Index(n)));
        end;
        
        i=i+1;
        HV=0;
        Cur=0;
    else
%         Add(j)=X(Cikl(1,Index(n)),Cikl(2,Index(n)))
        j=j+1;
        HV=0;
        Cur=1;
    end;
    
end;
% Sub
% Add



%Izmenim znacheniya peremennih,chtobi vipolnyalis ogranicheniya
i=1;j=1;Cur=1;HV=0;
n=1; Sub=0; Add=0;
yes=0;%esli yes=1 to iskluchaemaya peremennaya ushe udalenna


while n<=k-1
    if (Cikl(1,Index(n))==Cikl(1,Index(n+1)) && (HV~=2))
        HV=1;
        n=n+1;
        continue;   
    end;
    if (Cikl(2,Index(n))==Cikl(2,Index(n+1)) && (HV~=1))
        HV=2;
        n=n+1;
        continue
    end;
    if (Cur==1)
%         Sub(i)=X(Cikl(1,Index(n)),Cikl(2,Index(n))
        X(Cikl(1,Index(n)),Cikl(2,Index(n)))=X(Cikl(1,Index(n)),Cikl(2,Index(n)))-Min;
        if ((yes==0) &&(X(Cikl(1,Index(n)),Cikl(2,Index(n)))==0))
            X(Cikl(1,Index(n)),Cikl(2,Index(n)))=-1;
            yes=1;
        end;    
        i=i+1;
        HV=0;
        Cur=0;
    else
%         Add(j)=X(Cikl(1,Index(n)),Cikl(2,Index(n)))
        X(Cikl(1,Index(n)),Cikl(2,Index(n)))=X(Cikl(1,Index(n)),Cikl(2,Index(n)))+Min;
        j=j+1;
        HV=0;
        Cur=1;
    end;
    
end;
%Teper dobavim peremennuyu, vkluchaemuyu v bazis:
X(MinY,MaxX)=Min;


end;

%
% Posetite https://urvanov.ru

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

function [X]=TransportProblem(Cost,X,Proposal,Demand);

%Eta funkciya reshaet transportnuyu zadachu.

%Obyavleniye:

%function TransportProblem(Cost,X,Proposal,Demand);

%Vhodnie parametri:

%Cost - tablica stoimostey perevozok

%X - tablica X (smotrite help FindFirstDecision

%dlya bolshey informacii). X sodershit nachalnoe bazisnoe

%resheniye.

%Proposal - tablica cen (znacheniye NewProposal,

%vozvrashaemoe funkciyey FindFirstDecision)

%Demand - tablica sprosa (vozvrashaetsya funkciyey

%FindFirstDecision (NewDemand))

%Smotrite takje:

% FindFirstDecision

% Transport

%Opredeleniye razmerov tablici cen

[SizeY,SizeX]=size(Cost);

Noviy_Maximum=1;

while Noviy_Maximum>0

%Obyavleniye massivov patencialov

u=zeros(SizeY,1); %massiv potencialov strok

v=zeros(1,SizeX) ; %massiv potencialov stolbcov

for n=1:SizeY

u(n)=NaN;

end;

for n=1:SizeX

v(n)=NaN;

end;

u(1)=0;

yes=0;%peremennaya dlya proverki, vse li potenciali vichislenni

%Etot zikl prohodit vsyu tablicy Cost do teh por, poka

%ne budut vichislenni vse potenciali

while (yes==0)

yes=1;

%sleduyushiye zikli vichislyayut potenciali

for m=1:SizeY

for n=1:SizeX

if (X(m,n)>=0)

if ((u(m)~=NaN)&&(not (v(n)>=0)) &&(not (v(n)<=0)) )

v(n)=Cost(m,n)-u(m);

else

if ((v(n)~=NaN))

u(m)=Cost(m,n)-v(n) ;

else

yes=0;

end

end;

% pause;

end;

%Teper posle togo, kak potenciali bili vichislenni

%nahodim nailbolshee poposhitelnoe chislo sredi

%u(i)+v(j)-Cost(i,j) dla kashdoy iz nebazisnih pere-

%mennih. X(i,j), gde u(i)+v(j)-Cost(i,j) minimalno

%i budet vvodimoy peremennoy

MaxX=0;MinY=0;Noviy_Maximum=0;

for m=1:SizeY

for n=1:SizeX

if not (X(m,n)>=0)

if ( (u(m)+v(n)-Cost(m,n)>=Noviy_Maximum)&&(u(m)+v(n)-Cost(m,n)>0))

MaxX=n;

MinY=m;

Noviy_Maximum=u(m)+v(n)-Cost(MinY,MaxX);

end;

end

%Teper vvodimaya peremennaya naydena.

%Eto X(MinY,MaxX)

if Noviy_Maximum<=0 continue; end;

%Naidem iskluchaemuyu peremennuyu

%Dlya etogo sostavim zamknutiy cikl, v kotoriy

%budut vhodit tolko bazisniye peremenniye i vvo-

%dimaya peremennaya.

%Sozdadim massiv,gde budut perechislenni bazisniye

%peremenniye i vvodimaya peremennaya

%Cikl nachinaetsa s vvodimoy peremennoy

Cikl(1,1)=MinY;

Cikl(2,1)=MaxX;

k=2;%index sleduyushey bazisnoy peremennoy

for m=1:SizeY

for n=1:SizeX

if (X(m,n)>=0)

Cikl(1,k)=m;

Cikl(2,k)=n;

k=k+1;

end;

%Zamknutiy cikl zakanchivaetsa na vvodimoy peremennoy

Cikl(1,k)=MinY;

Cikl(2,k)=MaxX;

%Teper neobhodimo perebrat vse perestanovki massiva Cikl

%Dlya etogo obyavim massiv indeksov:

%1,2,3,4,5...

%Eti indexi ukazivayut na elementi massiva Cikl.

%To est indexam:

%1,2,3,4,5...

%Sootvetstvuyut:

%Cikl(:,1),Cikl(:,2),Cikl(:,3),Cikl(:,4),Cikl(:,5)...

%A indexam:

%i1,i2,i3,i4... Sootvetstvuyut

%Cikl(:,i1),Cikl(:,i2),Cikl(:,i3),Cikl(:,i4).

%nachalnaya inicializaciya massiva indeksov:

%1,2,3,4,5,6,7,8,9,10,11,12...

m=1;

for n=1:k

Index(n)=m;

m=m+1;

end;

%Index(k-2)=k; %dlya otladki NE VKLUCHAYTE ETU STROKU

%Teper dlya prohoshdeniya vseh vozmoshnih ciklov

%nushno izmenyat massiv indeksov sleduyushim obrazom:

%naprimer k=6 (razmer massiva Index=6)

%1,2,3,4,5,6

%1,2,3,5,2,6

%1,2,3,5,3,6

%1,2,3,5,4,6

%1,2,3,5,5,6

%1,2,4,2,2,6

%1,2,4,2,3,6

%1,2,4,2,4,6

%1,2,4,2,5,6

%1,2,4,3,2,6

%...

%Sleduet zametit, chto krayniy leviy i krayniy praviy indexi

%ne uchavstvuyut, poskolku mi ishem cikl, nachinayushiysya

%i zakanchivayushiysya na vvodimoy peremennoy.

%n budet ukazivat na tekushiy obrabativaemiy (izmenyaemiy)

%element.

n=k-1;

yes=0; %Peremennaya yes yavlyaetsya flashkom.

% yes=1 - zamknutiy cikl nayden

% yes=0 - zamknutiy cikl ne nayden

while n~=1

%Proverka, ne poluchilsya li zamknutiy cikl.

%Esli poluchiksya zamknutiy cikl, to vihodim iz cikla s infor-

%maciyey o tom, chto zamknutiy cikl nayden.

yes=1; %Pervonachalno predpolagaem, chto Index hranit

%zamknutiy cikl

% for i=1:k

% for j=1:k;

% if ((Index(i)==Index(j)) && (i~=j)) yes=0; end;

% end;

for m=2:k

yes2=0;

if (Cikl(1,Index(m))==Cikl(1,Index(m-1)))

yes2=1;

end;

if (Cikl(2,Index(m))==Cikl(2,Index(m-1)))

yes2=1;

end;

if (yes2==0) %Esli ne vipolnilos ni odno iz us-

yes=0; %loviy,to znachit eto ne zamknutiy

end; %cikl

end;

if (yes==1)

n=1;

continue;

end;

if Index(n)<k-1

%Uvelichivaem znacheniye Index(n), esli ono eshe ne

%dostiglo maksimalnogo

Index(n)=Index(n)+1;

n=n+1;

%Znacheniye n ne dolshno previsit k ili bit ravnim k

if (n>=k) n=n-1; end;

else

%Esli znachenie Index(n) dostiglo maksimalnogo zna-

%cheniya to znachit neobhodimo uvelichit element, sto-

%yashiy levee

Index(n)=1;

n=n-1;

end;

%Teper proizvedem proverku. Esli zamknutiy cikl ne nayden,

%to proizoshla fatalnaya oshibka.

if (yes==0)

disp('Fatal error:')

disp('Not closed cycle is found.');

disp('Press any key to continue...');

disp('Fatalnaya oshibka:');

disp('Ne naiden zamknutiy cikl.');

disp('Nashmite lubuyu klavishu dlya prodolsheniya... ');

pause

end;

%Priravnyaem vvodimuyu peremennuyu phi.

%Dalee prohodim po zamknutomu ciklu i poocheredno priba-

%vlyaem i otnimaem phi k znacheniyam bazisnih peremennih,

%nahodyashihsya v uglovih yacheykah cikla.

%i,j - indeksi matric Sub i Add, Cur tekushaya operaciya:

%0 - plibavleniye

%1 - vichitaniye

%HV - dlya opredeleniya uglovih peremennih

i=1;j=1;Cur=1;HV=0;

n=1; Sub=0; Add=0;Min=-1;

while n<=k-1

if (Cikl(1,Index(n))==Cikl(1,Index(n+1)) && (HV~=2))

HV=1;

n=n+1;

continue;

end;

if (Cikl(2,Index(n))==Cikl(2,Index(n+1)) && (HV~=1))

HV=2;

n=n+1;

continue

end;

if (Cur==1)

% Sub(i)=X(Cikl(1,Index(n)),Cikl(2,Index(n)))

if (Min>X(Cikl(1,Index(n)),Cikl(2,Index(n))))

Min=X(Cikl(1,Index(n)),Cikl(2,Index(n)));

end;

if (Min==-1)

Min=X(Cikl(1,Index(n)),Cikl(2,Index(n)));

end;

i=i+1;

HV=0;

Cur=0;

else

% Add(j)=X(Cikl(1,Index(n)),Cikl(2,Index(n)))

j=j+1;

HV=0;

Cur=1;

end;

% Sub

% Add

%Izmenim znacheniya peremennih,chtobi vipolnyalis ogranicheniya

i=1;j=1;Cur=1;HV=0;

n=1; Sub=0; Add=0;

yes=0;%esli yes=1 to iskluchaemaya peremennaya ushe udalenna

while n<=k-1

if (Cikl(1,Index(n))==Cikl(1,Index(n+1)) && (HV~=2))

HV=1;

n=n+1;

continue;

end;

if (Cikl(2,Index(n))==Cikl(2,Index(n+1)) && (HV~=1))

HV=2;

n=n+1;

continue

end;

if (Cur==1)

% Sub(i)=X(Cikl(1,Index(n)),Cikl(2,Index(n))

X(Cikl(1,Index(n)),Cikl(2,Index(n)))=X(Cikl(1,Index(n)),Cikl(2,Index(n)))-Min;

if ((yes==0) &&(X(Cikl(1,Index(n)),Cikl(2,Index(n)))==0))

X(Cikl(1,Index(n)),Cikl(2,Index(n)))=-1;

yes=1;

end;

i=i+1;

HV=0;

Cur=0;

else

% Add(j)=X(Cikl(1,Index(n)),Cikl(2,Index(n)))

X(Cikl(1,Index(n)),Cikl(2,Index(n)))=X(Cikl(1,Index(n)),Cikl(2,Index(n)))+Min;

j=j+1;

HV=0;

Cur=1;

end;

%Teper dobavim peremennuyu, vkluchaemuyu v bazis:

X(MinY,MaxX)=Min;

end;

% Posetite https://urvanov.ru

Файл «Transport.m»:

function X=Transport(Cost,Proposal,Demand)
%Reshaet transportnuyu zadachu. Glavnaya funkciya dlya resheniya 
%transportnoy zadachi.
%
%Obyavleniye:
%function X=Transport(Cost,Proposal,Demand)
%
%Vhodniye parametri:
%Cost - tablica cen transportnoy zadachi
%Proposal - tablica predlosheniy transportnoy zadachi (stolbec)
%Demand - tablica sprosa transportnoy zadachi (stroka)
%
%*****************************************************************
%Primer vhodnih dannih:
%Transportnaya zadacha:
%________________________________________
%|      10|        2|       20|       11|
%|x11     |x12      |x13      |x14      |     15
%|________|_________|_________|_________|
%|      12|        7|        9|       20|
%|x21     |x22      |x23      |x24      |     25
%|________|_________|_________|_________|
%|       4|       14|       16|       18|
%|x31     |x32      |x33      |x34      |     10
%|________|_________|_________|_________|
%  5       15        15        15
%
%Dlya resheniya takoy transportnoy zadachi neobhodimo peredat sle-
%duyushiye parametri:
% Cost=[
%     10  2   20  11
%     12  7   9   20
%     4   14  16  18];
% Proposal=[
%     15,
%     25,
%     10];
% Demand=[
%     5   15  15  15
% ];
%Primer vzat iz knigi:
%   Taha,Hemdi A.
%T24  Vvedeniye v issledovaniye operaciy, 7-e izdaniye.: Per. s 
%angl. - M.: Izdatelskiy dom "Vilyams", 2005. - 912 s.: il. - 
%Paral. tit. angl.
% sm str 207
%*****************************************************************
%
%text funkcii:
%
%[X,NewProposal,NewDemand]=FindFirstDecision(Cost,Proposal,Demand);;
%X=TransportProblem(Cost,X,Proposal,Demand);
%
%
% Posetite https://urvanov.ru


[X,NewProposal,NewDemand]=FindFirstDecision(Cost,Proposal,Demand);;
X=TransportProblem(Cost,X,Proposal,Demand);

100

101

102

103

104

105

106

107

108

109

110

111

112

113

function X=Transport(Cost,Proposal,Demand)

%Reshaet transportnuyu zadachu. Glavnaya funkciya dlya resheniya

%transportnoy zadachi.

%Obyavleniye:

%function X=Transport(Cost,Proposal,Demand)

%Vhodniye parametri:

%Cost - tablica cen transportnoy zadachi

%Proposal - tablica predlosheniy transportnoy zadachi (stolbec)

%Demand - tablica sprosa transportnoy zadachi (stroka)

%*****************************************************************

%Primer vhodnih dannih:

%Transportnaya zadacha:

%________________________________________

%| 10| 2| 20| 11|

%|x11 |x12 |x13 |x14 | 15

%|________|_________|_________|_________|

%| 12| 7| 9| 20|

%|x21 |x22 |x23 |x24 | 25

%|________|_________|_________|_________|

%| 4| 14| 16| 18|

%|x31 |x32 |x33 |x34 | 10

%|________|_________|_________|_________|

% 5 15 15 15

%Dlya resheniya takoy transportnoy zadachi neobhodimo peredat sle-

%duyushiye parametri:

% Cost=[

% 10 2 20 11

% 12 7 9 20

% 4 14 16 18];

% Proposal=[

% 15,

% 25,

% 10];

% Demand=[

% 5 15 15 15

% ];

%Primer vzat iz knigi:

% Taha,Hemdi A.

%T24 Vvedeniye v issledovaniye operaciy, 7-e izdaniye.: Per. s

%angl. - M.: Izdatelskiy dom "Vilyams", 2005. - 912 s.: il. -

%Paral. tit. angl.

% sm str 207

%*****************************************************************

%text funkcii:

%[X,NewProposal,NewDemand]=FindFirstDecision(Cost,Proposal,Demand);;

%X=TransportProblem(Cost,X,Proposal,Demand);

% Posetite https://urvanov.ru

[X,NewProposal,NewDemand]=FindFirstDecision(Cost,Proposal,Demand);;

X=TransportProblem(Cost,X,Proposal,Demand);

Файл «WriteDecisionOfTheTransportProblem.m»:

function WriteDecisionOfTheTransportProblem(X,ProposalNames,DemandNames)
[k1,k2]=size(X);
disp('Vivod rezultatov:');
str='Spisok perevozok iz punkta';
   i=1;
for m=1:k1
    str='Spisok11 perevozok iz punkta';  
     disp(sprintf('%s %s',str,ProposalNames(m,:)))
    for n=1:k2
        
        if (X(m,n)>0) 
            disp(sprintf('v punkt %s sleduet perevozit %d.',DemandNames(m,:),X(m,n)))
        end;
    end;
    disp(' ');
    
end

function WriteDecisionOfTheTransportProblem(X,ProposalNames,DemandNames)

[k1,k2]=size(X);

disp('Vivod rezultatov:');

str='Spisok perevozok iz punkta';

i=1;

for m=1:k1

str='Spisok11 perevozok iz punkta';

disp(sprintf('%s %s',str,ProposalNames(m,:)))

for n=1:k2

if (X(m,n)>0)

disp(sprintf('v punkt %s sleduet perevozit %d.',DemandNames(m,:),X(m,n)))

end;

disp(' ');

end

Файл «Data.m»:

%Fail s dannimi dzl lab3

 Cost=[
      1   0   2
      3   5   4
      1  2   3
]
 Demand=[3    5   12]
 Proposal=[
     4
     6
     10
]
ProposalNames=[
    'P1'
    'P2'
    'P3'
]
DemandNames=['D1' 
    'D2' 
    'D3']



% Eti dannie prosto dlya proverki. sm TAHA
% Cost=[
%     10  2   20  11
%     12  7   9   20
%     4   14  16  18];
% Proposal=[
%     15,
%     25,
%     10];
% Demand=[
%     5   15  15  15
% ];

%Fail s dannimi dzl lab3

Cost=[

1 0 2

3 5 4

1 2 3

]

Demand=[3 5 12]

Proposal=[

]

ProposalNames=[

'P1'

'P2'

'P3'

]

DemandNames=['D1'

'D2'

'D3']

% Eti dannie prosto dlya proverki. sm TAHA

% Cost=[

% 10 2 20 11

% 12 7 9 20

% 4 14 16 18];

% Proposal=[

% 15,

% 25,

% 10];

% Demand=[

% 5 15 15 15

% ];

В результате чего было получено решение:

X =

    -1     4    -1
    -1    -1     6
     3     1     6

Vivod rezultatov:
Spisok11 perevozok iz punkta P1
v punkt D1 sleduet perevozit 4.
 
Spisok11 perevozok iz punkta P2
v punkt D2 sleduet perevozit 6.
 
Spisok11 perevozok iz punkta P3
v punkt D3 sleduet perevozit 3.
v punkt D3 sleduet perevozit 1.
v punkt D3 sleduet perevozit 6.

X =

-1 4 -1

-1 -1 6

3 1 6

Vivod rezultatov:

Spisok11 perevozok iz punkta P1

v punkt D1 sleduet perevozit 4.

Spisok11 perevozok iz punkta P2

v punkt D2 sleduet perevozit 6.

Spisok11 perevozok iz punkta P3

v punkt D3 sleduet perevozit 3.

v punkt D3 sleduet perevozit 1.

v punkt D3 sleduet perevozit 6.

Для решения этой задачи симплекс методом была составлена следующая система уравнений:

↓ Z=1*x1 +  0*x2 +  2*x3 +  3*x4 + 5*x5 +  4*x6 +  1*x7 +  2*x8 +  3*x9]

	1*x1+	1*x2+	1*x3+	0*x4+	0*x5+	0*x6+	0*x7+	0*x8+	0*x9   =   4
	0*x1+	0*x2+	0*x3+	1*x4+	1*x5+	1*x6+	0*x7+	0*x8+	0*x9   =   6
	0*x1+	0*x2+	0*x3+	0*x4+	0*x5+	0*x6+	1*x7+	1*x8+	1*x9   =  10
	1*x1+	0*x2+	0*x3+	1*x4+	0*x5+	0*x6+	1*x7+	0*x8+	0*x9   =   3
	0*x1+	1*x2+	0*x3+	0*x4+	1*x5+	0*x6+	0*x7+	1*x8+	0*x9   =   5
	0*x1+	0*x2+	1*x3+	0*x4+	0*x5+	1*x6+	0*x7+	0*x8+	1 *x9  =   12

↓ Z=1*x1 + 0*x2 + 2*x3 + 3*x4 + 5*x5 + 4*x6 + 1*x7 + 2*x8 + 3*x9]

1*x1+ 1*x2+ 1*x3+ 0*x4+ 0*x5+ 0*x6+ 0*x7+ 0*x8+ 0*x9 = 4

0*x1+ 0*x2+ 0*x3+ 1*x4+ 1*x5+ 1*x6+ 0*x7+ 0*x8+ 0*x9 = 6

0*x1+ 0*x2+ 0*x3+ 0*x4+ 0*x5+ 0*x6+ 1*x7+ 1*x8+ 1*x9 = 10

1*x1+ 0*x2+ 0*x3+ 1*x4+ 0*x5+ 0*x6+ 1*x7+ 0*x8+ 0*x9 = 3

0*x1+ 1*x2+ 0*x3+ 0*x4+ 1*x5+ 0*x6+ 0*x7+ 1*x8+ 0*x9 = 5

0*x1+ 0*x2+ 1*x3+ 0*x4+ 0*x5+ 1*x6+ 0*x7+ 0*x8+ 1 *x9 = 12

Результат работы программы (решение симплекс методом):

0 4 0 0 0 6 3 1 6 0 0 0 0

Columns 14 through 16

0 0 47

Что означает:

x1=4

x6=6

x7=3

x8=1

x9=6

Если сравнить эти решения, то можно заметить, что они абсолютно одинаковые. Исходя и этого можно сделать вывод, что задача была решена верно.

5.3.Пусть в задаче 5.1 ежедневный спрос хранилища 3 падает до 4 млн. галлонов. Избыток продукции на нефтеперерабатывающих заводах 1 и 2 должен переправляться на грузовиках в другие хранилища. Соответствующие средние транспортные издержки составляют 1,5 долл. за 100 галлонов при перевозке с завода 1 и 2,2 долл. при перевозке с завода 2. Завод 3 может использовать избыток бензина для нужд своего химического производства. Сформулируйте соответствующую транспортную задачу.

Условие задачи 5.1.Три нефтеперерабатывающих завода с максимальной ежедневной производительностью в 6, 5 и 8 млн. галлонов. Бензин транспортируется в бензохранилища по трубопроводу. Стоимость перекачки бензина на одну милю, рассчитанная с учетом длины трубопровода, составляет 1 цент на 100 галлонов. В таблице расстояний, приведенной ниже, показано, что завод 1 не связан с хранилищем 3. Сформулируйте соответствующую транспортную задачу.

		Бензохранилища
		1	2	3
	1	120	180	—
Заводы	2	300	100	80
	3	200	250	120

Решение:

Транспортная задача:

1,8	2,7	999999999	99999999999	6000000
6,6	2,2	1,76	99999999999	5000000
2	2,5	1,2	99999999999	8000000
x1	x2	4000000	19000000-x1-x2-4000000

—

Скачать ZIP-архив с исходными кодами

Ноябрь 2015
Пн	Вт	Ср	Чт	Пт	Сб	Вс
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

Добавить комментарий Отменить ответ