Section 6: Distribution and Network Models

0
0
1782 days ago, 1883 views
PowerPoint PPT Presentation
Presentation. An uncommon class of straight programming issues is called Network Flow issues. Five unique issues are considered:Transportation ProblemsAssignment ProblemsTransshipment ProblemsShortest-Route ProblemsMaximal Flow Problems. . Transportation, Assignment, and Transshipment Problems.

Presentation Transcript

Slide 1

´╗┐Section 6: Distribution and Network Models Instructor: Dr. Neha Mittal

Slide 2

Introduction An exceptional class of direct programming issues is called Network Flow issues. Five unique issues are viewed as: Transportation Problems Assignment Problems Transshipment Problems Shortest-Route Problems Maximal Flow Problems

Slide 3

Transportation, Assignment, and Transshipment Problems They are all system models , spoke to by an arrangement of hubs, an arrangement of circular segments, and capacities (e.g. costs, supplies, requests, and so on.) related with the circular segments as well as hubs.

Slide 4

In this part: Transportation & Assignment Problems Network Representation General LP Formulation Solution with QM Software Transshipment Problem Network Representation General LP Formulation

Slide 5

Transportation Problem The transportation issue tries to limit the aggregate delivery expenses of transporting merchandise from m starting points (each with a supply s i ) to n goals (each with a request d j ), when the unit shipping cost from a cause, i , to a goal, j , is c ij . The system portrayal for a transportation issue with two sources and three goals is given on the following slide.

Slide 6

Transportation Problem Network Representation 1 d 1 c 11 1 c 12 s 1 c 13 2 d 2 c 21 c 22 2 s 2 c 23 3 d 3 Sources Destinations

Slide 7

Transportation Problem Linear Programming Formulation Using the documentation: x ij = number of units dispatched from inception i to goal j c ij = cost per unit of delivery from beginning i to goal j s i = supply or limit in units at cause i d j = request in units at goal j

Slide 8

= Transportation Problem Linear Programming Formulation (proceeded with) x ij > 0 for all i and j

Slide 9

LP Formulation Special Cases The goal is boosting benefit or income: Minimum delivery ensure from i to j : xij > Lij Maximum course limit from i to j : xij < Lij Unacceptable course: Remove the comparing choice variable. Take care of as an expansion issue.

Slide 10

Transportation Problem: Example #1 Acme Acme Block Company has orders for 80 tons of concrete pieces at three rural areas as takes after: Northwood - 25 tons, Westwood - 45 tons, and Eastwood - 10 tons. Summit has two plants, each of which can deliver 50 tons for every week. Conveyance cost per ton from each plant to each rural area is appeared on the following slide. In what capacity ought to end of week shipments be made to take care of the above requests?

Slide 11

Delivery Cost Per Ton Northwood Westwood Eastwood Plant 1 24 30 40 Plant 2 30 40 42

Slide 12

Network Representation Demand Unit Costs 1 North Supply 25 24 1 Plant 1 50 30 40 2 West 45 30 2 Plant 2 40 50 42 3 East 10 Origins Destinations

Slide 13

Shipment Cost Minimization/LP Formulation Decision factors: x ij = Amount transported for i = 1-2 and j = 1-3 Min Z = 24x 11 + 30x 12 + 40x 13 + 30x 21 + 40x 22 + 42x 23 s.t. x 11 + x 12 + x 13 < 50 (Plant 1 limit) x 21 + x 22 + x 23 < 50 (Plant 2 limit) x 11 + x 21 = 25 (Northwood request) x 12 + x 22 = 45 (Westwood request) x 13 + x 23 = 10 (Eastwood request) x ij > 0 for i = 1-2 birthplaces, j = 1-3 goals

Slide 14

QM Input

Slide 15

QM Solution

Slide 17

Optimal Solution (Minimizing Cost) From To Amount Cost Plant 1 Northwood 5 120 Plant 1 Westwood 45 1,350 Plant 2 Northwood 20 600 Plant 2 Eastwood 10 420 Total Cost = $2,490 Notes : Supply from Plant 2 is not completely used (abundance appeared in "Sham" segment in QM). Additionally, nothing is sent from Plant 1 to Eastwood or from Plant 2 to Westwood. The unit cost for that course should diminish more than the minor cost (appeared in QM) keeping in mind the end goal to be used.

Slide 18

QM Output (utilizing "Transportation" Module) Transportation Shipments Window 1) Which plant has abundance supply? What amount? 2) What the unit cost of shipments from Plant 1 to Eastwood would need to be all together for that course to be used (unique cost = $40) Marginal Costs Window

Slide 19

Transportation Problem: Example #2 The Navy has 9,000 pounds of material in Albany, Georgia that it wishes to ship to three goals: San Diego, Norfolk, and Pensacola. They require 4,000, 2,500, and 2,500 pounds, respectively. There are three distinct transporters and government directions require level with circulation of delivery among the three bearers.

Slide 20

The shipping costs per pound for truck, railroad, and plane travel are demonstrated as follows. Plan and comprehend a direct program to decide the transportation courses of action (mode, goal, and amount) that will limit the aggregate delivery cost. Goal Mode San Diego Norfolk Pensacola Truck $12 $ 6 $ 5 Railroad 20 11 9 Airplane 30 26 28

Slide 21

Decision Variables We need to decide the pounds of material, x ij , to be sent by mode i to goal j . The accompanying table abridges the choice factors: San Diego Norfolk Pensacola Truck x 11 x 12 x 13 Railroad x 21 x 22 x 23 Airplane x 31 x 32 x 33

Slide 22

Objective Function Minimize the aggregate transportation cost. Min: (shipping cost per pound for every mode per goal matching) x (number of pounds dispatched by mode per goal blending). Min: 12 x 11 + 6 x 12 + 5 x 13 + 20 x 21 + 11 x 22 + 9 x 23 + 30 x 31 + 26 x 32 + 28 x 33

Slide 23

Constraints Equal utilization of transportation modes: (1) x 11 + x 12 + x 13 = 3000 (2) x 21 + x 22 + x 23 = 3000 (3) x 31 + x 32 + x 33 = 3000 Destination material prerequisites: (4) x 11 + x 21 + x 31 = 4000 (5) x 12 + x 22 + x 32 = 2500 (6) x 13 + x 23 + x 33 = 2500 Non-antagonism of factors: x ij > 0, i = 1,2,3 and j = 1,2,3

Slide 24

QM Output

Slide 25

Solution Summary San Diego will get 1000 lbs. by truck and 3000 lbs. via plane. Norfolk will get 2000 lbs. by truck and 500 lbs. by railroad. Pensacola will get 2500 lbs. by railroad. The aggregate transportation cost will be $142,000.

Slide 26

Practice Problem Powerco has three electric power plants that supply the electric needs of four urban areas. The related supply of each plant and request of every city is given in the table. The cost of sending 1 million kwh of power from a plant to a city relies on upon the separation the power must travel. Decide what amount of vitality ought to be provided to the city by which plant?

Slide 28

Practice Problem

Slide 29

Costs to Haul from each site to each factory (round-outing expenses) are given underneath:

Slide 30

Assignment Problem A task issue tries to limit the aggregate cost task of i laborers to j employments, given that the cost of specialist i performing work j is c ij . It accept all specialists are alloted and each employment is performed. A task issue is an uncommon instance of a transportation issue in which all provisions and all requests are equivalent to 1; thus task issues might be tackled as straight projects. The system portrayal of a task issue with three laborers and three employments is appeared on the following slide.

Slide 31

Network Representation c 11 1 c 12 c 13 Agents Tasks c 21 c 22 2 c 23 c 31 c 32 3 c 33

Slide 32

Linear Programming Formulation Using the documentation: x ij = 1 if operator i is doled out to errand j 0 generally c ij = cost of appointing operator i to undertaking j

Slide 33

Linear Programming Formulation (proceeded with) x ij > 0 for all i and j

Slide 34

LP Formulation Special Cases Number of operators surpasses the quantity of assignments: Number of undertakings surpasses the quantity of specialists: Add enough sham operators to even out the quantity of operators and the quantity of assignments. The target work coefficients for these new factor would be zero. Additional operators essentially stay unassigned.

Slide 35

LP Formulation Special Cases (proceeded with) The task options are assessed as far as income or benefit: Solve as an expansion issue. A task is unsuitable: Remove the comparing choice variable. A specialist is allowed to work t errands:

Slide 36

Practice Problem An electrical temporary worker pays his subcontractors a settled expense in addition to mileage for work performed. On a given day the temporary worker is confronted with three electrical occupations related with different activities. Given underneath are the separations between the subcontractors and the undertakings. Ventures Subcontractor A B C Westside 50 36 16 Federated 28 30 18 Goliath 35 32 20 Universal 25 14 How ought to the contractual workers be appointed to limit add up to mileage costs?

Slide 37

Network Representation 50 West . A 36 16 Subcontractors Projects 28 30 Fed. B 18 32 35 Gol. C 20 25 Univ. 14

Slide 38

Linear Programming Formulation Min 50 x 11 +36 x 12 +16 x 13 +28 x 21 +30 x 22 +18 x 23 +35 x 31 +32 x 32 +20 x 33 +25 x 41 +25 x 42 +14 x 43 s.t. x 11 + x 12 + x 13 < 1 x 21 + x 22 + x 23 < 1 x 31 + x 32 + x 33 < 1 x 41 + x 42 + x 43 < 1 x 11 + x 21 + x 31 + x 41 = 1 x 12 + x 22 + x 32 + x 42 = 1 x 13 + x 23 + x 33 + x 43 =

SPONSORS