Manuals/calci/Exampleslp

Linear Programming Examples in z3

DESCRIPTION

Basic Linear Programming examples in z3.
Instead of using arrays to solve these problems, we could create a model in a JavaScript object, and solve it through the object's solve function.
Reflecting different domains like Engineering, Statistics, etc.
Testing how we can make better solutions to the standard problems compared to other software.
The lp-format input syntax is a set of algebraic expressions and declarations in the following order:

<objective function>
<constraint>*
<declaration>*

where:

 <objective function> is a linear combination of optional variables and constants, ending with a semicolon, optionally preceded by "max: " or "min: "
 to indicate whether you want it to be minimized or maximized. The case is not important, "Max:" or "MAX:" will work as well. Maximization is the default. 
 Alternatives are minimise, minimize, maximise, Maximize. The objective function is required, but can be empty.
 
 <constraint> is an optional constraint name followed by a colon plus a linear combination of variables and constants or (just one) constraint name followed 
 by a colon (a range) or (just one) variable name without a colon (a bound), followed by a relational operator, followed again by a linear combination of 
 variables and constants, ending with a semicolon. The relational operator can be any of the following: "<" "<=" "=" ">" ">=". There is no semantic difference
 between "<" and "<=" nor between ">" and ">=" (even for integer variables!).

Examples

ExampleLP1: Chocolate Problem
Shannon's Chocolates produces semisweet chocolate chips and milk chocolate chips at its plants in Wichita, KS and Moore, OK. The Wichita plant produces 3000 pounds of semisweet chips and 2000 pounds of milk chocolate chips each day at a cost of $1000, while the Moore plant produces 1000 pounds of semisweet chips and 6000 pounds of milk chocolate chips each day at a cost of $1500. Shannon has an order from Food Box Supermarkets for at least 30,000 pounds of semisweet chips and 60,000 pounds of milk chocolate chips. How should Shannon schedule its production so that it can fill the order at minimum cost? What is the minimum cost?

z3 code: Chocolate Problem

var solver = require('javascript-lp-solver'),
	results,
    model = {
    "name": "Chocolate Problem",
    "optimize": "cost",
    "opType": "min",
    "constraints": {
        "semisweet": {
            "min": 30000
        },
        "milk chocolate": {
            "min": 60000
        }
    },
    "variables": {
        "Kansas": {
            "semisweet": 3000,
            "milk chocolate": 2000,
            "cost": 1000
        },
        "Oklahoma": {
            "semisweet": 1000,
            "milk chocolate": 6000,
            "cost": 1500
        }
    }
};
    
console.log(solver.Solve(model));

Solution:

{ feasible: true,
  result: 18750,
  bounded: true,
  Kansas: 7.5,
  Oklahoma: 7.5 }

ExampleLP2: Coffee Problem
Fred's Coffee sells two blends of beans: Yusip Blend and Exotic Blend. Yusip Blend is one-half Costa Rican beans and one-half Ethiopian beans. Exotic Blend is one-quarter Costa Rican beans and three-quarters Ethiopian beans. Profit on the Yusip Blend is $3.50 per pound, while profit on the Exotic Blend is $4.00 per pound. Each day Fred receives a shipment of 200 pounds of Costa Rican beans and 330 pounds of Ethiopian beans to use for the two blends. How many pounds of each blend should be prepared each day to maximize profit? What is the maximum profit?

z3 code: Coffee Problem

var solver = require('javascript-lp-solver'),
    results,
    model = {
    "name": "Coffee Problem",
    "optimize": "profit",
    "opType": "max",
    "constraints": {
        "costa": {
            "max": 200
        },
        "ethiopian": {
            "max": 330
        }
    },
    "variables": {
        "yusip": {
            "costa": 0.5,
            "ethiopian": 0.5,
            "profit": 3.5
        },
        "exotic": {
            "costa": 0.25,
            "ethiopian": 0.75,
            "profit": 4
        }
    }
};
console.log(solver.Solve(model));

Solution:

{ feasible: true,
  result: 1985,
  bounded: true,
  yusip: 270,
  exotic: 260 }

ExampleLP3: Farmer Problem
Fred's Coffee sells two blends of beans: Yusip Blend and Exotic Blend. Yusip Blend is one-half Costa Rican beans and one-half Ethiopian beans. Exotic Blend is one-quarter Costa Rican beans and three-quarters Ethiopian beans. Profit on the Yusip Blend is $3.50 per pound, while profit on the Exotic Blend is $4.00 per pound. Each day Fred receives a shipment of 200 pounds of Costa Rican beans and 330 pounds of Ethiopian beans to use for the two blends. How many pounds of each blend should be prepared each day to maximize profit? What is the maximum profit?

z3 code: Farmer Problem

var solver = require('javascript-lp-solver'),
    results,
    model = {
    "name": "farmer Problem",
    "optimize": "profit",
    "opType": "max",
    "constraints": {
        "storage": {
            "max": 15000
        },
        "expense": {
            "max": 4000
        },
		"plant": {
            "max": 75
        }
    },
    "variables": {
        "wheat": {
            "storage": 120,
            "expense": 110,
			"plant": 1,
            "profit": 143
        },
        "barley": {
            "storage": 210,
            "expense": 30,
			"plant": 1,
            "profit": 60
        }
    }
};
console.log(solver.Solve(model));

Solution:

{ feasible: true,
  result: 6315.625,
  bounded: true,
  wheat: 21.875,
  barley: 53.125 }

ExampleLP4: SAS Manufacturing Problem
http://support.sas.com/documentation/cdl/en/imlug/66845/HTML/default/viewer.htm#imlug_genstatexpls_sect011.htm
Consider the following product mix example (Hadley, 1962). A shop that has three machines, A, B, and C, turns out four different products. Each product must be processed on each of the three machines (for example, lathes, drills, and milling machines). The following table shows the number of hours required by each product on each machine: The weekly time available on each of the machines is 2,000, 8,000, and 5,000 hours, respectively. The products contribute 5.24, 7.30, 8.34, and 4.18 to profit, respectively. What mixture of products can be manufactured to maximize profit?

z3 code: SAS Problem

var solver = require('javascript-lp-solver'),
	results,
    model = {
    "name": "Manufacturing Problem",
    "optimize": "profit",
    "opType": "max",
    "constraints": {
        "timea": {
            "max": 2000
        },
        "timeb": {
            "max": 8000
        },
		"timec": {
            "max": 5000
        }
    },
    "variables": {
        "m1": {
            "timea": 1.5,
            "timeb": 1,
			"timec": 1.5,
			"profit": 5.24
        },
        "m2": {
            "timea": 1,
            "timeb": 5,
			"timec": 3,
			"profit": 7.3
        },
		"m3": {
            "timea": 2.4,
            "timeb": 1,
			"timec": 3.5,
			"profit": 8.34
        },
		"m4": {
            "timea": 1,
            "timeb": 3.5,
			"timec": 1,
			"profit": 4.18
        }
    },
};
console.log(solver.Solve(model));

Solution:

{ feasible: true,
  result: 12737.05882353,
  bounded: true,
  m1: 294.11764706,
  m4: 58.82352941,
  m2: 1500 }

ExampleLP5: Manufacturing Problem
A company wants to maximize the profit for two products A and B which are sold at $ 25 and $ 20 respectively. There are 1800 resource units available every day and product A requires 20 units while B requires 12 units. Both of these products require a production time of 4 minutes and total available working hours are 8 in a day. What should be the production quantity for each of the products to maximize profits.

z3 code: Manufacturing Problem

var solver = require('javascript-lp-solver'),
	results,
    model = {
    "name": "Manufacturing Problem",
    "optimize": "profit",
    "opType": "max",
    "constraints": {
        "time": {
            "max": 8*60
        },
        "resources": {
            "max": 1800
        }
    },
    "variables": {
        "ma": {
            "resources": 20,
            "time": 4,
			"profit": 25
        },
        "mb": {
            "resources": 12,
            "time": 4,
			"profit": 20
        }
    },
};
console.log(solver.Solve(model));

Solution:

{ feasible: true, result: 2625, bounded: true, mb: 75, ma: 45 }

ExampleLP6: Manufacturing Problem
A factory manufactures three products, which require three resources – labor, materials and administration. The unit profits on these products are $10, $6 and $4 respectively. There are 100 hr of labor, 600 lb of material, and 300hr of administration available per day. In order to determine the optimal product mix, the following LP model is formulated and solve:

z3 code: Manufacturing Problem

var solver = require('javascript-lp-solver'),
	results,
    model = {
    "name": "Factory Problem",
    "optimize": "profit",
    "opType": "max",
    "constraints": {
        "labor": {
            "max": 100(h)
        },
        "material": {
            "max": 600(lb)
        },
		"administration": {
            "max": 300(h)
        }
    },
    "variables": {
        "a": {
            "labor": 1(h),
            "material": 10(lb),
			"administration": 2(h),
			"profit": 10(USD)
        },
        "b": {
            "labor": 1(h),
            "material": 4(lb),
			"administration": 2(h),
			"profit": 6(USD)
        },
		"c": {
            "labor": 1(h),
            "material": 5(lb),
			"administration": 6(h),
			"profit": 4(USD)
        }
    },
};
console.log(solver.Solve(model));

Solution:

{ feasible: true,
  result: 733.33333333,
  bounded: true,
  b: 66.66666667,
  a: 33.33333333 }

ExampleLP7: Mining Problem
The Metalco Company desires to blend a new alloy of 40% tin, 35% zinc, and 25% lead from several available alloys having the properties given in Table 1. Formulate a linear program whose solution would yield the proportions of these alloys that should be blended to produce a new alloy at minimum cost.

Spreadsheet
	Alloy1	Alloy2	Alloy3	Alloy4	Alloy5
%Tin	60	25	45	20	50
%Zinc	10	15	45	50	40
%Lead	30	60	10	30	10
Cost($lb.)	22	20	25	24	27

z3 code: Mining Problem

var solver = require('javascript-lp-solver'),
	results,
    model = {
    "name": "Mining Problem",
    "optimize": "Cost",
    "opType": "min",
    "constraints": {
        "Tin": {
            "min": 40
        },
        "Zinc": {
            "min": 35
        },
		"Lead": {
            "min": 25
        }
    },
    "variables": {
        "Alloy1": {
            "Tin": 60,
            "Zinc": 10,
			"Lead": 30,
			"Cost": 22
        },
        "Alloy2": {
            "Tin": 25,
            "Zinc": 15,
			"Lead": 60,
			"Cost": 20
        },
		"Alloy3": {
            "Tin": 45,
            "Zinc": 45,
			"Lead": 10,
			"Cost": 25
        },
		"Alloy4": {
            "Tin": 20,
            "Zinc": 50,
			"Lead": 30,
			"Cost": 24
        },
		"Alloy5": {
            "Tin": 50,
            "Zinc": 40,
			"Lead": 10,
			"Cost": 27
        }
    },
};
console.log(solver.Solve(model));

Solution:

{ feasible: true,
  result: 23.45652174,
  bounded: true,
  Alloy1: 0.04347826,
  Alloy3: 0.67391304,
  Alloy2: 0.2826087 }