最適化（線形計画法）

1. A. C++
2. B. Java
3. C. JavaScript
4. D. PHP
5. E. Ruby
6. F. Python
7. G. C#
8. H. VB

　　プログラムは，線形計画法に対するプログラム例です．実行に関しては，使用方法を参考にしてください．なお，このプログラムは，クラスを使用して記述しています（ JavaScript の場合はオブジェクトを使用）．

1. C++

   /****************************/
   /* 線形計画法               */
   /*      coded by Y.Suganuma */
   /****************************/
   #include <stdio.h>
   
   /*************/
   /* クラス LP */
   /*************/
   class LP
   {
   		int n;   // 制約条件の数
   		int m;   // 変数の数
   		int m_s;   // スラック変数の数
   		int m_a;   // 人為変数の数
   		int mm;   // m + m_s + m_a
   		int *a;   // 人為変数があるか否か
   		int *cp;   // 比較演算子（-1: 左辺 < 右辺, 0: 左辺 = 右辺, 1: 左辺 > 右辺）
   		int *row;   // 各行の基底変数の番号
   		double *z;   // 目的関数の係数
   		double **s;   // 単体表　
   		double eps;   // 許容誤差
   		int err;   // エラーコード （0:正常終了, 1:解無し）
   	public:
   		/******************************/
   		/* コンストラクタ             */
   		/*      n1 : 制約条件の数     */
   		/*      m1 : 変数の数         */
   		/*      z1 : 目的関数の係数   */
   		/*      eq_l : 制約条件の左辺 */
   		/*      eq_r : 制約条件の右辺 */
   		/*      cp1 : 比較演算子      */
   		/******************************/
   		LP(int n1, int m1, double *z1, double **eq_l, double *eq_r, int *cp1)
   		{
   			int i1, i2, k;
   					// 初期設定
   			eps = 1.0e-10;
   			err = 0;
   			n   = n1;
   			m   = m1;
   			a   = new int [n];
   			cp  = new int [n];
   			for (i1 = 0; i1 < n; i1++) {
   				a[i1]  = 0;
   				cp[i1] = cp1[i1];
   			}
   			z = new double [m];
   			for (i1 = 0; i1 < m; i1++)
   				z[i1] = z1[i1];
   					// スラック変数と人為変数の数を数える
   			m_s = 0;
   			m_a = 0;
   			for (i1 = 0; i1 < n; i1++) {
   				if (cp[i1] == 0) {
   					m_a++;
   					if (eq_r[i1] < 0.0) {
   						eq_r[i1] = -eq_r[i1];
   						for (i2 = 0; i2 < m; i2++)
   							eq_l[i1][i2] = -eq_l[i1][i2];
   					}
   				}
   				else {
   					m_s++;
   					if (eq_r[i1] < 0.0) {
   						cp[i1]   = -cp[i1];
   						eq_r[i1] = -eq_r[i1];
   						for (i2 = 0; i2 < m; i2++)
   							eq_l[i1][i2] = -eq_l[i1][i2];
   					}
   					if (cp[i1] > 0)
   						m_a++;
   				}
   			}
   					// 単体表の作成
   							// 初期設定
   			mm  = m + m_s + m_a;
   			row = new int [n];
   			s   = new double * [n+1];
   			for (i1 = 0; i1 <= n; i1++) {
   				s[i1] = new double [mm+1];
   				if (i1 < n) {
   					s[i1][0] = eq_r[i1];
   					for (i2 = 0; i2 < m; i2++)
   						s[i1][i2+1] = eq_l[i1][i2];
   					for (i2 = m+1; i2 <= mm; i2++)
   						s[i1][i2] = 0.0;
   				}
   				else {
   					for (i2 = 0; i2 <= mm; i2++)
   						s[i1][i2] = 0.0;
   				}
   			}
   							// スラック変数
   			k = m + 1;
   			for (i1 = 0; i1 < n; i1++) {
   				if (cp[i1] != 0) {
   					if (cp[i1] < 0) {
   						s[i1][k] = 1.0;
   						row[i1]  = k - 1;
   					}
   					else
   						s[i1][k] = -1.0;
   					k++;
   				}
   			}
   							// 人為変数
   			for (i1 = 0; i1 < n; i1++) {
   				if (cp[i1] >= 0) {
   					s[i1][k] = 1.0;
   					row[i1]  = k - 1;
   					a[i1]    = 1;
   					k++;
   				}
   			}
   							// 目的関数
   			if (m_a == 0) {
   				for (i1 = 0; i1 < m; i1++)
   					s[n][i1+1] = -z[i1];
   			}
   			else {
   				for (i1 = 0; i1 <= m+m_s; i1++) {
   					for (i2 = 0; i2 < n; i2++) {
   						if (a[i2] > 0)
   							s[n][i1] -= s[i2][i1];
   					}
   				}
   			}
   		}
   
   		/*******************************/
   		/* 最適化                      */
   		/*      sw : =0 : 中間結果無し */
   		/*           =1 : 中間結果あり */
   		/*      return : =0 : 正常終了 */
   		/*             : =1 : 解無し   */
   		/*******************************/
   		int optimize(int sw)
   		{
   			int i1, i2, k;
   					// フェーズ１
   			if (sw > 0) {
   				if (m_a > 0)
   					printf("\nphase 1\n");
   				else
   					printf("\nphase 2\n");
   			}
   			opt_run(sw);
   					// フェーズ２
   			if (err == 0 && m_a > 0) {
   							// 目的関数の変更
   				mm -= m_a;
   				for (i1 = 0; i1 <= mm; i1++)
   					s[n][i1] = 0.0;
   				for (i1 = 0; i1 < n; i1++) {
   					k = row[i1];
   					if (k < m)
   						s[n][0] += z[k] * s[i1][0];
   				}
   				for (i1 = 0; i1 < mm; i1++) {
   					for (i2 = 0; i2 < n; i2++) {
   						k = row[i2];
   						if (k < m)
   							s[n][i1+1] += z[k] * s[i2][i1+1];
   					}
   					if (i1 < m)
   						s[n][i1+1] -= z[i1];
   				}
   							// 最適化
   				if (sw > 0)
   					printf("\nphase 2\n");
   				opt_run(sw);
   			}
   
   			return err;
   		}
   
   		/*******************************/
   		/* 最適化（単体表の変形）      */
   		/*      sw : =0 : 中間結果無し */
   		/*           =1 : 中間結果あり */
   		/*******************************/
   		void opt_run(int sw)
   		{
   			int i1, i2, p, q, k;
   			double x, min;
   
   			err = -1;
   			while (err < 0) {
   					// 中間結果
   				if (sw > 0) {
   					printf("\n");
   					output();
   				}
   					// 列の選択（巡回を防ぐため必ずしも最小値を選択しない，Bland の規則）
   				q = -1;
   				for (i1 = 1; i1 <= mm && q < 0; i1++) {
   					if (s[n][i1] < -eps)
   						q = i1 - 1;
   				}
   					// 終了（最適解）
   				if (q < 0)
   					err = 0;
   					// 行の選択（ Bland の規則を採用）
   				else {
   					p   = -1;
   					k   = -1;
   					min = 0.0;
   					for (i1 = 0; i1 < n; i1++) {
   						if (s[i1][q+1] > eps) {
   							x = s[i1][0] / s[i1][q+1];
   							if (p < 0 || x < min || x == min && row[i1] < k) {
   								min = x;
   								p   = i1;
   								k   = row[i1];
   							}
   						}
   					}
   							// 解無し
   					if (p < 0)
   						err = 1;
   							// 変形
   					else {
   						x      = s[p][q+1];
   						row[p] = q;
   						for (i1 = 0; i1 <= mm; i1++)
   							s[p][i1] /= x;
   						for (i1 = 0; i1 <= n; i1++) {
   							if (i1 != p) {
   								x = s[i1][q+1];
   								for (i2 = 0; i2 <= mm; i2++)
   									s[i1][i2] -= x * s[p][i2];
   							}
   						}
   					}
   				}
   			}
   		}
   
   		/****************/
   		/* 単体表の出力 */
   		/****************/
   		void output()
   		{
   			int i1, i2;
   
   			for (i1 = 0; i1 <= n; i1++) {
   				if (i1 < n)
   					printf("x%d", row[i1]+1);
   				else
   					printf(" z");
   				for (i2 = 0; i2 <= mm; i2++)
   					printf(" %f", s[i1][i2]);
   				printf("\n");
   			}
   		}
   
   		/**************/
   		/* 結果の出力 */
   		/**************/
   		void result()
   		{
   			double x;
   			int i1, i2;
   
   			if (err > 0)
   				printf("\n解が存在しません\n");
   			else {
   				printf("\n(");
   				for (i1 = 0; i1 < m; i1++) {
   					x = 0.0;
   					for (i2 = 0; i2 < n; i2++) {
   						if (row[i2] == i1) {
   							x = s[i2][0];
   							break;
   						}
   					}
   					if (i1 == 0)
   						printf("%f", x);
   					else
   						printf(", %f", x);
   				}
   				printf(") のとき，最大値 %f\n", s[n][0]);
   			}
   		}
   };
   
   /****************/
   /* main program */
   /****************/
   int main()
   {
   	double **eq_l, *eq_r, *z;
   	int i1, i2, n, m, *cp, sw;
   	char c[2];
   					// 入力
   							// 変数の数と式の数
   	scanf("%d %d", &m, &n);
   	cp   = new int [n];
   	z    = new double [m];
   	eq_l = new double * [n];
   	eq_r = new double [n];
   	for (i1 = 0; i1 < n; i1++)
   		eq_l[i1] = new double [m];
   							// 目的関数の係数
   	for (i1 = 0; i1 < m; i1++)
   		scanf("%lf", &z[i1]);
   							// 制約条件
   	for (i1 = 0; i1 < n; i1++) {
   		for (i2 = 0; i2 < m; i2++)
   			scanf("%lf", &eq_l[i1][i2]);
   		scanf("%s", c);
   		if (c[0] == '<')
   			cp[i1] = -1;
   		else if (c[0] == '>')
   			cp[i1] = 1;
   		else
   			cp[i1] = 0;
   		scanf("%lf", &eq_r[i1]);
   	}
   					// 実行
   	LP lp = LP(n, m, z, eq_l, eq_r, cp);
   	sw = lp.optimize(1);
   					// 結果の出力
   	lp.result();
   
   	return 0;
   }
   			

2. Java

   /****************************/
   /* 線形計画法               */
   /*      coded by Y.Suganuma */
   /****************************/
   import java.io.*;
   import java.util.StringTokenizer;
   
   /*************/
   /* クラス LP */
   /*************/
   class LP
   {
   	private int n;   // 制約条件の数
   	private int m;   // 変数の数
   	private int m_s;   // スラック変数の数
   	private int m_a;   // 人為変数の数
   	private int mm;   // m + m_s + m_a
   	private int a[];   // 人為変数があるか否か
   	private int cp[];   // 比較演算子（-1:左辺<右辺, 0:左辺=右辺, 1:左辺>右辺）
   	private int row[];   // 各行の基底変数の番号
   	private double z[];   // 目的関数の係数
   	private double s[][];   // 単体表
   	private double eps;   // 許容誤差
   	private int err;   // エラーコード （0:正常終了, 1:解無し）
   
   	/******************************/
   	/* コンストラクタ             */
   	/*      n1 : 制約条件の数     */
   	/*      m1 : 変数の数         */
   	/*      z1 : 目的関数の係数   */
   	/*      eq_l : 制約条件の左辺 */
   	/*      eq_r : 制約条件の右辺 */
   	/*      cp1 : 比較演算子      */
   	/******************************/
   	LP(int n1, int m1, double z1[], double eq_l[][], double eq_r[], int cp1[])
   	{
   		int i1, i2, k;
   					// 初期設定
   		eps = 1.0e-10;
   		err = 0;
   		n   = n1;
   		m   = m1;
   		a   = new int [n];
   		cp  = new int [n];
   		for (i1 = 0; i1 < n; i1++) {
   			a[i1]  = 0;
   			cp[i1] = cp1[i1];
   		}
   		z = new double [m];
   		for (i1 = 0; i1 < m; i1++)
   			z[i1] = z1[i1];
   					// スラック変数と人為変数の数を数える
   		m_s = 0;
   		m_a = 0;
   		for (i1 = 0; i1 < n; i1++) {
   			if (cp[i1] == 0) {
   				m_a++;
   				if (eq_r[i1] < 0.0) {
   					eq_r[i1] = -eq_r[i1];
   					for (i2 = 0; i2 < m; i2++)
   						eq_l[i1][i2] = -eq_l[i1][i2];
   				}
   			}
   			else {
   				m_s++;
   				if (eq_r[i1] < 0.0) {
   					cp[i1]   = -cp[i1];
   					eq_r[i1] = -eq_r[i1];
   					for (i2 = 0; i2 < m; i2++)
   						eq_l[i1][i2] = -eq_l[i1][i2];
   				}
   				if (cp[i1] > 0)
   					m_a++;
   			}
   		}
   					// 単体表の作成
   							// 初期設定
   		mm  = m + m_s + m_a;
   		row = new int [n];
   		s   = new double [n+1][mm+1];
   		for (i1 = 0; i1 <= n; i1++) {
   			if (i1 < n) {
   				s[i1][0] = eq_r[i1];
   				for (i2 = 0; i2 < m; i2++)
   					s[i1][i2+1] = eq_l[i1][i2];
   				for (i2 = m+1; i2 <= mm; i2++)
   					s[i1][i2] = 0.0;
   			}
   			else {
   				for (i2 = 0; i2 <= mm; i2++)
   					s[i1][i2] = 0.0;
   			}
   		}
   							// スラック変数
   		k = m + 1;
   		for (i1 = 0; i1 < n; i1++) {
   			if (cp[i1] != 0) {
   				if (cp[i1] < 0) {
   					s[i1][k] = 1.0;
   					row[i1]  = k - 1;
   				}
   				else
   					s[i1][k] = -1.0;
   				k++;
   			}
   		}
   							// 人為変数
   		for (i1 = 0; i1 < n; i1++) {
   			if (cp[i1] >= 0) {
   				s[i1][k] = 1.0;
   				row[i1]  = k - 1;
   				a[i1]    = 1;
   				k++;
   			}
   		}
   							// 目的関数
   		if (m_a == 0) {
   			for (i1 = 0; i1 < m; i1++)
   				s[n][i1+1] = -z[i1];
   		}
   		else {
   			for (i1 = 0; i1 <= m+m_s; i1++) {
   				for (i2 = 0; i2 < n; i2++) {
   					if (a[i2] > 0)
   						s[n][i1] -= s[i2][i1];
   				}
   			}
   		}
   	}
   
   	/*******************************/
   	/* 最適化                      */
   	/*      sw : =0 : 中間結果無し */
   	/*           =1 : 中間結果あり */
   	/*      return : =0 : 正常終了 */
   	/*             : =1 : 解無し   */
   	/*******************************/
   	int optimize(int sw)
   	{
   		int i1, i2, k;
   					// フェーズ１
   		if (sw > 0) {
   			if (m_a > 0)
   				System.out.printf("\nphase 1\n");
   			else
   				System.out.printf("\nphase 2\n");
   		}
   		opt_run(sw);
   					// フェーズ２
   		if (err == 0 && m_a > 0) {
   							// 目的関数の変更
   			mm -= m_a;
   			for (i1 = 0; i1 <= mm; i1++)
   				s[n][i1] = 0.0;
   			for (i1 = 0; i1 < n; i1++) {
   				k = row[i1];
   				if (k < m)
   					s[n][0] += z[k] * s[i1][0];
   			}
   			for (i1 = 0; i1 < mm; i1++) {
   				for (i2 = 0; i2 < n; i2++) {
   					k = row[i2];
   					if (k < m)
   						s[n][i1+1] += z[k] * s[i2][i1+1];
   				}
   				if (i1 < m)
   					s[n][i1+1] -= z[i1];
   			}
   							// 最適化
   			if (sw > 0)
   				System.out.printf("\nphase 2\n");
   			opt_run(sw);
   		}
   
   		return err;
   	}
   
   	/*******************************/
   	/* 最適化（単体表の変形）      */
   	/*      sw : =0 : 中間結果無し */
   	/*           =1 : 中間結果あり */
   	/*******************************/
   	void opt_run(int sw)
   	{
   		int i1, i2, p, q, k;
   		double x, min;
   
   		err = -1;
   		while (err < 0) {
   					// 中間結果
   			if (sw > 0) {
   				System.out.printf("\n");
   				output();
   			}
   					// 列の選択（巡回を防ぐため必ずしも最小値を選択しない，Bland の規則）
   			q = -1;
   			for (i1 = 1; i1 <= mm && q < 0; i1++) {
   				if (s[n][i1] < -eps)
   					q = i1 - 1;
   			}
   					// 終了（最適解）
   			if (q < 0)
   				err = 0;
   					// 行の選択（ Bland の規則を採用）
   			else {
   				p   = -1;
   				k   = -1;
   				min = 0.0;
   				for (i1 = 0; i1 < n; i1++) {
   					if (s[i1][q+1] > eps) {
   						x = s[i1][0] / s[i1][q+1];
   						if (p < 0 || x < min || x == min && row[i1] < k) {
   							min = x;
   							p   = i1;
   							k   = row[i1];
   						}
   					}
   				}
   							// 解無し
   				if (p < 0)
   					err = 1;
   							// 変形
   				else {
   					x      = s[p][q+1];
   					row[p] = q;
   					for (i1 = 0; i1 <= mm; i1++)
   						s[p][i1] /= x;
   					for (i1 = 0; i1 <= n; i1++) {
   						if (i1 != p) {
   							x = s[i1][q+1];
   							for (i2 = 0; i2 <= mm; i2++)
   								s[i1][i2] -= x * s[p][i2];
   						}
   					}
   				}
   			}
   		}
   	}
   
   	/****************/
   	/* 単体表の出力 */
   	/****************/
   	void output()
   	{
   		int i1, i2;
   
   		for (i1 = 0; i1 <= n; i1++) {
   			if (i1 < n)
   				System.out.printf("x%d", row[i1]+1);
   			else
   				System.out.printf(" z");
   			for (i2 = 0; i2 <= mm; i2++)
   				System.out.printf(" %f", s[i1][i2]);
   			System.out.printf("\n");
   		}
   	}
   
   	/**************/
   	/* 結果の出力 */
   	/**************/
   	void result()
   	{
   		double x;
   		int i1, i2;
   
   		if (err > 0)
   			System.out.printf("\n解が存在しません\n");
   		else {
   			System.out.printf("\n(");
   			for (i1 = 0; i1 < m; i1++) {
   				x = 0.0;
   				for (i2 = 0; i2 < n; i2++) {
   					if (row[i2] == i1) {
   						x = s[i2][0];
   						break;
   					}
   				}
   				if (i1 == 0)
   					System.out.printf("%f", x);
   				else
   					System.out.printf(", %f", x);
   			}
   			System.out.printf(") のとき，最大値 %f\n", s[n][0]);
   		}
   	}
   }
   
   /****************/
   /* main program */
   /****************/
   public class Test
   {
   	public static void main (String[] args) throws IOException
   	{
   		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   		double eq_l[][], eq_r[], z[];
   		int i1, i2, n, m, cp[], sw;
   		String c;
   		StringTokenizer str;
   					// 入力
   							// 変数の数と式の数
   		str  = new StringTokenizer(in.readLine(), " ");
   		m    = Integer.parseInt(str.nextToken());
   		n    = Integer.parseInt(str.nextToken());
   		cp   = new int [n];
   		z    = new double [m];
   		eq_l = new double [n][m];
   		eq_r = new double [n];
   							// 目的関数の係数
   		str = new StringTokenizer(in.readLine(), " ");
   		for (i1 = 0; i1 < m; i1++)
   			z[i1] = Double.parseDouble(str.nextToken());
   							// 制約条件
   		for (i1 = 0; i1 < n; i1++) {
   			str = new StringTokenizer(in.readLine(), " ");
   			for (i2 = 0; i2 < m; i2++)
   				eq_l[i1][i2] = Double.parseDouble(str.nextToken());
   			c = str.nextToken();
   			if (c.compareTo("<") == 0)
   				cp[i1] = -1;
   			else if (c.compareTo(">") == 0)
   				cp[i1] = 1;
   			else
   				cp[i1] = 0;
   			eq_r[i1] = Double.parseDouble(str.nextToken());
   		}
   					// 実行
   		LP lp = new LP(n, m, z, eq_l, eq_r, cp);
   		sw    = lp.optimize(1);
   					// 結果の出力
   		lp.result();
   	}
   }
   			

3. JavaScript
   　　ここをクリックすると，任意のデータに対して，画面上で解を得ることができます．

   <!DOCTYPE HTML>
   
   <HTML>
   
   <HEAD>
   
   	<TITLE>最適化（線形計画法）</TITLE>
   	<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8">
   	<SCRIPT TYPE="text/javascript">
   		lp = null;   // オブジェクト LP
   
   		/****************/
   		/* main program */
   		/****************/
   		function main()
   		{
   					// 入力
   							// 変数の数と式の数
   			let m    = parseInt(document.getElementById("order").value);
   			let n    = parseInt(document.getElementById("cond").value);
   			let cp   = new Array(n);
   			let z    = new Array(m);
   			let eq_l = new Array(n);
   			for (let i1 = 0; i1 < n; i1++)
   				eq_l[i1] = new Array(m);
   			let eq_r = new Array(n);
   							// 目的関数の係数
   			let s1   = (document.getElementById("data").value).split("\n");
   			let s2   = s1[0].split(" ");
   			for (let i1 = 0; i1 < m; i1++)
   				z[i1] = parseFloat(s2[i1]);
   							// 制約条件
   			for (let i1 = 0; i1 < n; i1++) {
   				s2 = s1[i1+1].split(" ");
   				for (let i2 = 0; i2 < m; i2++)
   					eq_l[i1][i2] = parseFloat(s2[i2]);
   				c = s2[m];
   				if (c == "<")
   					cp[i1] = -1;
   				else if (c == ">")
   					cp[i1] = 1;
   				else
   					cp[i1] = 0;
   				eq_r[i1] = parseFloat(s2[m+1]);
   			}
   					// 実行
   			lp = new LP(n, m, z, eq_l, eq_r, cp);
   			sw = lp.optimize(1);
   					// 結果の出力
   			lp.result();
   			document.getElementById("ans").value = lp.str;
   		}
   
   		/******************************/
   		/* オブジェクト LP            */
   		/*      n1 : 制約条件の数     */
   		/*      m1 : 変数の数         */
   		/*      z1 : 目的関数の係数   */
   		/*      eq_l : 制約条件の左辺 */
   		/*      eq_r : 制約条件の右辺 */
   		/*      cp1 : 比較演算子      */
   		/******************************/
   		function LP(n1, m1, z1, eq_l, eq_r, cp1)
   		{
   					// 初期設定
   			this.str = "";   // 出力文字列
   			this.eps = 1.0e-10;   // 許容誤差
   			this.err = 0;   // エラーコード （0:正常終了, 1:解無し）
   			this.n   = n1;   // 制約条件の数
   			this.m   = m1;   // 変数の数
   			this.a   = new Array(this.n);   // 人為変数があるか否か
   			this.cp  = new Array(this.n);   // 比較演算子（-1: 左辺 < 右辺, 0:左辺 = 右辺, 1:左辺 > 右辺）
   			for (let i1 = 0; i1 < this.n; i1++) {
   				this.a[i1]  = 0;
   				this.cp[i1] = cp1[i1];
   			}
   			this.z = new Array(this.m);   // 目的関数の係数
   			for (let i1 = 0; i1 < this.m; i1++)
   				this.z[i1] = z1[i1];
   					// スラック変数と人為変数の数を数える
   			this.m_s = 0;   // スラック変数の数
   			this.m_a = 0;   // 人為変数の数
   			for (let i1 = 0; i1 < this.n; i1++) {
   				if (this.cp[i1] == 0) {
   					this.m_a++;
   					if (eq_r[i1] < 0.0) {
   						eq_r[i1] = -eq_r[i1];
   						for (let i2 = 0; i2 < this.m; i2++)
   							eq_l[i1][i2] = -eq_l[i1][i2];
   					}
   				}
   				else {
   					this.m_s++;
   					if (eq_r[i1] < 0.0) {
   						this.cp[i1]   = -this.cp[i1];
   						eq_r[i1]      = -eq_r[i1];
   						for (let i2 = 0; i2 < this.m; i2++)
   							eq_l[i1][i2] = -eq_l[i1][i2];
   					}
   					if (this.cp[i1] > 0)
   						this.m_a++;
   				}
   			}
   					// 単体表の作成
   							// 初期設定
   			this.mm  = this.m + this.m_s + this.m_a;   // m + m_s + m_a
   			this.row = new Array(this.n);   // 各行の基底変数の番号
   			this.s   = new Array(this.n+1);   // 単体表
   			for (let i1 = 0; i1 <= this.n; i1++) {
   				this.s[i1] = new Array(this.mm+1);
   				if (i1 < this.n) {
   					this.s[i1][0] = eq_r[i1];
   					for (let i2 = 0; i2 < this.m; i2++)
   						this.s[i1][i2+1] = eq_l[i1][i2];
   					for (let i2 = this.m+1; i2 <= this.mm; i2++)
   						this.s[i1][i2] = 0.0;
   				}
   				else {
   					for (let i2 = 0; i2 <= this.mm; i2++)
   						this.s[i1][i2] = 0.0;
   				}
   			}
   							// スラック変数
   			let k = this.m + 1;
   			for (let i1 = 0; i1 < this.n; i1++) {
   				if (this.cp[i1] != 0) {
   					if (this.cp[i1] < 0) {
   						this.s[i1][k] = 1.0;
   						this.row[i1]  = k - 1;
   					}
   					else
   						this.s[i1][k] = -1.0;
   					k++;
   				}
   			}
   							// 人為変数
   			for (let i1 = 0; i1 < this.n; i1++) {
   				if (this.cp[i1] >= 0) {
   					this.s[i1][k] = 1.0;
   					this.row[i1]  = k - 1;
   					this.a[i1]    = 1;
   					k++;
   				}
   			}
   							// 目的関数
   			if (this.m_a == 0) {
   				for (let i1 = 0; i1 < this.m; i1++)
   					this.s[this.n][i1+1] = -this.z[i1];
   			}
   			else {
   				for (let i1 = 0; i1 <= this.m+this.m_s; i1++) {
   					for (let i2 = 0; i2 < this.n; i2++) {
   						if (this.a[i2] > 0)
   							this.s[this.n][i1] -= this.s[i2][i1];
   					}
   				}
   			}
   		}
   
   	/*******************************/
   	/* 最適化                      */
   	/*      sw : =0 : 中間結果無し */
   	/*           =1 : 中間結果あり */
   	/*      return : =0 : 正常終了 */
   	/*             : =1 : 解無し   */
   	/*******************************/
   	LP.prototype.optimize = function(sw)
   	{
   					// フェーズ１
   		if (sw > 0) {
   			if (lp.m_a > 0)
   				lp.str += "\nphase 1\n";
   			else
   				lp.str += "\nphase 2\n";
   		}
   		lp.opt_run(sw);
   					// フェーズ２
   		if (lp.err == 0 && lp.m_a > 0) {
   							// 目的関数の変更
   			lp.mm -= lp.m_a;
   			for (let i1 = 0; i1 <= lp.mm; i1++)
   				lp.s[lp.n][i1] = 0.0;
   			for (let i1 = 0; i1 < lp.n; i1++) {
   				let k = lp.row[i1];
   				if (k < lp.m)
   					lp.s[lp.n][0] += lp.z[k] * lp.s[i1][0];
   			}
   			for (let i1 = 0; i1 < lp.mm; i1++) {
   				for (i2 = 0; i2 < lp.n; i2++) {
   					let k = lp.row[i2];
   					if (k < lp.m)
   						lp.s[lp.n][i1+1] += lp.z[k] * lp.s[i2][i1+1];
   				}
   				if (i1 < lp.m)
   					lp.s[lp.n][i1+1] -= lp.z[i1];
   			}
   							// 最適化
   			if (sw > 0)
   				lp.str += "\nphase 2\n";
   			lp.opt_run(sw);
   		}
   
   		return lp.err;
   	}
   
   	/*******************************/
   	/* 最適化（単体表の変形）      */
   	/*      sw : =0 : 中間結果無し */
   	/*           =1 : 中間結果あり */
   	/*******************************/
   	LP.prototype.opt_run = function(sw)
   	{
   		lp.err = -1;
   		while (lp.err < 0) {
   					// 中間結果
   			if (sw > 0) {
   				lp.str += "\n";
   				lp.output();
   			}
   					// 列の選択（巡回を防ぐため必ずしも最小値を選択しない，Bland の規則）
   			let q = -1;
   			for (let i1 = 1; i1 <= lp.mm && q < 0; i1++) {
   				if (lp.s[lp.n][i1] < -lp.eps)
   					q = i1 - 1;
   			}
   					// 終了（最適解）
   			if (q < 0)
   				lp.err = 0;
   					// 行の選択（ Bland の規則を採用）
   			else {
   				let p   = -1;
   				let k   = -1;
   				let min = 0.0;
   				for (let i1 = 0; i1 < lp.n; i1++) {
   					if (lp.s[i1][q+1] > lp.eps) {
   						let x = lp.s[i1][0] / lp.s[i1][q+1];
   						if (p < 0 || x < min || x == min && lp.row[i1] < k) {
   							min = x;
   							p   = i1;
   							k   = lp.row[i1];
   						}
   					}
   				}
   							// 解無し
   				if (p < 0)
   					lp.err = 1;
   							// 変形
   				else {
   					let x      = lp.s[p][q+1];
   					lp.row[p]  = q;
   					for (let i1 = 0; i1 <= lp.mm; i1++)
   						lp.s[p][i1] /= x;
   					for (let i1 = 0; i1 <= lp.n; i1++) {
   						if (i1 != p) {
   							x = lp.s[i1][q+1];
   							for (let i2 = 0; i2 <= lp.mm; i2++)
   								lp.s[i1][i2] -= x * lp.s[p][i2];
   						}
   					}
   				}
   			}
   		}
   	}
   
   	/****************/
   	/* 単体表の出力 */
   	/****************/
   	LP.prototype.output = function()
   	{
   		for (let i1 = 0; i1 <= lp.n; i1++) {
   			if (i1 < lp.n)
   				lp.str += ("x" + (lp.row[i1]+1));
   			else
   				lp.str += " z";
   			for (let i2 = 0; i2 <= lp.mm; i2++)
   				lp.str += (" " + lp.s[i1][i2]);
   			lp.str += "\n";
   		}
   	}
   
   	/**************/
   	/* 結果の出力 */
   	/**************/
   	LP.prototype.result = function()
   	{
   		if (lp.err > 0)
   			lp.str += "\n解が存在しません\n";
   		else {
   			lp.str += "\n(";
   			for (let i1 = 0; i1 < lp.m; i1++) {
   				let x = 0.0;
   				for (let i2 = 0; i2 < lp.n; i2++) {
   					if (lp.row[i2] == i1) {
   						x = lp.s[i2][0];
   						break;
   					}
   				}
   				if (i1 == 0)
   					lp.str += x;
   				else
   					lp.str += (", " + x);
   			}
   			lp.str += (") のとき，最大値 " + lp.s[lp.n][0] + "\n");
   		}
   	}
   	</SCRIPT>
   </HEAD>
   
   <BODY STYLE="font-size: 130%; background-color: #eeffee;">
   
   	<H2 STYLE="text-align:center"><B>最適化（線形計画法）</B></H2>
   
   	<DL>
   		<DT>　　テキストフィールドおよびテキストエリアには，例として，
   		<DD><DL>
   			<DT>目的関数，
   			<DD>z = 3x<SUB>1</SUB> + 2x<SUB>2</SUB>　　　(1)
   			<DT>を，制約条件，
   			<DD>3x<SUB>1</SUB> + x<SUB>2</SUB> ≦ 9　　　(2)
   			<DD>2.5x<SUB>1</SUB> + 2x<SUB>2</SUB> ≦ 12.5　　　(3)
   			<DD>x<SUB>1</SUB> + 2x<SUB>2</SUB> ≦ 8　　　(4)
   			<DD>x<SUB>1</SUB>， x<SUB>2</SUB> ≧ 0
   			<DT>のもとで，最大にする．
   		</DL></DD>
   		<DT>を実行するための値が設定されています．他の問題を実行する場合は，それらを適切に修正してください．
   	</DL>
   
   	<DIV STYLE="text-align:center">
   		変数の数：<INPUT ID="order" STYLE="font-size: 100%" TYPE="text" SIZE="3" VALUE="2"> 
   		制約条件数：<INPUT ID="cond" STYLE="font-size: 100%;" TYPE="text" SIZE="3" VALUE="3"> 
   		<BUTTON STYLE="font-size: 100%; background-color: pink" onClick="main()">OK</BUTTON><BR><BR>
   		入力データ：<TEXTAREA ID="data" COLS="30" ROWS="15" STYLE="font-size: 100%">
   3 2
   3 1 < 9
   2.5 2 < 12.5
   1 2 < 8</TEXTAREA><BR><BR>
   		<TEXTAREA ID="ans" COLS="60" ROWS="15" STYLE="font-size: 100%"></TEXTAREA>
   	</DIV>
   
   </BODY>
   
   </HTML>
   			

4. PHP

   <?php
   
   /****************************/
   /* 線形計画法               */
   /*      coded by Y.Suganuma */
   /****************************/
   #include 
   
   /*************/
   /* クラス LP */
   /*************/
   class LP
   {
   		private $n;   // 制約条件の数
   		private $m;   // 変数の数
   		private $m_s;   // スラック変数の数
   		private $m_a;   // 人為変数の数
   		private $mm;   // m + m_s + m_a
   		private $a = array();   // 人為変数があるか否か
   		private $cp = array();   // 比較演算子（-1: 左辺 < 右辺, 0: 左辺 = 右辺, 1: 左辺 > 右辺）
   		private $row = array();   // 各行の基底変数の番号
   		private $z = array();   // 目的関数の係数
   		private $s = array();   // 単体表
   		private $eps;   // 許容誤差
   		private $err;   // エラーコード （0:正常終了, 1:解無し）
   
   		/******************************/
   		/* コンストラクタ             */
   		/*      n1 : 制約条件の数     */
   		/*      m1 : 変数の数         */
   		/*      z1 : 目的関数の係数   */
   		/*      eq_l : 制約条件の左辺 */
   		/*      eq_r : 制約条件の右辺 */
   		/*      cp1 : 比較演算子      */
   		/******************************/
   		function LP($n1, $m1, $z1, $eq_l, $eq_r, $cp1)
   		{
   					// 初期設定
   			$this->eps = 1.0e-10;
   			$this->err = 0;
   			$this->n   = $n1;
   			$this->m   = $m1;
   			for ($i1 = 0; $i1 < $this->n; $i1++) {
   				$this->a[$i1]  = 0;
   				$this->cp[$i1] = $cp1[$i1];
   			}
   			for ($i1 = 0; $i1 < $this->m; $i1++)
   				$this->z[$i1] = $z1[$i1];
   					// スラック変数と人為変数の数を数える
   			$this->m_s = 0;
   			$this->m_a = 0;
   			for ($i1 = 0; $i1 < $this->n; $i1++) {
   				if ($this->cp[$i1] == 0) {
   					$this->m_a++;
   					if ($eq_r[$i1] < 0.0) {
   						$eq_r[$i1] = -$eq_r[$i1];
   						for ($i2 = 0; $i2 < $this->m; $i2++)
   							$eq_l[$i1][$i2] = -$eq_l[$i1][$i2];
   					}
   				}
   				else {
   					$this->m_s++;
   					if ($eq_r[$i1] < 0.0) {
   						$this->cp[$i1]   = -$this->cp[$i1];
   						$eq_r[$i1] = -$eq_r[$i1];
   						for ($i2 = 0; $i2 < $this->m; $i2++)
   							$eq_l[$i1][$i2] = -$eq_l[$i1][$i2];
   					}
   					if ($this->cp[$i1] > 0)
   						$this->m_a++;
   				}
   			}
   					// 単体表の作成
   							// 初期設定
   			$this->mm  = $this->m + $this->m_s + $this->m_a;
   			for ($i1 = 0; $i1 <= $this->n; $i1++) {
   				$this->s[$i1] = array($this->mm+1);
   				if ($i1 < $this->n) {
   					$this->s[$i1][0] = $eq_r[$i1];
   					for ($i2 = 0; $i2 < $this->m; $i2++)
   						$this->s[$i1][$i2+1] = $eq_l[$i1][$i2];
   					for ($i2 = $this->m+1; $i2 <= $this->mm; $i2++)
   						$this->s[$i1][$i2] = 0.0;
   				}
   				else {
   					for ($i2 = 0; $i2 <= $this->mm; $i2++)
   						$this->s[$i1][$i2] = 0.0;
   				}
   			}
   							// スラック変数
   			$k = $this->m + 1;
   			for ($i1 = 0; $i1 < $this->n; $i1++) {
   				if ($this->cp[$i1] != 0) {
   					if ($this->cp[$i1] < 0) {
   						$this->s[$i1][$k] = 1.0;
   						$this->row[$i1]  = $k - 1;
   					}
   					else
   						$this->s[$i1][$k] = -1.0;
   					$k++;
   				}
   			}
   							// 人為変数
   			for ($i1 = 0; $i1 < $this->n; $i1++) {
   				if ($this->cp[$i1] >= 0) {
   					$this->s[$i1][$k] = 1.0;
   					$this->row[$i1]  = $k - 1;
   					$this->a[$i1]    = 1;
   					$k++;
   				}
   			}
   							// 目的関数
   			if ($this->m_a == 0) {
   				for ($i1 = 0; $i1 < $this->m; $i1++)
   					$this->s[$this->n][$i1+1] = -$this->z[$i1];
   			}
   			else {
   				for ($i1 = 0; $i1 <= $this->m+$this->m_s; $i1++) {
   					for ($i2 = 0; $i2 < $this->n; $i2++) {
   						if ($this->a[$i2] > 0)
   							$this->s[$this->n][$i1] -= $this->s[$i2][$i1];
   					}
   				}
   			}
   		}
   
   		/*******************************/
   		/* 最適化                      */
   		/*      sw : =0 : 中間結果無し */
   		/*           =1 : 中間結果あり */
   		/*      return : =0 : 正常終了 */
   		/*             : =1 : 解無し   */
   		/*******************************/
   		function optimize($sw)
   		{
   					// フェーズ１
   			if ($sw > 0) {
   				if ($this->m_a > 0)
   					printf("\nphase 1\n");
   				else
   					printf("\nphase 2\n");
   			}
   			$this->opt_run($sw);
   					// フェーズ２
   			if ($this->err == 0 && $this->m_a > 0) {
   							// 目的関数の変更
   				$this->mm -= $this->m_a;
   				for ($i1 = 0; $i1 <= $this->mm; $i1++)
   					$this->s[$this->n][$i1] = 0.0;
   				for ($i1 = 0; $i1 < $this->n; $i1++) {
   					$k = $this->row[$i1];
   					if ($k < $this->m)
   						$this->s[$this->n][0] += $this->z[$k] * $this->s[$i1][0];
   				}
   				for ($i1 = 0; $i1 < $this->mm; $i1++) {
   					for ($i2 = 0; $i2 < $this->n; $i2++) {
   						$k = $this->row[$i2];
   						if ($k < $this->m)
   							$this->s[$this->n][$i1+1] += $this->z[$k] * $this->s[$i2][$i1+1];
   					}
   					if ($i1 < $this->m)
   						$this->s[$this->n][$i1+1] -= $this->z[$i1];
   				}
   							// 最適化
   				if ($sw > 0)
   					printf("\nphase 2\n");
   				$this->opt_run($sw);
   			}
   
   			return $this->err;
   		}
   
   		/*******************************/
   		/* 最適化（単体表の変形）      */
   		/*      sw : =0 : 中間結果無し */
   		/*           =1 : 中間結果あり */
   		/*******************************/
   		function opt_run($sw)
   		{
   			$this->err = -1;
   			while ($this->err < 0) {
   					// 中間結果
   				if ($sw > 0) {
   					printf("\n");
   					$this->output();
   				}
   					// 列の選択（巡回を防ぐため必ずしも最小値を選択しない，Bland の規則）
   				$q = -1;
   				for ($i1 = 1; $i1 <= $this->mm && $q < 0; $i1++) {
   					if ($this->s[$this->n][$i1] < -$this->eps)
   						$q = $i1 - 1;
   				}
   					// 終了（最適解）
   				if ($q < 0)
   					$this->err = 0;
   					// 行の選択（ Bland の規則を採用）
   				else {
   					$p   = -1;
   					$k   = -1;
   					$min = 0.0;
   					for ($i1 = 0; $i1 < $this->n; $i1++) {
   						if ($this->s[$i1][$q+1] > $this->eps) {
   							$x = $this->s[$i1][0] / $this->s[$i1][$q+1];
   							if ($p < 0 || $x < $min || $x == $min && $this->row[$i1] < $k) {
   								$min = $x;
   								$p   = $i1;
   								$k   = $this->row[$i1];
   							}
   						}
   					}
   							// 解無し
   					if ($p < 0)
   						$this->err = 1;
   							// 変形
   					else {
   						$x             = $this->s[$p][$q+1];
   						$this->row[$p] = $q;
   						for ($i1 = 0; $i1 <= $this->mm; $i1++)
   							$this->s[$p][$i1] /= $x;
   						for ($i1 = 0; $i1 <= $this->n; $i1++) {
   							if ($i1 != $p) {
   								$x = $this->s[$i1][$q+1];
   								for ($i2 = 0; $i2 <= $this->mm; $i2++)
   									$this->s[$i1][$i2] -= $x * $this->s[$p][$i2];
   							}
   						}
   					}
   				}
   			}
   		}
   
   		/****************/
   		/* 単体表の出力 */
   		/****************/
   		function output()
   		{
   			for ($i1 = 0; $i1 <= $this->n; $i1++) {
   				if ($i1 < $this->n)
   					printf("x%d", $this->row[$i1]+1);
   				else
   					printf(" z");
   				for ($i2 = 0; $i2 <= $this->mm; $i2++)
   					printf(" %f", $this->s[$i1][$i2]);
   				printf("\n");
   			}
   		}
   
   		/**************/
   		/* 結果の出力 */
   		/**************/
   		function result()
   		{
   			if ($this->err > 0)
   				printf("\n解が存在しません\n");
   			else {
   				printf("\n(");
   				for ($i1 = 0; $i1 < $this->m; $i1++) {
   					$x = 0.0;
   					for ($i2 = 0; $i2 < $this->n; $i2++) {
   						if ($this->row[$i2] == $i1) {
   							$x = $this->s[$i2][0];
   							break;
   						}
   					}
   					if ($i1 == 0)
   						printf("%f", $x);
   					else
   						printf(", %f", $x);
   				}
   				printf(") のとき，最大値 %f\n", $this->s[$this->n][0]);
   			}
   		}
   }
   
   					// 入力
   							// 変数の数と式の数
   	fscanf(STDIN, "%d %d", $m, $n);
   	$cp   = array($n);
   	$z    = array($m);
   	$eq_l = array($n);
   	$eq_r = array($n);
   	for ($i1 = 0; $i1 < $n; $i1++)
   		$eq_l[$i1] = array($m);
   							// 目的関数の係数
   	$str  = trim(fgets(STDIN));
   	$z[0] = floatval(strtok($str, " "));
   	for ($i1 = 1; $i1 < $m; $i1++)
   		$z[$i1] = floatval(strtok(" "));
   							// 制約条件
   	for ($i1 = 0; $i1 < $n; $i1++) {
   		$str          = trim(fgets(STDIN));
   		$eq_l[$i1][0] = floatval(strtok($str, " "));
   		for ($i2 = 1; $i2 < $m; $i2++)
   			$eq_l[$i1][$i2] = floatval(strtok(" "));
   		$c = strtok(" ");
   		if ($c == '<')
   			$cp[$i1] = -1;
   		else if ($c == '>')
   			$cp[$i1] = 1;
   		else
   			$cp[$i1] = 0;
   		$eq_r[$i1] = floatval(strtok(" "));
   	}
   					// 実行
   	$lp = new LP($n, $m, $z, $eq_l, $eq_r, $cp);
   	$sw = $lp->optimize(1);
   					// 結果の出力
   	$lp->result();
   
   ?>
   			

5. Ruby

   #***************************/
   # 線形計画法               */
   #      coded by Y.Suganuma */
   #***************************/
   
   #************/
   # クラス LP */
   #************/
   class LP
   	#*****************************/
   	# コンストラクタ             */
   	#      n1 : 制約条件の数     */
   	#      m1 : 変数の数         */
   	#      z1 : 目的関数の係数   */
   	#      eq_l : 制約条件の左辺 */
   	#      eq_r : 制約条件の右辺 */
   	#      cp1 : 比較演算子      */
   	#*****************************/
   	def initialize(n1, m1, z1, eq_l, eq_r, cp1)
   				# 初期設定
   		@_eps = 1.0e-10   # 許容誤差
   		@_err = 0   # エラーコード （0:正常終了, 1:解無し）
   		@_n   = n1   # 制約条件の数
   		@_m   = m1   # 変数の数
   		@_a   = Array.new(@_n)   # 人為変数があるか否か
   		@_cp  = Array.new(@_n)   # 比較演算子（-1: 左辺 < 右辺, 0: 左辺 = 右辺, 1: 左辺 > 右辺）
   		for i1 in 0 ... @_n
   			@_a[i1]  = 0
   			@_cp[i1] = cp1[i1]
   		end
   		@_z = Array.new(@_m)   # 目的関数の係数
   		for i1 in 0 ... @_m
   			@_z[i1] = z1[i1]
   		end
   				# スラック変数と人為変数の数を数える
   		@_m_s = 0   # スラック変数の数
   		@_m_a = 0   # 人為変数の数
   		for i1 in 0 ... @_n
   			if @_cp[i1] == 0
   				@_m_a += 1
   				if eq_r[i1] < 0.0
   					eq_r[i1] = -eq_r[i1]
   					for i2 in 0 ... @_m
   						eq_l[i1][i2] = -eq_l[i1][i2]
   					end
   				end
   			else
   				@_m_s += 1
   				if eq_r[i1] < 0.0
   					@_cp[i1] = -@_cp[i1]
   					eq_r[i1] = -eq_r[i1]
   					for i2 in 0 ... @_m
   						eq_l[i1][i2] = -eq_l[i1][i2]
   					end
   				end
   				if @_cp[i1] > 0
   					@_m_a += 1
   				end
   			end
   		end
   				# 単体表の作成
   						# 初期設定
   		@_mm  = @_m + @_m_s + @_m_a   # m + m_s + m_a
   		@_row = Array.new(@_n)   # 各行の基底変数の番号
   		@_s   = Array.new(@_n+1)   # 単体表
   		for i1 in 0 ... @_n+1
   			@_s[i1] = Array.new(@_mm+1)
   			if i1 < @_n
   				@_s[i1][0] = eq_r[i1]
   				for i2 in 0 ... @_m
   					@_s[i1][i2+1] = eq_l[i1][i2]
   				end
   				for i2 in @_m+1 ... @_mm+1
   					@_s[i1][i2] = 0.0
   				end
   			else
   				for i2 in 0 ... @_mm+1
   					@_s[i1][i2] = 0.0
   				end
   			end
   		end
   						# スラック変数
   		k = @_m + 1
   		for i1 in 0 ... @_n
   			if @_cp[i1] != 0
   				if @_cp[i1] < 0
   					@_s[i1][k] = 1.0
   					@_row[i1]  = k - 1
   				else
   					@_s[i1][k] = -1.0
   				end
   				k += 1
   			end
   		end
   						# 人為変数
   		for i1 in 0 ... @_n
   			if @_cp[i1] >= 0
   				@_s[i1][k] = 1.0
   				@_row[i1]  = k - 1
   				@_a[i1]    = 1
   				k += 1
   			end
   		end
   						# 目的関数
   		if @_m_a == 0
   			for i1 in 0 ... @_m
   				@_s[@_n][i1+1] = -@_z[i1]
   			end
   		else
   			for i1 in 0 ... @_m+@_m_s+1
   				for i2 in 0 ... @_n
   					if @_a[i2] > 0
   						@_s[@_n][i1] -= @_s[i2][i1]
   					end
   				end
   			end
   		end
   	end
   
   	#******************************/
   	# 最適化                      */
   	#      sw : =0 : 中間結果無し */
   	#           =1 : 中間結果あり */
   	#      return : =0 : 正常終了 */
   	#             : =1 : 解無し   */
   	#******************************/
   	def optimize(sw)
   				# フェーズ１
   		if sw > 0
   			if @_m_a > 0
   				printf("\nphase 1\n")
   			else
   				printf("\nphase 2\n")
   			end
   		end
   		opt_run(sw)
   				# フェーズ２
   		if @_err == 0 && @_m_a > 0
   						# 目的関数の変更
   			@_mm -= @_m_a
   			for i1 in 0 ... @_mm+1
   				@_s[@_n][i1] = 0.0
   			end
   			for i1 in 0 ... @_n
   				k = @_row[i1]
   				if k < @_m
   					@_s[@_n][0] += @_z[k] * @_s[i1][0]
   				end
   			end
   			for i1 in 0 ... @_mm
   				for i2 in 0 ... @_n
   					k = @_row[i2]
   					if k < @_m
   						@_s[@_n][i1+1] += @_z[k] * @_s[i2][i1+1]
   					end
   				end
   				if i1 < @_m
   					@_s[@_n][i1+1] -= @_z[i1]
   				end
   			end
   						# 最適化
   			if sw > 0
   				printf("\nphase 2\n")
   			end
   			opt_run(sw)
   		end
   
   		return @_err
   	end
   
   	#******************************/
   	# 最適化（単体表の変形）      */
   	#      sw : =0 : 中間結果無し */
   	#           =1 : 中間結果あり */
   	#******************************/
   	def opt_run(sw)
   		@_err = -1
   		while @_err < 0
   				# 中間結果
   			if sw > 0
   				printf("\n")
   				output()
   			end
   				# 列の選択（巡回を防ぐため必ずしも最小値を選択しない，Bland の規則）
   			q = -1
   			for i1 in 1 ... @_mm+1
   				if @_s[@_n][i1] < -@_eps
   					q = i1 - 1
   				end
   				if q >= 0
   					break
   				end
   			end
   				# 終了（最適解）
   			if q < 0
   				@_err = 0
   				# 行の選択（ Bland の規則を採用）
   			else
   				p   = -1
   				k   = -1
   				min = 0.0
   				for i1 in 0 ... @_n
   					if @_s[i1][q+1] > @_eps
   						x = @_s[i1][0] / @_s[i1][q+1]
   						if p < 0 || x < min || x == min && @_row[i1] < k
   							min = x
   							p   = i1
   							k   = @_row[i1]
   						end
   					end
   				end
   						# 解無し
   				if p < 0
   					@_err = 1
   						# 変形
   				else
   					x        = @_s[p][q+1]
   					@_row[p] = q
   					for i1 in 0 ... @_mm+1
   						@_s[p][i1] /= x
   					end
   					for i1 in 0 ... @_n+1
   						if i1 != p
   							x = @_s[i1][q+1]
   							for i2 in 0 ... @_mm+1
   								@_s[i1][i2] -= x * @_s[p][i2]
   							end
   						end
   					end
   				end
   			end
   		end
   	end
   
   	#***************/
   	# 単体表の出力 */
   	#***************/
   	def output()
   		for i1 in 0 ... @_n+1
   			if i1 < @_n
   				printf("x%d", @_row[i1]+1)
   			else
   				printf(" z")
   			end
   			for i2 in 0 ... @_mm+1
   				printf(" %f", @_s[i1][i2])
   			end
   			printf("\n")
   		end
   	end
   
   	#*************/
   	# 結果の出力 */
   	#*************/
   	def result()
   		if @_err > 0
   			printf("\n解が存在しません\n")
   		else
   			printf("\n(")
   			for i1 in 0 ... @_m
   				x = 0.0
   				for i2 in 0 ... @_n
   					if @_row[i2] == i1
   						x = @_s[i2][0]
   						break
   					end
   				end
   				if i1 == 0
   					printf("%f", x)
   				else
   					printf(", %f", x)
   				end
   			end
   			printf(") のとき，最大値 %f\n", @_s[@_n][0])
   		end
   	end
   end
   
   				# 入力
   						# 変数の数と式の数
   str  = gets();
   a    = str.split(" ");
   m    = Integer(a[0]);
   n    = Integer(a[1]);
   cp   = Array.new(n)
   z    = Array.new(m)
   eq_r = Array.new(n)
   eq_l = Array.new(n)
   for i1 in 0 ... n
   	eq_l[i1] = Array.new(m)
   end
   						# 目的関数の係数
   str = gets();
   a   = str.split(" ");
   for i1 in 0 ... m
   	z[i1] = Float(a[i1])
   end
   						# 制約条件
   for i1 in 0 ... n
   	str = gets();
   	a   = str.split(" ");
   	for i2 in 0 ... m
   		eq_l[i1][i2] = Float(a[i2])
   	end
   	if a[m] == '<'
   		cp[i1] = -1
   	elsif a[m] == '>'
   		cp[i1] = 1
   	else
   		cp[i1] = 0
   	end
   	eq_r[i1] = Float(a[m+1])
   end
   				# 実行
   lp = LP.new(n, m, z, eq_l, eq_r, cp)
   sw = lp.optimize(1)
   				# 結果の出力
   lp.result()
   			

6. Python

   # -*- coding: UTF-8 -*-
   import numpy as np
   import sys
   from math import *
   
   ############################################
   # クラス LP（線形計画法）
   #      coded by Y.Suganuma
   ############################################
   
   class LP :
   
   	################################
   	# コンストラクタ
   	#      n1 : 制約条件の数
   	#      m1 : 変数の数
   	#      z1 : 目的関数の係数
   	#      eq_l : 制約条件の左辺
   	#      eq_r : 制約条件の右辺
   	#      cp1 : 比較演算子
   	################################
   
   	def __init__(self, n1, m1, z1, eq_l, eq_r, cp1) :
   				# 初期設定
   		self.eps = 1.0e-10   # 許容誤差
   		self.err = 0   # エラーコード （0:正常終了, 1:解無し）
   		self.n   = n1   # 制約条件の数
   		self.m   = m1   # 変数の数
   		self.a   = np.zeros(self.n)   # 人為変数があるか否か
   		self.cp  = cp1   # 比較演算子（-1:左辺<右辺, 0:左辺=右辺, 1:左辺>右辺）
   		self.z   = z1   # 目的関数の係数
   				# スラック変数と人為変数の数を数える
   		self.m_s = 0   # スラック変数の数
   		self.m_a = 0   # 人為変数の数
   		for i1 in range(0, self.n) :
   			if self.cp[i1] == 0 :
   				self.m_a += 1
   				if eq_r[i1] < 0.0 :
   					eq_r[i1] = -eq_r[i1]
   					for i2 in rang(0, self.m) :
   						eq_l[i1][i2] = -eq_l[i1][i2]
   			else :
   				self.m_s += 1
   				if eq_r[i1] < 0.0 :
   					self.cp[i1] = -self.cp[i1]
   					eq_r[i1]    = -eq_r[i1]
   					for i2 in rang(0, self.m) :
   						eq_l[i1][i2] = -eq_l[i1][i2]
   				if self.cp[i1] > 0 :
   					self.m_a += 1
   				# 単体表の作成
   					# 初期設定
   		self.mm  = self.m + self.m_s + self.m_a
   		self.row = np.empty(self.n, np.int)   # 各行の基底変数の番号
   		self.s   = np.empty((self.n+1, self.mm+1), np.float)   # 単体表
   		for i1 in range(0, self.n+1) :
   			if i1 < self.n :
   				self.s[i1][0] = eq_r[i1]
   				for i2 in range(0, self.m) :
   					self.s[i1][i2+1] = eq_l[i1][i2]
   				for i2 in range(self.m+1, self.mm+1) :
   					self.s[i1][i2] = 0.0
   			else :
   				for i2 in range(0, self.mm+1) :
   					self.s[i1][i2] = 0.0
   					# スラック変数
   		k = self.m + 1
   		for i1 in range(0, self.n) :
   			if self.cp[i1] != 0 :
   				if self.cp[i1] < 0 :
   					self.s[i1][k] = 1.0
   					self.row[i1]  = k - 1
   				else :
   					self.s[i1][k] = -1.0
   				k += 1
   					# 人為変数
   		for i1 in range(0, self.n) :
   			if self.cp[i1] >= 0 :
   				self.s[i1][k] = 1.0
   				self.row[i1]  = k - 1
   				self.a[i1]    = 1
   				k += 1
   					# 目的関数
   		if self.m_a == 0 :
   			for i1 in range(0, self.m) :
   				self.s[self.n][i1+1] = -self.z[i1]
   		else :
   			for i1 in range(0 , self.m+self.m_s+1) :
   				for i2 in range(0 , self.n) :
   					if self.a[i2] > 0 :
   						self.s[self.n][i1] -= self.s[i2][i1]
   
   	################################
   	# 最適化
   	#      sw : =0 : 中間結果無し
   	#           =1 : 中間結果あり
   	#      return : =0 : 正常終了
   	#             : =1 : 解無し
   	################################
   
   	def optimize(self, sw) :
   				# フェーズ１
   		if sw > 0 :
   			if self.m_a > 0 :
   				print("\nphase 1")
   			else :
   				print("\nphase 2")
   		self.opt_run(sw)
   				# フェーズ２
   		if self.err == 0 and self.m_a > 0 :
   					# 目的関数の変更
   			self.mm -= self.m_a
   			for i1 in range(0, self.mm+1) :
   				self.s[self.n][i1] = 0.0
   			for i1 in range(0 , self.n) :
   				k = self.row[i1]
   				if k < self.m :
   					self.s[self.n][0] += self.z[k] * self.s[i1][0]
   			for i1 in range(0, self.mm) :
   				for i2 in range(0, self.n) :
   					k = self.row[i2]
   					if k < self.m :
   						self.s[self.n][i1+1] += self.z[k] * self.s[i2][i1+1]
   				if i1 < self.m :
   					self.s[self.n][i1+1] -= self.z[i1]
   					# 最適化
   			if sw > 0 :
   				print("\nphase 2")
   			self.opt_run(sw)
   
   		return self.err
   
   	################################
   	# 最適化（単体表の変形）
   	#      sw : =0 : 中間結果無し
   	#           =1 : 中間結果あり
   	################################
   
   	def opt_run(self, sw) :
   
   		self.err = -1
   		while self.err < 0 :
   				# 中間結果
   			if sw > 0 :
   				print()
   				self.output()
   				# 列の選択（巡回を防ぐため必ずしも最小値を選択しない，Bland の規則）
   			q = -1
   			for i1 in range(1, self.mm+1) :
   				if self.s[self.n][i1] < -self.eps :
   					q = i1 - 1
   					break
   				# 終了（最適解）
   			if q < 0 :
   				self.err = 0
   				# 行の選択（ Bland の規則を採用）
   			else :
   				p   = -1
   				k   = -1
   				min = 0.0
   				for i1 in range(0, self.n) :
   					if self.s[i1][q+1] > self.eps :
   						x = self.s[i1][0] / self.s[i1][q+1]
   						if (p < 0) or (x < min) or ((x == min) and (self.row[i1] < k)) :
   							min = x
   							p   = i1
   							k   = self.row[i1]
   					# 解無し
   				if p < 0 :
   					self.err = 1
   					# 変形
   				else :
   					x           = self.s[p][q+1]
   					self.row[p] = q
   					for i1 in range(0, self.mm+1) :
   						self.s[p][i1] /= x
   					for i1 in range(0, self.n+1) :
   						if i1 != p :
   							x = self.s[i1][q+1]
   							for i2 in range(0, self.mm+1) :
   								self.s[i1][i2] -= (x * self.s[p][i2])
   
   	################################
   	# 単体表の出力
   	################################
   
   	def output(self) :
   
   		for i1 in range(0, self.n+1) :
   			if i1 < self.n :
   				print("x" + str(self.row[i1]+1), end="")
   			else :
   				print(" z", end="")
   			for i2 in range(0, self.mm+1) :
   				print(" " + str(self.s[i1][i2]), end="")
   			print()
   
   	################################
   	# 結果の出力
   	################################
   
   	def result(self) :
   
   		if self.err > 0 :
   			print("\n解が存在しません")
   		else :
   			print("\n(", end="")
   			for i1 in range(0, self.m) :
   				x = 0.0
   				for i2 in range(0, self.n) :
   					if self.row[i2] == i1 :
   						x = self.s[i2][0]
   						break
   				if i1 == 0 :
   					print(x, end="")
   				else :
   					print(", " + str(x), end="")
   			print(") のとき，最大値 " + str(self.s[self.n][0]))
   
   ############################################
   # 線形計画法
   #      coded by Y.Suganuma
   ############################################
   
   			# 入力
   				# 変数の数と式の数
   line = sys.stdin.readline()
   x    = line.split()
   m    = int(x[0])
   n    = int(x[1])
   cp   = np.empty(n, np.int)
   z    = np.empty(m, np.float)
   eq_r = np.empty(n, np.float)
   eq_l = np.empty((n, m), np.float)
   				# 目的関数の係数
   line = sys.stdin.readline()
   x    = line.split()
   for i1 in range(0, m) :
   	z[i1] = float(x[i1])
   				# 制約条件
   for i1 in range(0, n) :
   	line = sys.stdin.readline()
   	x    = line.split()
   	for i2 in range(0, m) :
   		eq_l[i1][i2] = float(x[i2])
   	if x[m] == '<' :
   		cp[i1] = -1
   	elif x[m] == '>' :
   		cp[i1] = 1
   	else :
   		cp[i1] = 0
   	eq_r[i1] = float(x[m+1])
   			# 実行
   lp = LP(n, m, z, eq_l, eq_r, cp)
   lp.optimize(1)
   			# 結果の出力
   lp.result()
   			

7. C#

   /****************************/
   /* 線形計画法               */
   /*      coded by Y.Suganuma */
   /****************************/
   using System;
   
   /*************/
   /* クラス LP */
   /*************/
   class LP
   {
   	private int n;   // 制約条件の数
   	private int m;   // 変数の数
   	private int m_s;   // スラック変数の数
   	private int m_a;   // 人為変数の数
   	private int mm;   // m + m_s + m_a
   	private int[] a;   // 人為変数があるか否か
   	private int[] cp;   // 比較演算子（-1:左辺<右辺, 0:左辺=右辺, 1:左辺>右辺）
   	private int[] row;   // 各行の基底変数の番号
   	private double[] z;   // 目的関数の係数
   	private double[][] s;   // 単体表
   	private double eps;   // 許容誤差
   	private int err;   // エラーコード （0:正常終了, 1:解無し）
   
   	/******************************/
   	/* コンストラクタ             */
   	/*      n1 : 制約条件の数     */
   	/*      m1 : 変数の数         */
   	/*      z1 : 目的関数の係数   */
   	/*      eq_l : 制約条件の左辺 */
   	/*      eq_r : 制約条件の右辺 */
   	/*      cp1 : 比較演算子      */
   	/******************************/
   	public LP(int n1, int m1, double[] z1, double[][] eq_l, double[] eq_r, int[] cp1)
   	{
   					// 初期設定
   		eps = 1.0e-10;
   		err = 0;
   		n   = n1;
   		m   = m1;
   		a   = new int [n];
   		cp  = new int [n];
   		for (int i1 = 0; i1 < n; i1++) {
   			a[i1]  = 0;
   			cp[i1] = cp1[i1];
   		}
   		z = new double [m];
   		for (int i1 = 0; i1 < m; i1++)
   			z[i1] = z1[i1];
   					// スラック変数と人為変数の数を数える
   		m_s = 0;
   		m_a = 0;
   		for (int i1 = 0; i1 < n; i1++) {
   			if (cp[i1] == 0) {
   				m_a++;
   				if (eq_r[i1] < 0.0) {
   					eq_r[i1] = -eq_r[i1];
   					for (int i2 = 0; i2 < m; i2++)
   						eq_l[i1][i2] = -eq_l[i1][i2];
   				}
   			}
   			else {
   				m_s++;
   				if (eq_r[i1] < 0.0) {
   					cp[i1]   = -cp[i1];
   					eq_r[i1] = -eq_r[i1];
   					for (int i2 = 0; i2 < m; i2++)
   						eq_l[i1][i2] = -eq_l[i1][i2];
   				}
   				if (cp[i1] > 0)
   					m_a++;
   			}
   		}
   					// 単体表の作成
   							// 初期設定
   		mm  = m + m_s + m_a;
   		row = new int [n];
   		s   = new double [n+1][];
   		for (int i1 = 0; i1 < n+1; i1++)
   			s[i1] = new double [mm+1];
   		for (int i1 = 0; i1 <= n; i1++) {
   			if (i1 < n) {
   				s[i1][0] = eq_r[i1];
   				for (int i2 = 0; i2 < m; i2++)
   					s[i1][i2+1] = eq_l[i1][i2];
   				for (int i2 = m+1; i2 <= mm; i2++)
   					s[i1][i2] = 0.0;
   			}
   			else {
   				for (int i2 = 0; i2 <= mm; i2++)
   					s[i1][i2] = 0.0;
   			}
   		}
   							// スラック変数
   		int k = m + 1;
   		for (int i1 = 0; i1 < n; i1++) {
   			if (cp[i1] != 0) {
   				if (cp[i1] < 0) {
   					s[i1][k] = 1.0;
   					row[i1]  = k - 1;
   				}
   				else
   					s[i1][k] = -1.0;
   				k++;
   			}
   		}
   							// 人為変数
   		for (int i1 = 0; i1 < n; i1++) {
   			if (cp[i1] >= 0) {
   				s[i1][k] = 1.0;
   				row[i1]  = k - 1;
   				a[i1]    = 1;
   				k++;
   			}
   		}
   							// 目的関数
   		if (m_a == 0) {
   			for (int i1 = 0; i1 < m; i1++)
   				s[n][i1+1] = -z[i1];
   		}
   		else {
   			for (int i1 = 0; i1 <= m+m_s; i1++) {
   				for (int i2 = 0; i2 < n; i2++) {
   					if (a[i2] > 0)
   						s[n][i1] -= s[i2][i1];
   				}
   			}
   		}
   	}
   
   	/*******************************/
   	/* 最適化                      */
   	/*      sw : =0 : 中間結果無し */
   	/*           =1 : 中間結果あり */
   	/*      return : =0 : 正常終了 */
   	/*             : =1 : 解無し   */
   	/*******************************/
   	public int optimize(int sw)
   	{
   					// フェーズ１
   		if (sw > 0) {
   			if (m_a > 0) {
   				Console.WriteLine();
   				Console.WriteLine("phase 1");
   			}
   			else {
   				Console.WriteLine();
   				Console.WriteLine("phase 2");
   			}
   		}
   		opt_run(sw);
   					// フェーズ２
   		int k;
   		if (err == 0 && m_a > 0) {
   							// 目的関数の変更
   			mm -= m_a;
   			for (int i1 = 0; i1 <= mm; i1++)
   				s[n][i1] = 0.0;
   			for (int i1 = 0; i1 < n; i1++) {
   				k = row[i1];
   				if (k < m)
   					s[n][0] += z[k] * s[i1][0];
   			}
   			for (int i1 = 0; i1 < mm; i1++) {
   				for (int i2 = 0; i2 < n; i2++) {
   					k = row[i2];
   					if (k < m)
   						s[n][i1+1] += z[k] * s[i2][i1+1];
   				}
   				if (i1 < m)
   					s[n][i1+1] -= z[i1];
   			}
   							// 最適化
   			if (sw > 0) {
   				Console.WriteLine();
   				Console.WriteLine("phase 2");
   			}
   			opt_run(sw);
   		}
   
   		return err;
   	}
   
   	/*******************************/
   	/* 最適化（単体表の変形）      */
   	/*      sw : =0 : 中間結果無し */
   	/*           =1 : 中間結果あり */
   	/*******************************/
   	void opt_run(int sw)
   	{
   		err = -1;
   		int p, q, k;
   		double x, min;
   
   		while (err < 0) {
   					// 中間結果
   			if (sw > 0) {
   				Console.WriteLine();
   				output();
   			}
   					// 列の選択（巡回を防ぐため必ずしも最小値を選択しない，Bland の規則）
   			q = -1;
   			for (int i1 = 1; i1 <= mm && q < 0; i1++) {
   				if (s[n][i1] < -eps)
   					q = i1 - 1;
   			}
   					// 終了（最適解）
   			if (q < 0)
   				err = 0;
   					// 行の選択（ Bland の規則を採用）
   			else {
   				p   = -1;
   				k   = -1;
   				min = 0.0;
   				for (int i1 = 0; i1 < n; i1++) {
   					if (s[i1][q+1] > eps) {
   						x = s[i1][0] / s[i1][q+1];
   						if (p < 0 || x < min || x == min && row[i1] < k) {
   							min = x;
   							p   = i1;
   							k   = row[i1];
   						}
   					}
   				}
   							// 解無し
   				if (p < 0)
   					err = 1;
   							// 変形
   				else {
   					x      = s[p][q+1];
   					row[p] = q;
   					for (int i1 = 0; i1 <= mm; i1++)
   						s[p][i1] /= x;
   					for (int i1 = 0; i1 <= n; i1++) {
   						if (i1 != p) {
   							x = s[i1][q+1];
   							for (int i2 = 0; i2 <= mm; i2++)
   								s[i1][i2] -= x * s[p][i2];
   						}
   					}
   				}
   			}
   		}
   	}
   
   	/****************/
   	/* 単体表の出力 */
   	/****************/
   	void output()
   	{
   		for (int i1 = 0; i1 <= n; i1++) {
   			if (i1 < n)
   				Console.Write("x" + (row[i1]+1));
   			else
   				Console.Write(" z");
   			for (int i2 = 0; i2 <= mm; i2++)
   				Console.Write(" " + s[i1][i2]);
   			Console.WriteLine();
   		}
   	}
   
   	/**************/
   	/* 結果の出力 */
   	/**************/
   	public void result()
   	{
   		if (err > 0) {
   			Console.WriteLine("解が存在しません");
   			Console.WriteLine();
   		}
   		else {
   			Console.WriteLine();
   			Console.Write("(");
   			for (int i1 = 0; i1 < m; i1++) {
   				double x = 0.0;
   				for (int i2 = 0; i2 < n; i2++) {
   					if (row[i2] == i1) {
   						x = s[i2][0];
   						break;
   					}
   				}
   				if (i1 == 0)
   					Console.Write(x);
   				else
   					Console.Write(", " + x);
   			}
   			Console.WriteLine(") のとき，最大値 " + s[n][0]);
   		}
   	}
   }
   
   /****************/
   /* main program */
   /****************/
   class Program
   {
   	static void Main()
   	{
   					// 入力
   							// 変数の数と式の数
   		string[] str    = Console.ReadLine().Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
   		int m           = int.Parse(str[0]);
   		int n           = int.Parse(str[1]);
   		int[] cp        = new int [n];
   		double[] z      = new double [m];
   		double[][] eq_l = new double [n][];
   		for (int i1 = 0; i1 < n; i1++)
   			eq_l[i1] = new double [m];
   		double[] eq_r = new double [n];
   							// 目的関数の係数
   		str = Console.ReadLine().Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
   		for (int i1 = 0; i1 < m; i1++)
   			z[i1] = double.Parse(str[i1]);
   							// 制約条件
   		for (int i1 = 0; i1 < n; i1++) {
   			str = Console.ReadLine().Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
   			for (int i2 = 0; i2 < m; i2++)
   				eq_l[i1][i2] = double.Parse(str[i2]);
   			if (String.Compare("<", str[m]) == 0)
   				cp[i1] = -1;
   			else if (String.Compare(">", str[m]) == 0)
   				cp[i1] = 1;
   			else
   				cp[i1] = 0;
   			eq_r[i1] = double.Parse(str[m+1]);
   		}
   					// 実行
   		LP lp  = new LP(n, m, z, eq_l, eq_r, cp);
   		int sw = lp.optimize(1);
   					// 結果の出力
   		if (sw == 0)
   			lp.result();
   		else
   			Console.WriteLine("解がありません！");
   	}
   }
   			

8. VB

   ''''''''''''''''''''''''''''
   ' 線形計画法               '
   '      coded by Y.Suganuma '
   ''''''''''''''''''''''''''''
   Imports System.Text.RegularExpressions
   
   Module Test
   
   	Sub Main()
   					' 入力
   							' 変数の数と式の数
   		Dim MS As Regex     = New Regex("\s+") 
   		Dim str() As String = MS.Split(Console.ReadLine().Trim())
   		Dim m As Integer    = Integer.Parse(str(0))
   		Dim n As Integer    = Integer.Parse(str(1))
   		Dim cp(n) As Integer
   		Dim z(m) As Double
   		Dim eq_l(n,m) As Double
   		Dim eq_r(n) As Double
   							' 目的関数の係数
   		str = MS.Split(Console.ReadLine().Trim())
   		For i1 As Integer = 0 To m-1
   			z(i1) = Double.Parse(str(i1))
   		Next
   							' 制約条件
   		For i1 As Integer = 0 To n-1
   			str = MS.Split(Console.ReadLine().Trim())
   			For i2 As Integer = 0 To m-1
   				eq_l(i1,i2) = Double.Parse(str(i2))
   			Next
   			If String.Compare("<", str(m)) = 0
   				cp(i1) = -1
   			ElseIf String.Compare(">", str(m)) = 0
   				cp(i1) = 1
   			Else
   				cp(i1) = 0
   			End If
   			eq_r(i1) = Double.Parse(str(m+1))
   		Next
   					' 実行
   		Dim lp1 As LP     = New LP(n, m, z, eq_l, eq_r, cp)
   		Dim sw As Integer = lp1.optimize(1)
   					' 結果の出力
   		If sw = 0
   			lp1.result()
   		Else
   			Console.WriteLine("解がありません！")
   		End If
   
   	End Sub
   
   	'''''''''''''
   	' クラス LP '
   	'''''''''''''
   	Class LP
   
   		private n As Integer   ' 制約条件の数
   		private m As Integer   ' 変数の数
   		private m_s As Integer   ' スラック変数の数
   		private m_a As Integer   ' 人為変数の数
   		private mm As Integer   ' m + m_s + m_a
   		private a() As Integer   ' 人為変数があるか否か
   		private cp() As Integer   ' 比較演算子（-1:左辺<右辺, 0:左辺=右辺, 1:左辺>右辺）
   		private row() As Integer   ' 各行の基底変数の番号
   		private z() As Double   ' 目的関数の係数
   		private s(,) As Double   ' 単体表
   		private eps As Double   ' 許容誤差
   		private err As Integer   ' エラーコード （0:正常終了, 1:解無し）
   		
   		''''''''''''''''''''''''''''''
   		' コンストラクタ             '
   		'      n1 : 制約条件の数     '
   		'      m1 : 変数の数         '
   		'      z1 : 目的関数の係数   '
   		'      eq_l : 制約条件の左辺 '
   		'      eq_r : 制約条件の右辺 '
   		'      cp1 : 比較演算子      '
   		''''''''''''''''''''''''''''''
   		Public Sub New (n1 As Integer, m1 As Integer, z1() As Double, eq_l(,) As Double,
   	                    eq_r() As Double, cp1() As Integer)
   						' 初期設定
   			eps = 1.0e-10
   			err = 0
   			n   = n1
   			m   = m1
   			ReDim a(n)
   			ReDim cp(n)
   			For i1 As Integer = 0 To n-1
   				a(i1)  = 0
   				cp(i1) = cp1(i1)
   			Next
   			ReDim z(m)
   			For i1 As Integer = 0 To m-1
   				z(i1) = z1(i1)
   			Next
   						' スラック変数と人為変数の数を数える
   			m_s = 0
   			m_a = 0
   			For i1 As Integer = 0 To n-1
   				If cp(i1) = 0
   					m_a += 1
   					If eq_r(i1) < 0.0
   						eq_r(i1) = -eq_r(i1)
   						For i2 As Integer = 0 To m-1
   							eq_l(i1,i2) = -eq_l(i1,i2)
   						Next
   					End If
   				Else
   					m_s += 1
   					If eq_r(i1) < 0.0
   						cp(i1)   = -cp(i1)
   						eq_r(i1) = -eq_r(i1)
   						For i2 As Integer = 0 To m-1
   							eq_l(i1,i2) = -eq_l(i1,i2)
   						Next
   					End If
   					If cp(i1) > 0
   						m_a += 1
   					End If
   				End If
   			Next
   						' 単体表の作成
   								' 初期設定
   			mm  = m + m_s + m_a
   			ReDim row(n)
   			ReDim s(n+1,mm+1)
   			For i1 As Integer = 0 To n
   				If i1 < n
   					s(i1,0) = eq_r(i1)
   					For i2 As Integer = 0 To m-1
   						s(i1,i2+1) = eq_l(i1,i2)
   					Next
   					For i2 As Integer = m+1 To mm
   						s(i1,i2) = 0.0
   					Next
   				Else
   					For i2 As Integer = 0 To mm
   						s(i1,i2) = 0.0
   					Next
   				End If
   			Next
   								' スラック変数
   			Dim k As Integer = m + 1
   			For i1 As Integer = 0 To n-1
   				If cp(i1) <> 0
   					If cp(i1) < 0
   						s(i1,k) = 1.0
   						row(i1) = k - 1
   					Else
   						s(i1,k) = -1.0
   					End If
   					k += 1
   				End If
   			Next
   								' 人為変数
   			For i1 As Integer = 0 To n-1
   				If cp(i1) >= 0
   					s(i1,k) = 1.0
   					row(i1) = k - 1
   					a(i1)   = 1
   					k      += 1
   				End If
   			Next
   								' 目的関数
   			If m_a = 0
   				For i1 As Integer = 0 To m
   					s(n,i1+1) = -z(i1)
   				Next
   			Else
   				For i1 As Integer = 0 To m+m_s
   					For i2 As Integer = 0 To n-1
   						If a(i2) > 0
   							s(n,i1) -= s(i2,i1)
   						End If
   					Next
   				Next
   			End If
   
   		End Sub
   	
   		'''''''''''''''''''''''''''''''
   		' 最適化                      '
   		'      sw : =0 : 中間結果無し '
   		'           =1 : 中間結果あり '
   		'      return : =0 : 正常終了 '
   		'             : =1 : 解無し   '
   		'''''''''''''''''''''''''''''''
   		Public Function optimize(sw As Integer)
   						' フェーズ１
   			If sw > 0
   				If m_a > 0
   					Console.WriteLine()
   					Console.WriteLine("phase 1")
   				Else
   					Console.WriteLine()
   					Console.WriteLine("phase 2")
   				End If
   			End If
   			opt_run(sw)
   						' フェーズ２
   			Dim k As Integer
   			If err = 0 and m_a > 0
   								' 目的関数の変更
   				mm -= m_a
   				For i1 As Integer = 0 To mm
   					s(n,i1) = 0.0
   				Next
   				For i1 As Integer = 0 To n-1
   					k = row(i1)
   					If k < m
   						s(n,0) += z(k) * s(i1,0)
   					End If
   				Next
   				For i1 As Integer = 0 To mm-1
   					For i2 As Integer = 0 To n-1
   						k = row(i2)
   						If k < m
   							s(n,i1+1) += z(k) * s(i2,i1+1)
   						End If
   					Next
   					If i1 < m
   						s(n,i1+1) -= z(i1)
   					End If
   				Next
   								' 最適化
   				If sw > 0
   					Console.WriteLine()
   					Console.WriteLine("phase 2")
   				End If
   				opt_run(sw)
   			End If
   	
   			Return err
   
   		End Function
   	
   		'''''''''''''''''''''''''''''''
   		' 最適化（単体表の変形）      '
   		'      sw : =0 : 中間結果無し '
   		'           =1 : 中間結果あり '
   		'''''''''''''''''''''''''''''''
   		Sub opt_run(sw As Integer)
   
   			err = -1
   			Dim p As Integer
   			Dim q As Integer
   			Dim k As Integer
   			Dim x As Double
   			Dim min As Double
   	
   			Do While err < 0
   						' 中間結果
   				If sw > 0
   					Console.WriteLine()
   					output()
   				End If
   						' 列の選択（巡回を防ぐため必ずしも最小値を選択しない，Bland の規則）
   				q = -1
   				Dim ii As Integer = 1
   				Do While ii <= mm and q < 0
   					If s(n,ii) < -eps
   						q = ii - 1
   					End If
   					ii += 1
   				Loop
   						' 終了（最適解）
   				If q < 0
   					err = 0
   						' 行の選択（ Bland の規則を採用）
   				Else
   					p   = -1
   					k   = -1
   					min = 0.0
   					For i1 As Integer = 0 To n-1
   						If s(i1,q+1) > eps
   							x = s(i1,0) / s(i1,q+1)
   							If p < 0 or x < min or (x = min and row(i1) < k)
   								min = x
   								p   = i1
   								k   = row(i1)
   							End If
   						End If
   					Next
   								' 解無し
   					If p < 0
   						err = 1
   								' 変形
   					Else
   						x      = s(p,q+1)
   						row(p) = q
   						For i1 As Integer = 0 To mm
   							s(p,i1) /= x
   						Next
   						For i1 As Integer = 0 To n
   							If i1 <> p
   								x = s(i1,q+1)
   								For i2 As Integer = 0 To mm
   									s(i1,i2) -= x * s(p,i2)
   								Next
   							End If
   						Next
   					End If
   				End If
   			Loop
   
   		End Sub
   	
   		''''''''''''''''
   		' 単体表の出力 '
   		''''''''''''''''
   		Sub output()
   
   			For i1 As Integer = 0 To n
   				If i1 < n
   					Console.Write("x" & (row(i1)+1))
   				Else
   					Console.Write(" z")
   				End If
   				For i2 As Integer = 0 To mm
   					Console.Write(" " & s(i1,i2))
   				Next
   				Console.WriteLine()
   			Next
   
   		End Sub
   	
   		''''''''''''''
   		' 結果の出力 '
   		''''''''''''''
   		Public Sub result()
   
   			If err > 0
   				Console.WriteLine("解が存在しません")
   				Console.WriteLine()
   			Else
   				Console.WriteLine()
   				Console.Write("(")
   				For i1 As Integer = 0 To m-1
   					Dim x As Double = 0.0
   					For i2 As Integer = 0 To n-1
   						If row(i2) = i1
   							x = s(i2,0)
   							Exit For
   						End If
   					Next
   					If i1 = 0
   						Console.Write(x)
   					Else
   						Console.Write(", " & x)
   					End If
   				Next
   				Console.WriteLine(") のとき，最大値 " & s(n,0))
   			End If
   
   		End Sub
   
   	End Class
   	
   End Module