Section 6: Distribution and Network Models

Presentation Transcript

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

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

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.

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

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.

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

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

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

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.

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?

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

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

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

QM Input

QM Solution

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.

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

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.

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

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

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

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

QM Output

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.

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?

Practice Problem

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

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.

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

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

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

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.

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:

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?

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

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 =