Optimality Condition for Linear Programming Solutions

Click For Summary

Homework Help Overview

The discussion revolves around the optimality condition for linear programming solutions, specifically examining the criteria under which a feasible dictionary indicates an optimal solution. The original poster presents a statement regarding the conditions of the coefficients in relation to the objective function.

Discussion Character

  • Conceptual clarification, Assumption checking

Approaches and Questions Raised

  • The original poster attempts to prove or disprove the stated condition regarding the coefficients of the objective function. Some participants question the definitions of terms such as "feasible dictionary" and "z*," seeking clarification on their meanings and implications in the context of linear programming.

Discussion Status

The discussion is ongoing, with some participants providing clarifications on terminology and the original poster indicating they have found a counterexample. There is no explicit consensus on the proof or disproof of the original statement yet.

Contextual Notes

Participants are navigating definitions and concepts specific to linear programming, and there may be assumptions about prior knowledge of these terms that are being questioned.

Kalinka35
Messages
48
Reaction score
0

Homework Statement


A feasible dictionary whose last row reads z = z* + ∑ cjxjdescribes an optimal solution if and only if cj ≤ 0 for all j.
Prove or disprove.

Homework Equations


The Attempt at a Solution


It is clear that if all c's are ≤ 0, then the solution is optimal since increasing any of the variables would either lower or not affect the value of the objective function.
The opposite direction does not seem like it would be true, but I have no idea how to start proving that.
 
Physics news on Phys.org
What is a "feasible dictionary?" And what is z*?
 
A feasible dictionary shows the system of equations in the program with the basic variables on the left hand side and the non-basic variables on the right and it describes a feasible solution to the system.

z* is the constant from the objective equation when you set the non-basic variables equal to zero.

These are the terms that Chvatal uses.
 
Actually, I found a counterexample so I think I've got it.
 

Similar threads

  • · Replies 2 ·
Replies
2
Views
3K
  • · Replies 2 ·
Replies
2
Views
5K
  • · Replies 2 ·
Replies
2
Views
7K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 12 ·
Replies
12
Views
8K
  • · Replies 33 ·
2
Replies
33
Views
4K
Replies
1
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
5
Views
2K