「基礎OR」/「OR演習」 第2回 10/06/2009 森戸 晋.

Slides:



Advertisements
Similar presentations
Absolute Orientation. Absolute Orientation の問題 二つの座標系の間における剛体 (rigid body) 変換を復元す る問題である。 例えば: 2 台のステレオカメラから得られた3次元情報の間の関 係を推定する問題。 2 台のステレオカメラから得られた3次元情報の間の関.
Advertisements

<最適化の概念> 最適化すべき問 題 数学モデル 変数,数式 数理計画法 定められた計算手 順を用いて解くた めの方法論.
第6回 線形計画法の解法(4) 混合最小値問題 山梨大学.
線形計画 追加問題 ジュースを売って儲けよう!
ミクロ経済学第10回 企業と費用3:費用関数.
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
第八回  シンプレックス表の経済的解釈 山梨大学.
ゲーム理論・ゲーム理論Ⅰ (第8回) 第5章 不完全競争市場の応用
「基礎OR」/「OR演習」 第3回 宿題3.2 Red Brand Canners解説
© Yukiko Abe 2014 All rights reserved
初級ミクロ経済学 -生産者行動理論- 2014年10月20日 古川徹也 2014年10月20日 初級ミクロ経済学.
公共経営 「シミュレーション」 森戸担当分 第2回
「基礎OR」/「OR演習」 第1回 09/29/2009 森戸 晋.
第三回 線形計画法の解法(1) 標準最大値問題 山梨大学.
本時の目標 連立方程式の加減法のしかたを理解し、加減法を用いて連立方程式を解くことができる。
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
第四回 線形計画法(2) 混合最大値問題 山梨大学.
スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-
Extremal Combinatorics 14.1 ~ 14.2
土木計画学 第11回(12月21日) 土木計画と説明責任 計画における代替案の作成1 担当:榊原 弘之.
「基礎OR」/「OR演習」 第3回 10/13/2009 森戸 晋.
IT入門B2 ー 連立一次方程式 ー.
第二回 連立1次方程式の解法 内容 目標 連立1次方程式の掃出し法 初期基底を求める 連立1次方程式を掃出し法を用いてExcelで解析する
第3章 重回帰分析 ー 計量経済学 ー.
第3章 重回帰分析 ー 計量経済学 ー.
第 七 回 双対問題とその解法 山梨大学.
4.2 連立非線形方程式 (1)繰返し法による方法
1章前半.
第九回 問題の定式化練習と 自主研究課題 山梨大学.
方程式と不等式 1次方程式 1次不等式.
透視投影(中心射影)とは  ○ 3次元空間上の点を2次元平面へ投影する方法の一つ  ○ 投影方法   1.投影中心を定義する   2.投影平面を定義する
(ラプラス変換の復習) 教科書には相当する章はない
誤差の二乗和の一次導関数 偏微分.
Selfish Routing and the Price of Anarchy 第2回
Linear Relaxation for Hub Network Design Problems
© Yukiko Abe 2014 All rights reserved
© Yukiko Abe 2014 All rights reserved
第8章 気楽に「線形計画法」を覚えよう 1.最適化問題 経済行動:制約→最適化行動 最適化行動:売上高→最大化 生産費→最小化
情報学研究科 通信情報システム専攻 小野寺研究室 M1 奥村 佳弘
数学 ---> 抽象化、一般化 より複雑な関係ー>解析学 一次関数 y=ax+b より多くの要素ー>線形代数 x y f(x) y1 x1
経営システム工学入門実験 ロジスティクス 第3回
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
6. ラプラス変換.
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
人為変数や二段階を不要とする 実数型simplex法の解き方の 提案と検証
A First Course in Combinatorial Optimization Chapter
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
第4回 線形計画 2000年11月 第4回 線形計画.
公共経営研究科 「シミュレーション」森戸担当分 概要(12/02/05)
パターン認識特論 担当:和田 俊和 部屋 A513 主成分分析
プロセスデータ解析学5 -主成分分析- 担当:長谷部伸治     金 尚弘.
知識科学研究科 知識システム構築論講座 林研究室 佛明 智
第1回、平成22年6月30日 ー FEM解析のための連続体力学入門 - 応力とひずみ 解説者:園田 恵一郎.
4. システムの安定性.
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
逆運動学:手首自由度 運動学:速度、ャコビアン 2008.5.27
サポートベクターマシン Support Vector Machine SVM
行列式 方程式の解 Cramerの公式 余因数展開.
土木計画学 第12回(1月14日) 計画における代替案の作成2 担当:榊原 弘之.
人工知能特論II 第8回 二宮 崇.
経営システム工学入門実験 ロジスティクス 第3回
本時の目標 二元一次方程式とその解の意味を理解する。
行列 一次変換,とくに直交変換.
構造方程式ゼミナール 2012年11月14日-11月21日 構造方程式モデルの作成.
経営システム工学入門実験 ロジスティクス 第3回
ねらい いろいろな形の方程式を解くことを通して、方程式を解く手順を理解する。
割り当て問題(assignment problem)
東京工業大学情報理工学研究科 小島政和 第1回横幹連合コンファレンス 2005年11月25,26日 JA 長野県ビル
Presentation transcript:

「基礎OR」/「OR演習」 第2回 10/06/2009 森戸 晋

鉄鉱石配合問題の定式化 変数: Ti=配合1トン当たりの鉱山jの鉱石の重量 (≧0) 目的関数:最小化 トン当たりの費用 目的関数:最小化  トン当たりの費用 制約条件:各元素(A-C)の品質基準満足        配合の合計は1トン Min z=800T1+400T2+600T3+500T4 (費用) s.t. 10T1+ 3T2 + 8T3+ 2T4≧ 5 (元素A)   90T1+150T2+75T3+175T4≧100 (元素B) 45T1+ 25T2+20T3+ 37T4≧ 30 (元素C) T1+ T2+ T3+ T4= 1 (合計1)     T1,   T2, T3, T4 ≧ 0(非負条件)

被約費用(reduced cost) (EXCELでは)限界コスト 変数(列)に対応 二つの解釈が可能 ①xj=0である変数を無理に正にしようとしたときの、xj単位当たりの目的関数値の増加の度合い ②xj=0である変数を正にする可能性が生じる(つまり、最適解が最適でなくなる)目的関数の係数cjの変化量

潜在価格(shadow price) 双対価格(dual price) 制約条件式(行)に対応(別名: 単体乗数(simplex multiplier), 双対変数(dual variable)) 当該制約条件の右辺定数以外のすべての係数を元の問題のままにした上で、当該制約条件の右辺定数を微小量増加させたときの、増加単位量当たりの最適目的関数値の改善/改悪の度合い

農場経営問題のLP定式化 ①変数(variables) ②目的関数(objective function) ③制約条件(constraints) (決定)変数:wheat、alfalfa、beefの生産量          alfalfaの販売・購入量 目的関数:「収益ー費用」最大 制約条件:土地の許容上限        用水の許容上限 alfalfaのバランス     

農場経営問題 変数・目的関数 変数(variables):(単位の設定は一例) W=wheat raised and sold (acres) A=alfalfa raised (tons) B=beef raised and sold (tons) Ab=alfalfa bought (tons) As=alfalfa sold (tons) 目的関数(objective function): 最大化 72Wー30/3A+560Bー36Ab+34As

農場経営問題 制約条件 制約条件 土地 (単位acres) W+(1/3)A+0.05B≦1,200 農場経営問題 制約条件 制約条件 土地 (単位acres) W+(1/3)A+0.05B≦1,200 灌漑用水 (単位acre feet) 1.5W+(2.5/3)A+0.1B≦2,000 alfalfa (単位tons) Aー4B+AbーAs=0 非負条件  W, A, B, Ab, As ≧ 0

生産計画問題の定式化 線形計画問題 (決定)変数(決めること) 最大化 z =2 x1 + 3 x 2 (目的関数:利益) 製品1の生産量 x1    製品2の生産量 x2 最大化 z =2 x1 + 3 x 2 (目的関数:利益) 制約(条件) x1 + 2 x 2 ≦ 14 (鉄鋼) x1 + x 2 ≦ 8 (電力) 3 x1 + x 2 ≦ 18 (労働力) x1、x2≧0

生産計画問題の幾何的表現 x2 x1 0 z=一定

生産計画問題: スラック変数の導入 最大化 z =2 x1 + 3 x 2 (利益) 生産計画問題: スラック変数の導入 最大化 z =2 x1 + 3 x 2 (利益) 制約    x1 + 2 x 2 ≦ 14 (鉄鋼) x1 + x 2 ≦ 8 (電力) 3 x1 + x 2 ≦ 18 (労働力) x1、x2≧0 最大化 z =2 x1 + 3 x 2 (利益) 制約    x1 + 2 x 2+x3 = 14 (鉄)   x1 + x 2  +x4   = 8 (電) 3 x1 + x 2    +x5 =18 (労) x1、x2、x3、x4、x5≧0

生産計画: 連立方程式の非負解 z ー2 x1 ー 3 x 2 =0 (利益) 生産計画: 連立方程式の非負解 z ー2 x1 ー 3 x 2 =0 (利益)    x1 + 2 x 2+x3 = 14 (鉄) x1 + x 2   +x4   = 8 (電) 3 x1 + x 2     +x5 =18 (労) x1、x2、x3、x4、x5≧0 z ー2 x1 ー 3 x 2 =0 (利益)    x1 + 2 x 2+x3 = 14 (鉄) x1 + x 2   +x4   = 8 (電) 3 x1 + x 2     +x5 =18 (労) x1、x2、x3、x4、x5≧0 上の連立方程式からすぐに読み取れる解 x=(x1,x2,x3,x4,x5)=(0,0,14,8,18),z=0 実行可能解: 非負条件を満たす解 実行可能基底解: 「一切の計算なしに連立方程式から読み取れる実行可能解」

生産計画: 最適性の判定 z ー2 x1 ー 3 x 2 =0 (利益) 生産計画: 最適性の判定 z ー2 x1 ー 3 x 2 =0 (利益)    x1 + 2 x 2+x3 = 14 (鉄) x1 + x 2   +x4   = 8 (電) 3 x1 + x 2     +x5 =18 (労) x1=x2=0とすると、x=(0,0,14,8,18), z=0; この解は最適か? これ以外の解はx1,x2の少なくとも一方が正 一方を0に固定して他方を正にしよう; x1,x2のどっち?; そのとき解は改善するか? (選択された変数を)どこまで増やせるか?

生産計画: 連立方程式の等価変換1 z ー2 x1 ー 3 x 2 =0 (利益) 生産計画: 連立方程式の等価変換1 z ー2 x1 ー 3 x 2 =0 (利益)    x1 + 2 x 2+x3 = 14 (鉄) x1 + x 2   +x4   = 8 (電) 3 x1 + x 2     +x5 =18 (労) z ー2 x1 ー 3 x 2    =0 (利益)  (1/2)x1 +   x 2+(1/2)x3 = 7 (鉄) x1 + x 2     +x4   = 8 (電) 3 x1 + x 2       +x5 =18 (労)

生産計画: 連立方程式の等価変換2 z ー2 x1 ー 3 x 2 =0 (利益) 生産計画: 連立方程式の等価変換2 z ー2 x1 ー 3 x 2    =0 (利益)  (1/2)x1 +   x 2+(1/2)x3 = 7 (鉄) x1 + x 2     +x4   = 8 (電) 3 x1 + x 2       +x5 =18 (労)             x 2=7-(1/2)x1ー(1/2)x3 z ー2 x1 ー 3 x 2     =0 (利益)  (1/2)x1 +   x 2+(1/2)x3    = 7 (鉄) (1/2)x1      ー(1/2)x3 +x4   = 1 (電) 3 x1 + x 2        +x5 =18 (労)

生産計画: 連立方程式の等価変換3 z ー2 x1 ー 3 x 2 =0 (利益) 生産計画: 連立方程式の等価変換3 z ー2 x1 ー 3 x 2     =0 (利益)  (1/2)x1 +   x 2+(1/2)x3    = 7 (鉄) (1/2)x1      ー(1/2)x3 +x4   = 1 (電) 3 x1 + x 2        +x5 =18 (労)             x 2=7-(1/2)x1ー(1/2)x3 z ー2 x1 ー 3 x 2     =0 (利益)  (1/2)x1 +   x 2+(1/2)x3    = 7 (鉄) (1/2)x1      ー(1/2)x3 +x4   = 1 (電) (5/2) x1      ー(1/2)x3   +x5=11 (労)

生産計画: 連立方程式の等価変換4 z ー2 x1 ー 3 x 2 =0 (利益) 生産計画: 連立方程式の等価変換4 z ー2 x1 ー 3 x 2     =0 (利益)  (1/2)x1 +   x 2+(1/2)x3    = 7 (鉄) (1/2)x1      ー(1/2)x3 +x4   = 1 (電) (5/2) x1      ー(1/2)x3   +x5=11 (労)             x 2=7-(1/2)x1ー(1/2)x3 z ー (1/2)x1 +(3/2)x3    =21 (利益)    (1/2)x1 + x 2+(1/2)x3    = 7 (鉄)   (1/2)x1     ー(1/2)x3 +x4   = 1 (電) (5/2) x1    ー(1/2)x3   +x5=11 (労)  x=(x1,x2,x3,x4,x5)=(0,7,0,1,11),z=21

生産計画問題の幾何学的表現 労働力 z=一定 x2 鉄鋼 電力 0 x1

生産計画: 解の改善 z ー (1/2)x1 +(3/2)x3 =21 (利益) 生産計画: 解の改善 z ー (1/2)x1 +(3/2)x3    =21 (利益)    (1/2)x1 + x 2+(1/2)x3    = 7 (鉄)   (1/2)x1     ー(1/2)x3 +x4   = 1 (電) (5/2) x1    ー(1/2)x3   +x5=11 (労)  x=(x1,x2,x3,x4,x5)=(0,7,0,1,11),z=21 この実行可能基底解は最適か? x1=x3=0だと、この解しかない この解以外では、少なくともx1,x3の一方が正 x1,x3のどちらを0から増やす? どこまで増やせるか?

生産計画: 解の改善 z ー (1/2)x1 +(3/2)x3 =21 (利益) 生産計画: 解の改善 z ー (1/2)x1 +(3/2)x3    =21 (利益)    (1/2)x1 + x 2+(1/2)x3    = 7 (鉄)   (1/2)x1     ー(1/2)x3 +x4   = 1 (電) (5/2) x1    ー(1/2)x3   +x5=11 (労) 14  2 22/5 (x3を0に固定して)x1をどこまで増やせるか? z ー (1/2)x1 +(3/2)x3    =21 (利益)    (1/2)x1 + x 2+(1/2)x3    = 7 (鉄)   x1     ー x3 +2x4 = 2 (電) (5/2) x1    ー(1/2)x3   +x5=11 (労)         x1 = 2 + x3 ー2x4

生産計画問題の幾何学的表現 労働力 z=一定 x2 鉄鋼 電力 0 x1

生産計画: 最適解 z ー (1/2)x1 +(3/2)x3 =21 (利益) 生産計画: 最適解 z ー (1/2)x1 +(3/2)x3    =21 (利益)    (1/2)x1 + x 2+(1/2)x3    = 7 (鉄)   x1     ー x3 +2x4 = 2 (電) (5/2) x1    ー(1/2)x3   +x5=11 (労) 14  2 22/5 z               +x3+ x4 =22 (利益) x 2 +x3 ー x4 = 6 (鉄) x1       ― x3 +2x4 = 2 (電)     2x3 ー5 x4 +x5=11 (労)

単体表 No.0 z ー2 x1 ー 3 x 2 =0 (利益)    x1 + 2 x 2+x3 = 14 (鉄) x1 + x 2   +x4   = 8 (電) 3 x1 + x 2     +x5 =18 (労) 軸の列 0  1 軸の行 軸

等価変換=軸演算(掃き出し演算) 目標: 軸の列を、軸の要素を1とする単位ベクトルにする 新(軸の行) ← 旧(軸の行)÷軸の要素 目標: 軸の列を、軸の要素を1とする単位ベクトルにする 新(軸の行) ← 旧(軸の行)÷軸の要素 新(軸以外の行) ←      旧(軸以外の行)+定数*軸の行

単体表 No.1 z ー (1/2)x1 +(3/2)x3 =21 (利益) z ー (1/2)x1 +(3/2)x3    =21 (利益)    (1/2)x1 + x 2+(1/2)x3    = 7 (鉄)   (1/2)x1     ー(1/2)x3 +x4   = 1 (電) (5/2) x1    ー(1/2)x3   +x5=11 (労)

単体表 No.2 最適解

基底解(Basic Solution) 基底解 = m(3)本の制約条件(非負条件を除く)、n (5)個の変数(スラック変数を含む)からなる連立方程式の解で、適当なn-m (2)個の変数を0に固定し、残りのm (3)個の変数で連立方程式を解いて得られた解  (緑は生産計画問題の場合) 問題の制約条件がすべて不等式制約の場合、不等式制約や非負制約を定める直線・平面等の交点として定まる点(「生産計画問題」の場合全部で10個)が、幾何学的には基底解に対応 基底解の中には、値が負となる変数が出て、制約条件を満足しない実行不可能基底解も存在

基底変数(basic variable) 非基底変数(non-basic variable) 非基底変数=値を0に固定する変数(n -m個) ただし、mは制約条件(非負条件を除く)の数、nは変数の数 基底変数=非基底変数を0に固定することによって、値が決ってしまう変数(m個;ただし、目的関数値を示す変数も基底変数の1つと数える場合はm+1個)

可能基底解と可能基底形式 (basic feasible solution; b.f.s.) 可能基底解=非負条件を満足する基底解、すなわち、実行可能な基底解; 実行可能領域の端点(または頂点)に対応 可能基底形式=一切の計算をせずに可能基底解が読み取れる形で表示された連立方程式 可能基底形式(単体表)は、以下の条件を満たす:   1)基底変数に対応する列は単位ベクトル   2)基底変数の目的関数の係数は0   3)右辺定数は非負

単体法の基本手順 ステップ0 初期可能基底解を見つけ、ステップ1へ。 ステップ0 初期可能基底解を見つけ、ステップ1へ。 ステップ1 可能基底解は最適か?(最適性の判定)最適でなければ、ステップ2へ。(新たに基底変数となる変数の決定;軸の列の決定) ステップ2 基底から追い出される変数の決定(=軸の行の決定)と無限解(unbounded solution)の存在判定を行い、無限解でなければステップ3へ。 ステップ3 可能基底解を更新(軸演算、掃き出し演算)し、ステップ1へ。

軸演算(掃き出し演算):計算 「軸の列」に関しては、軸の要素を1とする単位ベクトルになるような等価変換を行いたい 等価変換で許される演算は、以下の2種類:  (a)軸の行に関しては、行を軸要素の値で割る  (b)軸の行以外の行に関しては、当該行から軸の行の定数倍を引いたり、当該行に軸の行の定数倍を加える

単体法計算のチェックリスト 右辺定数(目的関数値を除く)が非負か? (右辺定数が負はおかしい) 単位行列が隠れている 目的関数値が改善されている 基底変数の値が0の行が軸の行に選ばれなければ,すなわち,基底解が「退化」(後で解説予定)していなければ,目的関数値は単調に改善していくはず)

単体法の幾何的解釈 実行可能領域 = 凸多面体(Convex Polytope) x2 x1 0 z=一定 単体法の幾何的解釈 実行可能領域 =   凸多面体(Convex Polytope) 実行可能領域の端点(または頂点)   → 実行可能基底解(bfs)に対応 実行可能領域の端点のいずれかに線形計画問題の最適解が存在 単体法(Simplex Algorithm) =  実行可能領域の隣接する端点を   改善方向に動いていく

線形計画問題の可能領域 LPの実行可能領域=  凸多面体(有界なとき)  凸集合 端点⇒可能基底解に対応 実行不可能基底解

初期単体表が作れないとき どうすればよいか? Key Words: 二段階単体法、PhaseⅠ、人工変数

初期可能基底解が自明な場合 最大化 z=-3x1 +x3 制約 x1+x2+x3+x4≦4 ー2x1+x2-x3 ≦1 最大化 z=-3x1 +x3 制約  x1+x2+x3+x4≦4    ー2x1+x2-x3    ≦1 3x2+x3+x4≦9      xj ≧0(j=1,2,3,4) 1)各制約式に非負スラック変数を入れて等式化 たとえば、xj ≧0(j=5,6,7) 2)スラック変数を初期基底変数として初期単体表(=初期可能基底解)を作成

初期可能基底解が自明でない問題の解き方 最大化 z=-3x1 +x3 制約 x1+x2+x3+x4=4 ー2x1+x2-x3 =1 最大化 z=-3x1 +x3 制約  x1+x2+x3+x4=4    ー2x1+x2-x3    =1 3x2+x3+x4=9      xj ≧0(j=1,2,3,4)

非負人工変数 (Artificial Variables)の導入 最小化 z1=x5 +x6 +x7(人工変数の総和) 制約  x1+x2+x3+x4 +x5 =4    ー2x1+x2-x3    +x6 =1 3x2+x3+x4 +x7=9      xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0

第1段階(Phase I) 線形計画問題の実行可能性の判定 z1 ーx5ーx6ーx7 =0(人工変数総和)  x1+x2+x3+x4 +x5 =4 ー2x1+x2-x3    +x6 =1 3x2+x3+x4 +x7 =9      xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0

第1段階(Phase I) 「単体表」への等価変換 基底変数 z1 ーx1+5x2+x3+2x4      =14 z1      x1+x2+x3+x4 +x5 =4 x5    ー2x1+x2-x3    +x6 =1 x6 3x2+x3+x4 +x7=9 x7      xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0

第1段階(Phase I) 単体法の計算(1) ↓ 基底変数 z1 ーx1+5x2+x3+2x4 =14 z1 ↓ 基底変数 z1 ーx1+5x2+x3+2x4      =14 z1   x1+x2+x3+x4 +x5 =4 x5    ー2x1+x2-x3    +x6 =1 x6 ← 3x2+x3+x4 +x7=9 x7      xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0

PhaseⅠ成功(z1の最適値が0) → 元のLPが実行可能 元の問題の実行可能基底解が(原則として)求まる(どうやって?) 第1段階の線形計画問題の最適目的関数値(z1の最適値)が正ならば、元のLP問題は実行不可能

 所与のLPの実行可能性は、そのLPのPhase Ⅰ問題(これもまたLP)を解けば判定できる!

非負人工変数 (Artificial Variables)の導入 最小化 z1=x5 +x6 +x7(人工変数の総和) 最大化   z =-3x1 +x3 (元の目的関数) 制約  x1+x2+x3+x4 +x5 =4    ー2x1+x2-x3    +x6 =1 3x2+x3+x4 +x7=9      xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0

第1段階(Phase I) 線形計画問題の実行可能性の判定 z1 ーx5ーx6ーx7 =0(人工変数総和) z +3x1 ーx3 =0(元の目的関数)   x1+x2+x3+x4 +x5 =4    ー2x1+x2-x3    +x6 =1 3x2+x3+x4 +x7=9      xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0

z1 ーx5ーx6ーx7 =0(人工変数総和) z +3x1 ーx3 =0(元の目的関数)   x1+x2+x3+x4 +x5 =4    ー2x1+x2-x3    +x6 =1 3x2+x3+x4 +x7=9      xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0

基底変数 z1 ーx1+5x2+x3+2x4      =14 z1 z +3x1 ーx3 =0 z   x1+x2+x3+x4 +x5 =4 x5    ー2x1+x2-x3    +x6 =1 x6 3x2+x3+x4 +x7=9 x7      xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0

↓        基底変数 z1  + 9x1+  6x3+2x4  ー 5x6     =9  z1 z + 3x1 ーx3 =0 z  3x1+  2x3+ x4 +x5 ーx6 =3 x5    ー2x1+x2-x3    +x6 =1 x2     6x1+  4x3+ x4 ー 3x6 +x7=6 x7      xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0 まだ続く

 所与のLPの実行可能性は、そのLPのPhase Ⅰ問題(これもまたLP)を解けば判定できる!