Purchase Solution

Zero-One Programming Problem

Not what you're looking for?

Ask Custom Question

Problem 11-13

A group of college students is planning a camping trip during the upcoming break. The group must hike several miles through the woods to get to the campsite, and anything that is needed on this trip must be packed in a knapsack and carried to the campsite. One particular student, Tina Shawl, has identified eight items that she would like to take on the trip, but the combined weight is too great to take all of them. She has decided to rate the utility of each item on a scale of 1 to 100, with 100 being the most beneficial. The item weights in pounds and their utility values are given below.

Item 1 2 3 4 5 6 7 8
Weight 8 1 7 6 3 12 5 14
Utility 80 20 50 55 50 75 30 70

Recognizing that the hike to the campsite is a long one, a limit of 35 pounds has been set as the maximum total weight of the items to be carried.

(a) Formulate this as a 0-1 programming problem to maximize the total utility of the items carried. Solve this knapsack problem using a computer.
(b) Suppose item number 3 is an extra battery pack, which may be used with several of the other items. Tina has decided that she will only take item number 5, a CD player, if she also takes item number 3. On the other hand, if she takes item number 3, she may or may not take item number 5. Modify this problem to reflect this and solve the new problem.

Purchase this Solution
Solution Summary

This is an example for 0-1 programming problem. The problem is mathematically formulated and solved by using solver of M S Excel. Detailed description for the mathematical formulation and the procedure adopted for solving it by using computer is provided

Purchase this Solution
Free BrainMass Quizzes
Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

View More Free Quizzes
Related BrainMass Solutions

  • Some MCQs on Operations management

    Zero-one integer programming problem. D. Goal programming problem. 14. In a goal programming problem with two goals at the same priority level, all the deviational variables are equal to zero in the optimal solution.

  • zero one integre program / goal program - aerospace company

    Formulate the problem as a zero-one integer program with 8 decision variables and 5 constraints. Use the QM software (mixed integer programming) to solve. Set the variable type for each of the projects to "0/1".

  • Linear Programming tools

    negative, zero c. zero, zero d. zero, negative D 7. For a linear programming problem, assume that a given resource has not been fully used. In other words, the slack value associated with the resource constraint is positive.

  • Operations Management MCQs

    c. zero-one integer programming problems. d. goal programming problems. What is the total cost represented by the solution shown in Table 10-1?

  • Multiple choice questions on integer programming

    If we are solving a 0-1 integer programming problem, the constraint x1 + x2 = 1 is a mutually exclusive constraint. TRUE Only one of x1 and x2 can be 1 and only one of x1 and x2 can be zero.

  • Simplex Procedure and Graphing Linear Programming problems

    Degeneracy arises from solutions where one or more basic variables are zero, called degenerate solutions.

  • Game Theory : Two-Player Zero-Sum Game - Find Optimal Strategy

    You can find it in any textbook about Linear programming. In this solution the optimal strategy of a two player zero-sum game is found using linear programming methods.

  • Quantitative analysis:Constraints.

    TUTORIAL A binding constraint is a constraint for which at the optimal point, of a programming problem, has a slack value of zero.

  • Quantitative Methods Linear/Integer Programming

    A constraint for a linear programming problem can never have a zero as its right-hand-side value. _______14. Slack variables are only associated with maximization problems. _______15.

  • Some questions on LPP

    In maximization linear programming problem profit is maximized in the objective function by subtracting cost from revenue. TRUE/FALSE 19.

View More Related Solutions