## Network Simplex Pivot Tool

Mode:     (Seed: , Nodes: )

Or Select a Problem from Linear Programming: Foundations and Extensions:

 Pick a judge: Bart Simpson The Apprentice (you're fired) The Apprentice (don't think so) Show: Shipping Costs Supplies/Demands Flow Variables Slack Variables Dual Variables Artificial Costs Artificial Supplies Artificial Flows Artificial Slacks   Node edits:   Name:   Supply: Arc edits:   Shipping Cost:   Artificial Flow/Slack:

#### Instructions

There are three ways to create a problem. One is to build it up one node at a time. The second way is to let the applet generate a random problem having a specified number of nodes. The third way is to select a problem from the drop-down menu. Since the latter two are easier to explain, let's start with them.

#### Generating a Random Problem

To generate a random problem (both network topology and numerical data), choose either the Pivot 2-Phase or the Pivot Self-Dual mode with the choice box and then click on the Generate Random Problem button.

Note: If some of the randomly generated nodes are positioned in such a way that some of the numerical information gets blocked, you can click and drag the nodes to make things easier to read. Changing the appearance does not change the underlying problem you are trying to solve.

To generate just a random topology, choose the Build Network mode with the choice box and then click on Generate Random Problem.

To generate random data for a previously defined topology, choose the Edit Supplies/Costs mode with the choice box and then click on Generate Random Problem.

The textfield labeled Nodes can be editted to specify the number of nodes in the network. If the Seed field is left blank then an internally generated seed value will be used and the behavior of the generator will be different every time the applet is run. If, however, a seed value is given (it must be an integer), then that value is used to seed the random number generator. Specifying a value for the number of nodes and for the seed uniquely determines the sequence of problems generated.

#### Select a Problem from the Drop-Down Menu

Several specific examples and exercises from my book can be accessed directly using the drop-down. Select what you like and pick one of the two "Modes" for solving the problem.

#### Build Network

Choosing the Build Network mode with the choice box, you can build a network from scratch with the mouse. To do this, you specify arcs in the network by a pair of mouse clicks. The first mouse click must be on an existing node in the network. The second mouse click can be anywhere on the drawing canvas. If it is on an existing node, then an arc is created connecting the two selected nodes. By default, the direction of the arc is from the first node to the second node. To reverse the direction, simply hold the shift key while making the second click.

If the second mouse click is not on any existing node, then a new node is automatically created at the clicked location and an arc is created as before.

The applet always initializes the network with one preexisting node, which is labeled a. We refer to this node as the root node. It plays a special role in the following discussion.

By forcing you to build the network arc by arc always using an existing node for the first click, we guarantee that the network will be connected. Also, we use those arcs which involved the creation of a new node as the tree arcs for an initial spanning tree. All other arcs are non-tree arcs. Tree arcs are shown in red.

#### Editting Supplies/Costs

After defining the nodes and arcs, you need to specify supplies at the nodes and costs on the arcs. (Demands are given as negative supplies.) Choosing the Edit Supplies/Costs mode with the choice box, you can edit these values one at a time. The values are initially set to zero and are now shown on the graph. To change a supply value for a specific node, click on the node. The current name of the node and its supply value of zero will appear in the Node edits section to the right of the graph. There you can change the name of the node and you can change the supply. To change an arc cost, click on the pointer portion of the arc's arrow. You will then be able to enter a shipping cost in the Arc edits section.

Note that the root node's supply is automatically set so that the total supply equals the total demand. Hence, there is no need ever to edit the supply at the root node. In this way the applet ensures that none of the problems are trivially infeasible in the sense of a misbalance between total supply and total demand.

#### Pivoting

Having set data values, you are now ready to solve the problem you've specified. Choosing the Pivot 2-Phase mode with the choice box, you can use the mouse to specify pivots as pairs of mouse clicks on arcs.

In this mode, the supply and cost data disappear and instead you see current values of arc flows on tree arcs and dual slacks (i.e., reduced costs ) on non-tree arcs. Negative values for any of these arc variables are highlighted in bright pink. If the network does not show any pink, then the current spanning tree defines an optimal solution to the problem. To confirm that a solution is optimal, you can click on the Optimal button. Similarly, if you think that a current solution clearly demonstates that the problem is primal or dual infeasible, you can click on the corresponding button to confirm.

To facilitate pivoting, there is a set of artificial arc variables (both flows and dual slacks) that are initially set all to one but which change as pivots are done. To keep the canvas uncluttered, these artificial variables are not displayed unless specifically requested by clicking on their names in the Show section to the right of the main canvas. When the artificial variables are being shown, each one appears just after the corresponding regular variable. If an artificial variable is negative (i.e., infeasible), it is highlighted in yellow. Using the artificial variables appropriately, one can use the pivot tool to carry out the following methods from Linear Programming: Foundations and Extensions:

• Primal-Phase-I, Dual-Phase-II, Simplex Method
• Dual-Phase-I, Primal-Phase-II, Simplex Method
• Primal-Dual Simplex Method

#### Showing/Hiding Information

As explained above, there are four modes of operation:
• Build Network
• Edit Supplies/Costs
• Pivot 2-Phase
• Pivot Self-Dual
In each of these modes, different types of information are displayed. In the Build Network mdoe, only nodes and arcs are shown---i.e., no numerical data is displayed. In Edit Supplies/Costs mode, supply and cost data is shown on the graph of the network. In Pivot 2-Phase mode, current values of the arc variables are shown. This is the information you see by default. But, by clicking on things in the Show section you can select exactly the information you'd like to see. And, lastly, there is the Pivot Self-Dual mode. This mode is similar to the Pivot 2-Phase mode except that in addition what is shown in the 2-Phase mode you also see the artificial flows and artificial dual slacks and these artificial values are shown as they are multiplied by the parametric self-dual parameter $$\mu$$.

One of the options in the Show menu is to show Node Variables. These are the dual variables associated with each node. Since none of the three variants of the simplex method mentioned above use the dual variables in the pivot selection rule, these values are by default not shown (again, to keep the network from looking too cluttered). But it is important to be able to get these values---the Show menu makes it possible. Note that the dual variables are computed so that the root node's dual is zero.

If all information is shown simultaneously, the network can look quite cluttered. But some effort has been made to prevent overlapping numerical fields. In particular supply/demand data is shown above the node to which it applies, whereas dual variables are shown below the node. Similarly cost data is shown shifted up slightly from the centroid of the arc whereas arc variables are shown shifted down slightly. If nonetheless some data gets clobbered, you can use the mouse to drag (slowly, please) the nodes around some to get a better layout.

Finally, click here for the Java Applet version of the same tool.