线性优化 求助几道题 大家帮帮忙 每题1000GTB

000UID：111755

1
Optimal Solution
Consider the linear program:

Min
x + y

St
x + 2y = q

x, y > 0

a)
Find (with any method you’d like) an optimal solution to this problem as a function of q.

b)
Graph the optimal cost as a function of q.

c)
Construct the dual of this problem and identify its optimal solution as a function of q. How does this correspond to the graph in part b?






2
DualityConsider the following LP
Min a + b + c + d
St a + d = 3
b + d = 2
c + d = 0
a, b, c, d > 0

a) Write the dual of this problem.

b) Given the primal basis {a, b, c}, construct the corresponding primal and dual solutions.

c) What can you say about the optimality of this basis and its corresponding primal and dual solutions?




This solution is comprised of a detailed explanation to answer duality problem.



3


OptimizationSpecify whether the following statements are true or false and justify your answer.

a) Suppose we have an optimal basic feasible solution for an LP in standard form. If we increase the cost of a non-basic variable xn, the current solution will always remain optimal.

b) Suppose we have an optimal basic feasible solution for an LP in standard form. If we decrease the cost of a basic variable xb, the current solution will always remain optimal.

c) Suppose we have an optimal basic feasible solution for an LP in standard form. Further, suppose that this solution is both primal and dual non-degenerate. If we change the b vector, the current solution may remain feasible but become sub-optimal.



d) Consider a basic feasible solution to a linear program and suppose that the step size of the next pivot is 0. Does this mean that the current BFS is necessarily degenerate? Why or why not?

e)Consider a basic feasible solution to a linear program and suppose that it is degenerate. Does this mean that the next pivot will have step size of 0? Why or why not?

f)Consider a basic feasible solution to an LP in standard form. Suppose that two or more non-basic variables have negative reduced cost. Does this mean that the current solution is sub-optimal? Why or why not?

g)Suppose that we pivot in the non-basic variable with the most negative reduced cost and move to a new bfs with an improved objective value. Will this lead to the largest improvement in the objective value? Why or why not?




This solution is comprised of a detailed explanation to specify whether the following statements are true or false and justify your answer.



4
Big-M methodConsider the following algorithm for solving a linear program in standard form without having to use the Big-M method:
Choose any basis.
Check to see if this basis is primal feasible.
If so, use this as your initial BFS and solve the problem with simplex.
If the basis is primal infeasible, solve the problem using dual simplex

a) How would you find a basis to start this algorithm?

b) How would you check to see if this basis is primal feasible?

c) Do you think this algorithm will work? Why or why not?




This solution is comprised of a detailed explanation to answer
a) How would you find a basis to start this algorithm?

b) How would you check to see if this basis is primal feasible?

c) Do you think this algorithm will work? Why or why not?


5
Proof Optimal SolutionConsider a symmetric square matrix A and the following linear program:
Min cx
St Ax > c
x > 0
Prove that if x* satisfies Ax* = c and x* > 0 then x* is an optimal solution to this linear program.




This solution is comprised of a detailed explanation to prove that if x* satisfies Ax* = c and x* > 0 then x* is an optimal solution to this linear program.



6

Consider a feasible solution y to the linear program

Min
cx

St
Ax = b

x > 0
Let Z = {i | yi = 0}. Show that y is an optimal solution if and only if the following linear program has an optimal objective value of zero:

Min
cd

St
Ad = 0

di > 0 for all i in Z


Values are sought that allow for an optimal objective value of zero in this linear programming proof. The solution is detailed and well presented. The response was given a rating of "5/5" by the student who originally posted the question.



7

For a given basic feasible solution in a problem in standard form with no degenerate extreme points, what is the largest possible number of adjacent basic feasible solutions that it can have, as a function of n and m?

Give an example of when it will be strictly fewer than this number.


Cases for the largest possible adjacent basic feasible solutions are considered. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.

000UID：111755

大家谁学过就帮帮忙吧 估计要花些时间 帮我一部分也可以呀

我知道大家也不差GTB 我用马甲给 帮帮我吧 这是下次考试题目呀

000UID：111755

8 Linear Programming : Duality, Complementary Slackness, Dual Simplex Algorithm and Feasibility
Consider the linear program:
Min   -2x-y
St   x-y<2
     x+y<6
     x, y> 0
a) By inspection, argue that this problem cannot have an unbounded optimal solution.
b) Convert this problem to simplex standard form, enumerate all the basic solutions, identify which ones are feasible, and compute their objective values.
c) What is the optimal solution to this problem? How do you know?
d) What is the dual of this problem?
e) Use complementary slackness to prove your answer in part c.
f) For each basis in part b, use complementary slackness to find the corresponding basic solution to the dual problem, identify whether it's feasible, and compute its objective value.
g) Select a basis from part b which is primal infeasible but dual feasible. Using this as your initial solution, compute ONE pivot of the dual simplex algorithm. Is your new solution optimal? Why or why not?


Linear Programming, Duality, Complementary Slackness, Dual Simplex Algorithm and Feasibility are investigated. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.

ahleeUID：2188425

完全忘记了。。。。是在对不起。。。

nanyoUID：2313459

我只记得要画图，找最优点。。。

godspellUID：177241

恩，ls正解。。。可惜我学的是土木方向的。。。。

lostconchUID：2473832

做了一题，赚GTB~别的都好繁琐，不做了～～
注意theta用q代替了

1
Optimal Solution
Consider the linear program:

Min
x + y

St
x + 2y = q

x, y >= 0

a)
Find (with any method you’d like) an optimal solution to this problem as a function of .
x=0, y=q/2.

b)
Graph the optimal cost as a function of .
z=q/2.The Graph is obvious.

c)
Construct the dual of this problem and identify its optimal solution as a function of . How does this correspond to the graph in part b?
The dual of the problem is
Max
qx

St
2x<=1;
x<=1.

x is any real number

The optimal solution is x=1/2.
z=q/2.The two graph coincide.

000UID：111755

谢谢 https://bbs.gter.net/bbs/thread-1063548-1-1.html
7# lostconch