Mathematical programming - Ngo Huu Tam

Step 1Find the initial PACB using the minimum cost method as follows:

Assign 40 tons to cell (3,4), point A 320 tons left, delete column B 4 .

Assign 20 tons to cell (2,1), point A 2Only 20 tons left, delete column B 1 .

Assign 30 tons to cell (1,2), delete row A 1and column B 2 .

Divide into cells (2,3) 20 tons, cells (3,3) 20 tons, cells (3,4) 10 tons. The number of selected cells is 6, so we add cells (1,4) to make 7 = 4 +4 –1 cells.

Step 2 : Set 0 fee for selected boxes

s 1 =1 s 2 = 2 s 3 = 0 s 4 = 3

From column B 3, for s 3 = 0, we can calculate r 4 = 0, r 3 = -4 , r 2 = -3 ; r 3 = -4 s 4 = 3 ; s 4 = 3 r 1 = -5 ; r 1 = -5 s 2 = 2; r 2 = -3 s 1 = 1.

Recalculate the fare of the cells.

r 1 = -5

Collect Play	B 1 20	B 2 30	B 3 50	B 4 40
A 1 : 30	8	3  30	5	2 
A2 : 40	2  20	4	3  20	7
A3 : 60	5	6	4  20	1  40
A 4 : 10	0	0	0  10	0

Maybe you are interested!

r 2 = -3

r 3 = -4

r 4 = 0

Collect

Play

B 1 20	B 2 30	B 3 50	B 4 40
A 1 : 30	4	0  30	0	0 
A2 : 40	0  20	3	0  20	7
A3 : 60	2	4	0  20	0  40
A 4 : 10	1	2	0  10	3

All cells have non-negative charges so PACB is optimal. The optimal solution to the original problem is

Collect

Play

B 1 20

B 2 30

B 3 50

B 4 40

A 1 : 30

A2 : 40

A3 : 60

f min  8  20  5  20  3  20  4  10  360

2.3. Transport problem with prohibited cells :

In reality, due to damaged bridges, ferries, roads, or security issues, or because the distance is too long and requires a lot of transportation time, while the conditions for preserving goods cannot be implemented or are not in time, etc., there are some routes that cannot transport goods. These routes on the transport board are characterized by cells that cannot be distributed to goods. These cells are called prohibited cells.

In addition, the forbidden cell also appears in the unbalanced transmission and reception transport problem under the condition that some transmitting stations must transmit all the goods (total transmission > total collection) or under the condition that some receiving stations must collect all the goods (total transmission < total collection).

To solve the problem of transporting prohibited cells, we set the “fare” at the prohibited cell as “ M ”.

with the problem of minimizing the objective function ( f

  min)

and is “ M ” for function problems

maximum target ( f   max) , with M being an arbitrarily large positive number, we next apply

Use substitution algorithm or zero cell fee algorithm to solve.

Example 4

A company signed a contract to deliver to a customer 5 products of type A1 , 7 products of type A2 , 8 products of type A3 .within 1 month .The company has 3 factories I, II, III and factory III cannot produce product A3 . The production capacity of each factory I, II, III in 1 month is 9 products, 6 products, 5 products respectively. The profit earned on each product produced by the factories is given in the following table (unit: 20,000,000 VND/product).

X.Product Industry

I 9	II 6	III 5
A 1 : 5	8.5	6	7
A2 : 7	9	10	6.5
A 3 : 8	6	7.5	Forbidden City

Ask how to assign production to the factories to carry out the contract with the greatest profit and tell the amount of profit earned?

Prize

This problem is in the form of a balanced transmission and reception problem with the forbidden cell (3,3). Because

is the problem f  max so c 33 M , where M is an arbitrarily large positive number.

X.Product Industry

I 9	II 6	III 5
A 1 : 5	8.5	6	7
A2 : 7	9	10	6.5
A 3 : 8	6	7.5	-M

Distribute in turn as follows: cell (2,2)

6 ; cell (2,1)

1; cell (1,1)

5; cell

(3.1)

3; cell (3,3) 5

After the distribution is complete, we get the initial non-degenerate basic solution. Find the row potentials and column potentials and then calculate k i j u i+ v j- c i j we get:

X.Product Industry	I 9			II 6			III 5
A 1 : 5	8.5		0 5	6		3.5	7	M  4.5 Enter
A2 : 7	9		0 1	10		0 6	6.5	M  3.5
A 3 : 8	6		0 3	7.5		 0.5	-M	0 Give 5

u 1  2.5

u 2  3

v 1  6

v 2  7

v 3  M

give

u 3  0

Cell (1,3)

Have

k 13  M  4.5  0

So the current basic solution is not optimal.

The input cell is cell (1,3).

The control loop is V   (1,1), (1,3), (3,1), (3,3)  , V C

  (1,1), (3,3)  , V L   (3,1), (1,3)  .

The given cell is the cell

(3.3)

and the adjustment amount is

x 33 5. Make a new plan and find the system

new position we get:

Give

v 1  0

v 2  1

v 3  1.5

u1  8.5

X.Product Industry	I 9			II 6	III 5
A 1 : 5	8.5		0 0	6 3.5	7 	0 5
A2 : 7	9		0 1	10 0 Give 6	6.5	1
A 3 : 8	6		0 8	7.5  0.5 Enter	-M	M  4.5

u 2  9

u 3  6

Cell (3,2)

Have

k 32  1.5  0

So the current basic solution is not optimal.

The input cell is cell (3,2) .

The control loop is V   (2,1), (2,2), (3,1), (3,2)  , V C

  (1,1), (3,3)  , V L   (3,1), (1,3)  .

The given cell is cell (2,2)

and the adjustment amount is

x 22 6. Make a new plan and find the system

X.Product Industry	I 9				II 6			III 5
A 1 : 5	8.5			0 0	6		4	7 	0 5
A2 : 7	9			0 7	10		0.5 0	6.5	1
A 3 : 8	6			0 2	7.5		0 6	-M	M  4.5

new position we get:

u1  8.5

u 2  9

Give

v 1  0

v 2  1.5

v 3  1.5

u 3  6

All cells have k i j  0 so this basic solution is optimal. Since the forbidden cell (3,3) takes the value

distribution value

x 33  0

So the optimal solution to the problem is:

X.Product Industry

I 9

II 6

III 5

A 1 : 5

8.5

7 

A2 : 7

6.5

A 3 : 8

7.5

No entry

Maximum total profit:

f max  [9  7  6  2  7.5  6  7  5]  20,000,000 đồng = 155  20,000,000

Note: Can be solved using the zero-cost algorithm .

group

Example 5Solve the transportation problem given by the following table with the condition that station B is 1must collect all goods:

Collect

Play

B 160	B 220	B 3 50
A 1 : 75	6	3	1
A2 : 45	4	2	3

Prize

This is a problem where total revenue is greater than total output with the amount of goods to be collected being 10 tons greater than the amount of goods to be output. We set up an additional fake output station A 3with the delivery quantity of 10 tons and the freight charges of cells (3,2), (3,3) are 0 and cell (3,1) is M with M being an arbitrary large number (because B 1must collect enough goods so station B 1do not collect counterfeit goods from station A 3 , so cell (3,1) must be a forbidden cell).

Collect

Play

B 1 60	B 2 20	B 3 50
A 1 : 75	6	3	1
A2 : 45	4	2	3
A 3 :10	M	0	0

Step 1 : Find the initial PACB using the minimum cost method.

Classify into cell (1,3) 50 tons, row A 1Only 25 tons left, delete column B 3 .

Classify into cell (2,2) 20 tons, goods A 2Only 25 tons left, delete column B 2 .

Classify into cell (2,1) 25 tons, cell (1,1) 25 tons, cell (3,1) 10 tons.

Step 2 : Set the fee to 0 in the selected boxes.

for s 1 = 0 s 2 = 2 s 3 = 5

For s 1= 0 calculates r 1= -6, r 2= -4, r 3= -M, s 2= 2, s 3= 5 Recalculate the fare for all cells and we get

r 1 = -6

Collect Play	B 1 60	B 2 20	B 3 50
A 1 : 75	6  25	3	1  50
A2 : 45	4  25	2  20	3
A 3 : 10	M  10	0	0

r 2 = -4 r 3 = -M

Collect

Play

B 1 60	B 2 20	B 3 50
A 1 : 75	0  25	-1	0  50
A2 : 45	0  25	0  20	4
A 3 : 10	0  10	2-M 	5-M

Step 3 : Cells (1,2), (3,2), (3,3) have negative charges, so the current PACB is not optimal. Step 4: Insert cell (3,2) to get the loop V =  (2,1),(2,2),(3,1),(3,2) 

VC =  ( 2,2 ),(3,1) , V L =  (2,1),(3,2) 

The given cell is cell (3,1), the adjustment amount is 10. Cells (2,1) and (3,2) each add 10 tons; cells (2,2), (3,1) each subtract 10 tons.

s 1 = 0 s 2 = -2 s 3 = 0

Step 2: Set the selected boxes to 0 fees

r 1 = 0

Collect Play	B 1 60	B 2 20	B 3 50
A 1 : 75	0  25	3	0  50
A2 : 45	0  35	2  10	4
A 3 : 10	0	2-M  10	5 -M

r 2 = 0 r 3 = M

Let r 1= 0 calculates 1= 0, s 3= 0; s 1= 0 r 2= 0; r 2= 0 s 2= -2; s 2= -2 r 3= M. Recalculate the fare for all cells and we get

Collect

Play

B 1 60	B 2 20	B 3 50
A 1 : 75	0 25	1	0 50
A2 : 45	0 35	0 10	4
A 3 : 10	0	0 10	5

Collect

Play

B 1 60

B 2 20

B 3 50

A 1 : 75

A2 : 45

All cells have non-negative charges so P ACB is optimal. So the optimal solution to the original problem is

f min = 6.25 + 1.50 + 2.10 + 4.35 = 360.

Example 6

A garment company needs to distribute 2800 units of garment products type A1 , 2200 units of garment products type A2into three factories B 1 , B 2 , B 3to produce, with production capacity ( number of units of type A products 1or product type A 2 ) are 1600, 2000, 2400 product units respectively. The production cost ( unit 10,000 VND/1 product unit ) of the company when distributing each product unit to manufacturing enterprises is given in the following table.

Product Enterprise

B 1 1600	B 2 2000	B 3 2400
A 1 :2800	7	7.5	8
A2 : 2200	8	8.5	7.5

Because of the company's development strategy, factory B 3Must collect enough 2400 units of product to produce. Ask how to distribute products to manufacturing enterprises to minimize total cost and calculate the lowest total cost?

Prize

This problem is in the form of an unbalanced transport problem with less transmission.

revenue is

(1600  2000  2400)  (2800  2200)  1000 . Set up more dummy stations

A 3with

quantity to be emitted

a 3 1000 . To station

B 3Collect enough counterfeit goods

A 3impossible

broadcast to station

B 3should

(3.3)