Please do #4 in Excel spreadsheet and explain how you did it on excel please. Th
ID: 3702786 • Letter: P
Question
Please do #4 in Excel spreadsheet and explain how you did it on excel please. Thank you. 4) Use the branch and bound algorithm for binary variables to create a search tree that finds the optimal solution to max 71-32-2x3 4-2xs subject to 4x1 22-322 3 z binary for j 1,2, .. 5 Use Excel to solve the LP-relaxations at each node, but only turn in the tree labelled with optimal z and x values and the steps at each level indicating active nodes and what branching. bounding, or fathoming is taking place.Explanation / Answer
Follow similar process: below is my own example
Max Z = 9x1+ 5x2+ 6x3+ 4x4Subject to:–6x1+ 3x2+ 5x3+ 2x4? 10–x3+ x4 ? 1–-x1+ x3? 0–-x2+ x4? 0–xi? 1, xi? 0, xiinteger•Dequeue{}
Max Z = 9x1+ 5x2+ 6x3+ 4x4Subject to:–6x1+ 3x2+ 5x3+ 2x4? 10–x3+ x4 ? 1–-x1+ x3? 0–-x2+ x4? 0–xi? 1, xi? 0, xiinteger•Bound {}1.Constrain xi by {}2.Relax to LP3.
Max Z = 9x1+ 5x2+ 6x3+ 4x4Subject to:–6x1+ 3x2+ 5x3+ 2x4? 10–x3+ x4 ? 1–-x1+ x3? 0–-x2+ x4? 0–xi? 1, xi? 0, xiinteger•Try to fathom:1.infeasible?2.worse than incumbent?3.integer solution?
Max Z = 9x1+ 5x2+ 6x3+ 4x4Subject to:–6x1+ 3x2+ 5x3+ 2x4? 10–x3+ x4 ? 1–-x1+ x3? 0–-x2+ x4? 0–xi? 1, xi? 0, xiinteger•Branch:1.select unassigned xi•pick non-integer (x1)2.Split on xi