Kennesaw State University CS 4491 Assigment 8


Kennesaw State University
Department of Computer Science
Advanced Topic in Computer Science CS 4491/2
Assignment # 8 / Supply and Demand/ Max Traffic Flow

Dalibor Labudovic

05/6/2013
















Initial Problem Statement:
1) A factory of automobile space parts has two supply locations: S1 and S2. There are three demand points that require 35, 42, and 50 parts respectively. Supply point S1 has a capacity of 85 parts and S2 a capacity of 65 parts. The following table shows transportation costs and the costs (penalty) for excess demand of each supply point. Formulate and solve the optimization problem with lp_solve.
D1
D2
D3
Supply
S1
25
45
42
85
S2
20
60
50
65
Demand
35
42
50

Penalty
100
85
150


2) Traffic engineers are studying traffic patterns in part of a city. The immediate problem is to find the maximum flow of vehicle from a source point, S, to a destination point, D. Figure 1 and the following table show the flow capacity of the various roads, (between nodes). Note that the direction of the traffic is important. Formulate and solve a linear optimization problem that computes the maximum traffic flow from point S to point D.
Arc
Capacity

Arc
Capacity
S-3
6

4-5
5
3-S
1

5-4
1
S-4
7

4-6
7
4-S
1

6-4
1
S-2
5

4-D
2
2-S
0

D-4
0
2-4
1

5-D
8
4-2
4

D-5
0
2-3
2

5-6
2
3-2
1

6-5
2
3-4
2

6-D
8
4-3
1

D-6
2
3-5
4

5-3
3

Summary and purpose of the assignment activity:
The summary of the assignment is to utilize an optimization mathematical formalization for optimization and translate it into a simple program. The program then is run through another program LP solver to find the numerical solution to the linear optimization problem.
The purpose of this assignment activity is to utilize deep knowledge of mathematical and invoke real world problem issue to resolve with the use of computational programs.


Detail description of the solution and used in the project:
The solution used in this project is the use of mathematical linear optimization formulation to devise a customized formula then translate it to the computational model. The program lp solve will then find a numerical value and or the best optimal route from supply point to destination point.


1) SOURCE CODE
/* Car Parts */


/* Objective */


Minimize: 25x11 + 45x12 + 42x13 +
20x21 + 60x22 + 50x23 +
100x31 + 85x32 + 150x33; /* Penalty */


/* Capacity Constraints (Supply) */
x11 + x12 + x13 <= 85;
x21 + x22 + x23 <= 65;
x31 + x32 + x33 <= 0;








/* Capacity Constraints (Demand) */
x11 + x22 + x31 >= 35;
x12 + x22 + x32 >= 42;
x13 + x23 + x33 >= 50;
x14 + x24 + x34 >= 23;


2.) SOURCE CODE
/* max_flow.lp*/

/* Objective Function */

Maximize: xsd;

/*Source and destination constraints */
xsd = x4d + x5d + x6d;

/*arc capasity constraints */
xs2 <= 5;x2s <= 0;
xs4 <= 7;x4s <= 1;
xs3 <= 6;x3s <= 1;
x23 <= 2;x32 <= 1;
x24 <= 1;x42 <= 4;
x26 <= 4;x62 <= 3;
x34 <= 2;x43 <= 1;
x35 <= 4;x53 <= 3;
x45 <= 5;x54 <= 1;
x46 <= 7;x64 <= 1;
x4d <= 2;xd4 <= 0;
x56 <= 2;x65 <= 2;
x5d <= 8;x65 <= 0;
x6d <= 8;xd6 <= 2;

/* intermediate nodes constraints */
xs2 - xs3 - xs4 = 0;
x2s - x3s - x4s = 0;
x32 = 0;
x32 = 0;
x35 - x34 + s45 = 0;
x26 - x24 + x25 = 0;
x56 = 0;
x65 = 0;
xs4 - x4d = 0;
x45 - x5d = 0;
x46 - 6d = 0;


Table of results:
1)

Value of objective function: 4515

Actual values of the variables:
x11 0
x12 7
x13 50
x21 0
x22 35
x23 0
x31 0
x32 0
x33 0
x14 23
x24 0
x34 0

2)
Value of objective function: 15

Actual values of the variables:
xsd 15
x4d 2
x5d 5
x6d 8
xs2 2
x2s 0
xs4 2
x4s 0
xs3 0
x3s 0
x23 0
x32 0
x24 0
x42 0
x26 0
x62 0
x34 0
x43 0
x35 0
x53 0
x45 5
x54 0
x46 0
x64 0
xd4 0
x56 0
x65 0
xd6 0
s45 0
x25 0
d 0

Comments and Conclusion:
In conclusion this assignment activity was real well thought out and very difficult to understand and process but this type of assignment will provide me with the knowledge and skills to better my overall understanding of computational model and computational processing. The principles and guides line I learned in this project will be a useful still not only in C programming but also scientific computing.


Script:
1)
Script started on Sun 05 May 2013 11:01:32 PM EDT
#]0;dlabudovic@ubuntu: ~/Documents/CS4491/assign_08/P1#dlabudovic@ubuntu:~/Documents/CS4491/assign_08/P1$ lp_solbe##[K##[Kve car_parts.lp

Value of objective function: 4515

Actual values of the variables:
x11 0
x12 7
x13 50
x21 0
x22 35
x23 0
x31 0
x32 0
x33 0
x14 23
x24 0
x34 0
#]0;dlabudovic@ubuntu: ~/Documents/CS4491/assign_08/P1#dlabudovic@ubuntu:~/Documents/CS4491/assign_08/P1$ exit
exit

Script done on Sun 05 May 2013 11:01:51 PM EDT

2)
Script started on Sun 05 May 2013 11:02:18 PM EDT
#]0;dlabudovic@ubuntu: ~/Documents/CS4491/assign_08/P2#dlabudovic@ubuntu:~/Documents/CS4491/assign_08/P2$ lo##[Kp_solve max_flow.lp

Value of objective function: 15

Actual values of the variables:
xsd 15
x4d 2
x5d 5
x6d 8
xs2 2
x2s 0
xs4 2
x4s 0
xs3 0
x3s 0
x23 0
x32 0
x24 0
x42 0
x26 0
x62 0
x34 0
x43 0
x35 0
x53 0
x45 5
x54 0
x46 0
x64 0
xd4 0
x56 0
x65 0
xd6 0
s45 0
x25 0
d 0
#]0;dlabudovic@ubuntu: ~/Documents/CS4491/assign_08/P2#dlabudovic@ubuntu:~/Documents/CS4491/assign_08/P2$ exit
exit

Script done on Sun 05 May 2013 11:02:33 PM EDT

Comments

Post a Comment

Popular posts from this blog

How to clear & format SD card

Open CMD, go to Win Start button, type CMD Start DiskPart,  type diskpart in CMD Display all disks, type list disk Select the disk to clean, type select disk [# disk you would like to clean] Clean selected disk, type clean Make sure disk is selected, type list disk again. You should see * next to the disk you selected Create a partition, type create partition primary, then type select partition 1 Activate partition, type active Format disk, type format FS=NTFS label=mydrive quick
Read more

Sharepoint List: Days Elapsed or Countdown

Image
SharePoint List: How to Display Days Elapsed or Countdown  Problem :Have you thought about introducing a countdown or even days elapsed as a feature in a sharepoint list? Solution: Well i have a solution for you using javascript. It does get a little involved with code but very easy to implement. 4 Step Implementation: Step 1 : Create the list in sharepoint and name it what you like Add two columns: Column 'Today" type = Date and Time Column 'Days Elapsed' type = calculated Step 2 : Under list settings, go to column you have just added called Days Elapsed and enter the following formula: =ROUND(Today-Created,0)&" days" --> Output Data Type as a Single Line of Text. Step 3 : Some code --> Copy the code below and paste it into a nodepad, go through the code and change the name of your list: Look for LIST NAME , thats where you will change the name to your list name and also change the column name for "Today" if you named it...
Read more

CS4500 Test 4 Study Guide

CS4500  Test 4 Study Guide Note: This is a study guide, answers may be incorrect, double check and best of luck. A ________ network is totally isolated from the global Internet. Private On a network that uses NAT, the router can use ______ global address(es). A pool of In the sending computer, UDP sends a data unit from the _____ layer. Application TCP uses ____ for error detection. Checksum, Acknowledge and time-out _____ is an IP layer security protocol that only provides integrity and authentication. AH The ______ timer keeps track of the time between the sending of a segment and the receipt of an acknowledgement. Retransmission The definition of reliable delivery includes ______. Error-Free Delivery Which of the following is not part of the UDP user datagram header? Length of Header The _____ defines the server program. Well-Known Port Number If the incoming queue of a UDP client overflows, _____ The user datagrams are discarded and a port unrea...
Read more