Introduction To The Mathematics Of Operations Research With Mathematica 1st Edition Kevin J Hastings - Solutions

After a delicious meal at the well-known French restaurant La Racine et Puissance Rationelle, critic Ivor Smallbrain notices that the bill comes to $x$ pounds, $y$ pence, where $x$ and $y$ are the smallest integers greater than 1 that satisfy the equation $y^{4 / 3}=x^{5 / 6}$.How much is
Express the decimal $1 . \overline{813}$ as a fraction $\frac{m}{n}$ (where $m$ and $n$ are integers).
Show that the decimal expression for $\sqrt{2}$ is not periodic.
Which of the following numbers are rational, and which are irrational? Express those which are rational in the form $\frac{m}{n}$ with $m, n \in \mathbb{Z}$.(a) $0 . a_{1} a_{2} a_{3} \ldots$, where for $n=1,2,3, \ldots$, the value of $a_{n}$ is the number $0,1,2,3$ or 4 which is the
The Fibonacci sequence starts with the terms 1,1 and then proceeds by letting the next term be the sum of the previous two terms. So the sequence starts $1,1,2,3,5,8,13,21,34, \ldots$. With this in mind, consider the decimal expansion of $x=\frac{100}{9899}$ : it is \(0.010102030508132134
Show that for an integer $n \geq 2$, the period of the decimal expression for the rational number $\frac{1}{n}$ is at most $n-1$.Find the first few values of $n$ for which the period of $\frac{1}{n}$ is equal to $n-1$. Do you notice anything interesting about the values you've found?
Critic Ivor Smallbrain is watching the classic film 11. $\overline{9}$ Angry Men. But he is bored, and starts wondering idly exactly which rational numbers $\frac{1}{n}$ have decimal expressions with period equal to 1 . Having done the previous question during the advertisments before the film,
(a) Prove that $\sqrt{3}$ is irrational. (b) Prove that there are no rationals $r, s$ such that $\sqrt{3}=r+s \sqrt{2}$.
Which of the following numbers are rational and which are irrational?(a) $\sqrt{2}+\sqrt{\frac{3}{2}}$.(b) $1+\sqrt{2}+\sqrt{\frac{3}{2}}$.(c) $2 \sqrt{18}-3 \sqrt{8}+\sqrt{4}$.(d) $\sqrt{2}+\sqrt{3}+\sqrt{5}$(e) $\sqrt{2}+\sqrt{3}-\sqrt{5+2 \sqrt{6}}$.
For each of the following statements, either prove it is true or give a counterexample to show it is false.(a) The product of two rational numbers is always rational.(b) The product of two irrational numbers is always irrational.(c) The product of two irrational numbers is always rational.(d) The
(a) Let $a, b$ be rationals and $x$ irrational. Show that if $\frac{x+a}{x+b}$ is rational, then $a=b$.(b) Let $x, y$ be rationals such that $\frac{x^{2}+x+\sqrt{2}}{y^{2}+y+\sqrt{2}}$ is also rational. Prove that either $x=y$ or $x+y=-1$.
Prove that if $n$ is any positive integer, then $\sqrt{n}+\sqrt{2}$ is irrational.
Find $n$, given that both $n$ and $\sqrt{n-2}+\sqrt{n+2}$ are positive integers.
Critic Ivor Smallbrain is watching the horror movie Salamanders on a Desert Island. In the film, there are 30 salamanders living on a desert island: 15 are red, 7 blue and 8 green. When two of a different colour meet, horrifyingly they both change into the third colour. (For example, if a red and a
A sheep farmer will blend three types of feed for his sheep, costing $\$ 1$ per pound, $\$ 2$ per pound, and $\$ 3$ per pound, respectively. Feed 1 consists of $50 \%$ fat and $50 \%$ protein, feed 2 is $25 \%$ fat and $75 \%$ protein, and feed 3 is $40 \%$ fat and $60 \%$
Solve the standard minimum problem: minimize: g=y + y2 y + 12 2 4 y + y2 8 subject to: yi + 4y = 8 V1, V2 0
Verify that constraints (1)-(2) are equivalent to (5).
A woman operating her own business is trying to plan her weekly sales activity schedule to produce the most valuable sales results in the least possible time. She can make personal visits, do phone calls, or work on mass mailings. She estimates that each hour spent on personal visits nets her \(\$
Suppose that in the final simplex system for a dual maximum problem of a given minimum problem, there is a degenerate basic slack variable $x_{j}$. In the equation to which $x_{j}$ belongs is some non-basic variable $x_{k}$ with a positive coefficient; and furthermore in the objective row,
Suppose that in the final simplex system for a dual maximum problem of a given minimum problem, there is a non-basic variable in the objective row with coefficient zero. Recall that this indicates the presence of an alternative optimal solution for the maximum problem. Show that if this variable is
Prove that if a standard maximum problem is unbounded, then its dual standard minimum problem is infeasible.
Solve the standard minimum problem below. minimize: g=2y+y2+3 y3 } + 32 + 10 subject to: yi - 1/2 + 6 y 15 V1, V2, V3 O
Give an economic interpretation of the dual maximum problem for the problem of Exercise 1.
Give an economic interpretation of the dual minimum problem for the problem of Exercise 7 of Section 2.3.
Let $\boldsymbol{A} \mathbf{x}=\mathbf{b}$ be the system of equality constraints for a standard maximum problem, after the introduction of slack variables. There are $n$ variables and $m$ constraints. A basic solution is a vector $\mathbf{x}$ that satisfies the equality constraints, and has
Use duality and two-dimensional geometry to solve the following problem without recourse to the simplex algorithm: minimize: y + 3y2 + 4 y3 -3+ y3 13 2 subject to: J1 - J2 -1 1, , 2, 0
We studied duality only in the context of standard maximum and minimum problems. The concept can be extended to arbitrary problems using the following correspondences:Notice that the first four correspondences are known to us already from our study of standard problems, and the last three show how
Referring to Exercise 14 (a) Write the general form of the dual of the problem:(c) For each of the problems in (a) and (b), show that the dual of the dual problem is the original (i.e., primal) problem. This illustrates again the paired nature of dual problems. minimize: subject to: g = b'.y A' y
Our proof of the Strong Duality Theorem, as well as the presentation of the tableau method in Section 3, depended on the fact that the dictionary and tableau methods were equivalent. More specifically, solving for an entering basic variable in a constraint equation, and then substituting the
Let $A$ be the set $\{\alpha,\{1, \alpha\},\{3\},\{\{1,3\}\}, 3\}$. Which of the following statements are true and which are false? () . (b) {a} A. (c) {1,} CA. (d) {3,{3}} CA. (e) {1,3} A. (f) {{1,3}} CA. (g) {{1,}} CA. (h) {1,} A. (i) .
Let $B, C, D, E$ be the following sets:\[ \begin{gathered} B=\left\{x \mid x \text { a real number, } x^{2}
Which of the following arguments are valid? For the valid ones, write down the argument symbolically.(a) I eat chocolate if I am depressed. I am not depressed. Therefore I am not eating chocolate.(b) I eat chocolate only if I am depressed. I am not depressed. Therefore I am not eating chocolate.(c)
$A$ and $B$ are two statements. Which of the following statements about $A$ and $B$ implies one or more of the other statements?(a) Either $A$ is true or $B$ is true.(b) $A \Rightarrow B$.(c) $B \Rightarrow A$.(d) $\bar{A} \Rightarrow B$.(e) $\bar{B} \Rightarrow A$.
Which of the following statements are true, and which are false? (a) n = 3 only if n-2n-3=0. (b) n 2n 3 0 only if n = 3. (c) If n 2n 3 = 0 then n = 3. (d) For integers a and b, ab is a square only if both a and b are squares. (e) For integers a and b, ab is a square if both a and b are squares.
Write down careful proofs of the following statements:(a) $\sqrt{6}-\sqrt{2}>1$.(b) If $n$ is an integer such that $n^{2}$ is even, then $n$ is even.(c) If $n=m^{3}-m$ for some integer $m$, then $n$ is a multiple of 6 .
Disprove the following statements:(a) If $n$ and $k$ are positive integers, then $n^{k}-n$ is always divisible by $k$.(b) Every positive integer is the sum of three squares (the squares being $0,1,4,9,16$, etc.).
Prove by contradiction that a real number that is less than every positive real number cannot be positive.
(a) Find $a_{1}$.(b) Find $a_{2}, a_{3}, \ldots, a_{9}$.(c) Find $a_{100}$.(d) Investigate the sequence $a_{1}, a_{2}, \ldots, a_{n}, \ldots$ further.
A small software production company wants to maximize the benefit of the time and money spent by its staff in working on development projects. It produces software that is roughly classified as one of three types, increasing in value and also difficulty from one type to the next. Type 1 projects
Verify that the list in formula (8) constitutes a basic feasible solution for the winery problem (3)-(4).
Solve the following standard maximum problem by the simplex algorithm: maximize: 2x1 x2 x3 + 4x4 - x1 + x2 3 subject to: x3 + X4 6 x + 2x2 + x3 + 2x4 10 x; 0 for all i
An enterprising farmer wants to devote some of his land to the raising of hogs, chickens, and ostriches. He will use no more than 1000 square yards for this purpose. After deducting the cost of feed, he decides that he can profit by $\$ 500$ per hog, $\$ 50$ per chicken, and $\$ 1000$ per
Solve the problem below. Show that the feasible region is unbounded. maximize: f = -2x1 + x2 + x3 -x1 + x2 + X3 2 subject to: X1 - X2 + X3 2 X1, X2, X3 0
Show that if there exists at least one constraint in the standard maximum problem, say the $i^{\text {th }}$, such that $a_{i j}$ is strictly greater than zero for all $j$, then the problem is bounded.
A construction contractor builds single-family dwellings and apartment buildings. The contractor can make $\$ 5000$ profit on each house and $\$ 50,000$ on each apartment. It takes 400 hours to build a house and 1000 hours to build an apartment. Each house requires 1600 cubic feet of concrete,
Show that the following linear program is unbounded, using the dictionary implementation of the simplex algorithm. maximize: x1 + x2 + X3 x1 + x2 - X3 4 subject to: 2x1 - x2 + X3 6 X1, X2, X3 0
Redo the winery problem (3)-(4) using the tableau implementation of the simplex algorithm. Note the connection between the tableau you obtain at each step, and the corresponding system of equations in Section 3.
Solve Exercise 1 using the tableau method.
(a) What would you look for in a simplex tableau in order to conclude that a problem is unbounded?(b) What would you look for in a simplex tableau in order to detect a degeneracy?(c) What characteristic of a final simplex tableau indicates multiple solutions?
You may have thought of trying the method of Lagrange multipliers to find optimal solutions, since, after the introduction of slack variables into the standard maximum problem, the problem has the form:(The trouble here lies in the fact that the slack variables do not appear in the objective
Consider the problem:(a) Sketch the feasible region, find the coordinates of the corner points, and find the optimal value.(b) Repeat (a) if the right-hand side constants are changed to $6+h_{1}$ and $4+h_{2}$, respectively. Under what conditions on $h_{1}$ and $h_{2}$ are $x_{1}$ and
Show that if there is a non-basic variable all of whose coefficients are non-negative at some stage of execution, then the problem is unbounded, as the message described above claims.
Show inductively that at each pass through the loop, the next system represents a basic feasible solution. Show in addition that if there are no degeneracies, the value of the objective increases strictly.
Prove that if no degeneracies are encountered at any stage, then the algorithm terminates in finitely many steps with with an unboundedness message or an optimal solution.
Consider a bounded standard maximum problem in two variables whose feasible region is of the form:where the constants $b_{i}$ are non-negative. Give a geometric argument that a feasible point can be written as the convex combination of at most three corner points. a11 x1 + 912x2 < b am1x1 am 2x2
(a) In Example 1, show that the line segment connecting $(1 / 2,0,1 / 2)$ and $(1 / 2,1 / 2,0)$ is entirely in the triangular region.(b) Is the point $(1 / 2,1 / 8,3 / 8)$ on this segment?(c) Under what conditions on $x_{2}$ and $x_{3}$ is the point ( $\left.1 / 2, x_{2}, x_{3}\right)$
(a) By using the definition of convexity only, and not Theorem 1, show that the set of points $\left(x_{1}, x_{2}, x_{3}\right)$ such that:is convex.(b) Show that the intersection of a finite number of convex sets, if nonempty, is convex. X1 + X2 + X3 1 2x1 + x2 + 2x3 5 X1, X2, X3 0 VIVIN
If $f$ is the objective of any feasible, bounded linear program with a given system of constraints, show that the optimal value of $f$ is taken on at the same point as the optimal value of $c \cdot f$, where $c$ is a positive constant.
A function $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ is called convex if for any $\mathbf{x}, \mathbf{y} \in \mathbb{R}^{n}$ and $t \in[0,1]$Show that a non-constant convex function defined on a bounded convex set cannot take on its maximum value in the interior of the convex set. f(tx (1)
Construct a counterexample to Theorem 2 part (a) if the set $S$ is not bounded.
Show that $(4 / 3,10 / 3,0,0)$ is a basic feasible solution of the system: 2x1 + x2 + X3 6 x1 + 2x2 X20 + X4 = 8 for all i
Express the constraints below in equality form by inserting slack variables, then find two basic feasible solutions and argue that they do satisfy the definition of basic feasible solution. x1 - X2 + X1 x1 + X2 X3 2 4 X1 + X3 6 X1, X2, X3 0
Prove that if a feasible solution to a maximum problem in equality form is locally optimal, then it is optimal. (A solution is locally optimal if its objective value exceeds those of all feasible points in some neighborhood of this solution.)
A town post office has $\$ 800,000$ available for the purchase of delivery vehicles. There are two models, a Jeep style and a van style, under consideration. Each Jeep costs $\$ 8000$ and each van costs $\$ 10,000$. Estimated annual maintenance costs per vehicle are $\$ 800$ and $\$ 600$,
Solve the LP problem:\[ \begin{aligned} & \text { minimize: } g=x_{1}+x_{2} \\ & 2 x_{1}+3 x_{2} \geq 6 \\ & \text { subject to: } \\ & 4 x_{1}+3 x_{2} \geq 12 \\ & 6 x_{1}+x_{2} \geq 6 \\ & x_{1}, \quad x_{2} \geq 0 \end{aligned} \]
Find the complete solution set of the problem:\[ \begin{aligned} & \text { maximize: } f=4000 x_{1}+4000 x_{2} \end{aligned} \]![](https://cdn.mathpix.com/cropped/2024_05_17_42952ac7174e082af32cg-14.jpg?height=196&width=465&top_left_y=1574&top_left_x=415)
In a psychology experiment on conditioning, an experimenter places mice and rats into two types of conditioning boxes, I and II. Each mouse spends 20 minutes per day and each rat spends 40 minutes per day in box I. Each mouse spends 40 minutes per day and each rat spends 20 minutes per day in box
Find the solution set of the problem: minimize: 2x1 + x2 X2 X1 + 2x2 2x2 subject to: 2.01 + x2 X1, X2 IV IV IV IA -1x1 +1 4 6 0
A hospital patient is required to have at least 90 units of drug I and 120 units of drug II. The drugs are both contained in two substances $S_{1}$ and $S_{2}$. Suppose that a gram of $S_{1}$ contains 6 units of drug I and 4 units of drug II, and a gram of $S_{2}$ contains 3 units of drug I
Find the optimal solution, if it exists, of the problem:\[ \begin{aligned} & \text { maximize: } f=x_{1}-x_{2} \\ & -x_{1}+2 x_{2} \leq 3 \\ & x_{1}+x_{2} \geq 1 \\ & \text { subject to: } x_{2}-x_{1} \leq 1 \\ & x_{1}-3 x_{2} \leq 1 \\ & x_{1}, \quad x_{2} \geq 0 \end{aligned} \]
(a) Given the feasible region below, find the associated set of constraints.(b) For what set of non-negative coefficients $c_{1}$ and $c_{2}$ will $(1,2)$ be the maximum point of the objective function $f=c_{1} x_{1}+c_{2} x_{2}$ ?(c) For what set of non-negative coefficients will the
For the feasible region of Exercise 8, express (a) the point $(3 / 2,1)$ and (b) the point $(1,1)$ as a convex combination of extreme points.
Repeat Exercise 8 (a) and (b) for the feasible region sketched above.
Repeat Exercise 9 for the feasible region of Exercise 10.
Introduce slack variables into the following constraints, and give the values of all variables at each vertex of the feasible region.\[ \begin{aligned} & x_{1}-x_{2} \leq 2 \\ & 2 x_{1}+x_{2} \leq 10 \\ & x_{1}+x_{2} \leq 8 \\ & x_{1}, \quad x_{2} \geq 0 \end{aligned} \]
Suppose that the objective function to be maximized is the piecewise linear function:\[ f= \begin{cases}2 x_{1}+x_{2} & \text { if } x_{1} \leq 1 / 2 \\ x_{1}+x_{2}+1 / 2 & \text { otherwise }\end{cases} \]Sketch the $c$-level sets carefully in order to maximize $f$ over the feasible region
Consider the feasible region of Exercise 8 and the objective function $f=3 x_{1}+2 x_{2}$. Beginning at a point $\left(x_{1}, x_{2}\right)$ in the feasible region, in what direction does $f$ increase most rapidly? If we begin at $(0,0)$ and move through the interior of the feasible region
Argue using combinatorics and mathematical induction that, under assumptions (a)-(c) listed at the start of the section, there are $n$ ! total possible complete matchings.
Verify that the matching in Figure 1.52 is maximal by computing the total weight of each possible matching.
Find an augmenting path for the matching below, and use it to produce a new matching with more edges. 1+ +6 2 7 +6 3 2. 8 4. 3- 9 .8 5. 4 10 +9 5. 10 Exercise 3 Exercise 4
Repeat Exercise 3 for the matching above.
Finish the proof of Theorem 1, i.e., show that $M^{\prime}$ is a matching.
Write your own versions of the Mathematica functions: (a) AugmentMatching; (b) ReviseLabeling; (c) EqualitySubgraph.
Let $G=(V, E)$ be a bipartite graph with sides $V_{1}$ and $V_{2}$, each of $n$ vertices. Show that if there is a complete matching of $V_{1}$ to $V_{2}$, then for every subset $S$ of $V_{1}$,\[ |S| \leq|A(S)| \]where $A(S)$ is the set of all vertices in $V_{2}$ adjacent to
Consider the weight matrix, displayed below, of a bipartite graph.(a) Compute the feasible labeling $L_{1}$ of formula (1), and sketch the equality subgraph of $L_{1}$.(b) If $S=\{1,3\}$ compute the feasible labeling $L_{2}$ defined by (3), and sketch its equality subgraph. 3I1O 22226 03532
Repeat Exercise 8, with the weight matrix above and $S=\{2,3,4\}$. This time, do the problem by hand, rather than in Mathematica.
Verify claims (4)-(7) about the change of labeling.
Show that the label changing algorithm must produce an equality subgraph that has a complete matching, by arguing as follows:(a) Upon changing labeling, since by claim (5) there is a new edge from $S$ to $T^{c}$, show that there will either be an augmenting path in the new equality subgraph, or
A dishonest politician has four candidates for four patronage jobs. Each candidate has agreed to bribe the politician to obtain each job, by amounts shown in the matrix below (units of thousands of dollars). Find two different ways of assigning the candidates to jobs, each of which maximizes the
A company is planning to locate five branches in five states. After studying various factors related to the local economies and tax laws of the states, the company has managed to quantify how beneficial each branch would be if located in each state. These ratings are in the matrix above. How should
Find a maximal matching for the graph of Exercise 8.
Find a maximal matching for the graph of Exercise 9.
A sales manager must assign each of eight salespeople to one of eight different regions. He has asked the salespeople to rate their choice of regions in order, with 8 representing their most preferred choice and 1 representing their least preferred. The results are shown in the matrix below, with
(a) Consider the directed network below, whose edge capacities are indicated. For each of the vertex sets $\{1,2\},\{1,2,3\}$, and $\{1,4\}$, list the edges in the cut corresponding to the set and compute the capacity of the cut.(b) Assume it is the case that the vertex set $\{1,2\}$
For the graph with flows as indicated, and $V_{0}=\{1,3,5\}$, check the veracity of the first assertion of Lemma 1.
Prove Lemma 2.
For the capacity graph of Figure 1.43, find the capacity of the cut corresponding to the vertex set $\{1,4,7\}$. Is this cut a minimum cut?
Paths (a) and (b) are each paths in some larger network. In each case, decide whether the path is an augmenting path, and if so, use the method suggested by (7)-(10) to augment the path. (a) Exercise 5 (b)
Check the constraint (a) of (1) for the augmented flow $f_{\epsilon}$, defined by (10).
Show that if, in the maximal flow algorithm, the breadth-first search cannot label the sink, then there is no augmenting path from source to sink. (Hint: Suppose that one did exist. Consider the first vertex without a label on this path.)

Showing 400 - 500 of 575

Introduction To The Mathematics Of Operations Research With Mathematica 1st Edition Kevin J Hastings - Solutions

Step by Step Answers