静岡理工科大学 菅沼ホーム 目次 索引

最適化(線形計画法)

    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;
    					// フェーズ1
    			if (sw > 0) {
    				if (m_a > 0)
    					printf("\nphase 1\n");
    				else
    					printf("\nphase 2\n");
    			}
    			opt_run(sw);
    					// フェーズ2
    			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;
    					// フェーズ1
    		if (sw > 0) {
    			if (m_a > 0)
    				System.out.printf("\nphase 1\n");
    			else
    				System.out.printf("\nphase 2\n");
    		}
    		opt_run(sw);
    					// フェーズ2
    		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();
    	}
    }
    			
    アプレット版
    /****************************/
    /* 線形計画法               */
    /*      coded by Y.Suganuma */
    /****************************/
    import java.awt.*;
    import java.awt.event.*;
    import java.applet.*;
    import java.util.StringTokenizer;
    
    public class Linear extends Applet implements ActionListener {
    	TextField order, cond;
    	TextArea ta1, ta2;
    	Button bt;
    	Font f = new Font("TimesRoman", Font.BOLD, 20);
    
    	/************/
    	/* 初期設定 */
    	/************/
    	public void init()
    	{
    					// レイアウト,背景色,フォント
    		setLayout(new BorderLayout(5, 5));
    		setBackground(new Color(225, 255, 225));
    		setFont(f);
    					// 上のパネル
    		Panel pn1 = new Panel();
    		add(pn1, BorderLayout.NORTH);
    
    		pn1.add(new Label("変数の数:"));
    		order = new TextField("2", 3);
    		pn1.add(order);
    
    		pn1.add(new Label("制約条件数:"));
    		cond = new TextField("3", 3);
    		pn1.add(cond);
    
    		pn1.add(new Label(" "));
    		bt = new Button("OK");
    		bt.setBackground(Color.pink);
    		bt.addActionListener(this);
    		pn1.add(bt);
    					// 中央のパネル(データ)
    		Panel pn2 = new Panel();
    		add(pn2, BorderLayout.CENTER);
    
    		pn2.add(new Label("入力データ:"));
    		ta1 = new TextArea("3 2\n3 1 < 9\n2.5 2 < 12.5\n1 2 < 8\n", 10, 30);
    		pn2.add(ta1);
    					// 下のパネル(結果)
    		Panel pn3 = new Panel();
    		add(pn3, BorderLayout.SOUTH);
    
    		ta2 = new TextArea(10, 65);
    		pn3.add(ta2);
    	}
    
    	/******************************/
    	/* ボタンが押されたときの処理 */
    	/******************************/
    	public void actionPerformed(ActionEvent e)
    	{
    		double eq_l[][], eq_r[], z[];
    		int i1, i2, n, m, cp[], sw;
    		String c;
    		StringTokenizer str1, str2;
    
    		if (e.getSource() == bt) {
    					// 入力
    							// 変数の数と式の数
    			m    = Integer.parseInt(order.getText());
    			n    = Integer.parseInt(cond.getText());
    			cp   = new int [n];
    			z    = new double [m];
    			eq_l = new double [n][m];
    			eq_r = new double [n];
    							// 目的関数の係数
    			String s = ta1.getText();
    			str1     = new StringTokenizer(s, "\n");
    			str2     = new StringTokenizer(str1.nextToken(), " ");
    			for (i1 = 0; i1 < m; i1++)
    				z[i1] = Double.parseDouble(str2.nextToken());
    							// 制約条件
    			for (i1 = 0; i1 < n; i1++) {
    				str2 = new StringTokenizer(str1.nextToken(), " ");
    				for (i2 = 0; i2 < m; i2++)
    					eq_l[i1][i2] = Double.parseDouble(str2.nextToken());
    				c = str2.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(str2.nextToken());
    			}
    					// 実行
    			ta2.setText("");
    			LP lp = new LP(n, m, z, eq_l, eq_r, cp, ta2);
    			sw    = lp.optimize(1);
    					// 結果の出力
    			lp.result();
    		}
    	}
    }
    
    /*************/
    /* クラス 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:解無し)
    	private TextArea ta;
    
    	/******************************/
    	/* コンストラクタ             */
    	/*      n1 : 制約条件の数     */
    	/*      m1 : 変数の数         */
    	/*      z1 : 目的関数の係数   */
    	/*      eq_l : 制約条件の左辺 */
    	/*      eq_r : 制約条件の右辺 */
    	/*      cp1 : 比較演算子      */
    	/******************************/
    	LP(int n1, int m1, double z1[], double eq_l[][], double eq_r[], int cp1[], TextArea tai)
    	{
    		int i1, i2, k;
    					// 初期設定
    		ta  = tai;
    		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;
    					// フェーズ1
    		if (sw > 0) {
    			if (m_a > 0)
    				ta.append("\nphase 1\n");
    			else
    				ta.append("\nphase 2\n");
    		}
    		opt_run(sw);
    					// フェーズ2
    		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)
    				ta.append("\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) {
    				ta.append("\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)
    				ta.append("x" + (row[i1]+1));
    			else
    				ta.append(" z");
    			for (i2 = 0; i2 <= mm; i2++)
    				ta.append(" " + s[i1][i2]);
    			ta.append("\n");
    		}
    	}
    
    	/**************/
    	/* 結果の出力 */
    	/**************/
    	void result()
    	{
    		double x;
    		int i1, i2;
    
    		if (err > 0)
    			ta.append("\n解が存在しません\n");
    		else {
    			ta.append("\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)
    					ta.append(String.valueOf(x));
    				else
    					ta.append(", " + x);
    			}
    			ta.append(") のとき,最大値 " + s[n][0] + "\n");
    		}
    	}
    }
    			

  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)
    	{
    					// フェーズ1
    		if (sw > 0) {
    			if (lp.m_a > 0)
    				lp.str += "\nphase 1\n";
    			else
    				lp.str += "\nphase 2\n";
    		}
    		lp.opt_run(sw);
    					// フェーズ2
    		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)
    		{
    					// フェーズ1
    			if ($sw > 0) {
    				if ($this->m_a > 0)
    					printf("\nphase 1\n");
    				else
    					printf("\nphase 2\n");
    			}
    			$this->opt_run($sw);
    					// フェーズ2
    			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)
    				# フェーズ1
    		if sw > 0
    			if @_m_a > 0
    				printf("\nphase 1\n")
    			else
    				printf("\nphase 2\n")
    			end
    		end
    		opt_run(sw)
    				# フェーズ2
    		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) :
    				# フェーズ1
    		if sw > 0 :
    			if self.m_a > 0 :
    				print("\nphase 1")
    			else :
    				print("\nphase 2")
    		self.opt_run(sw)
    				# フェーズ2
    		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)
    	{
    					// フェーズ1
    		if (sw > 0) {
    			if (m_a > 0) {
    				Console.WriteLine();
    				Console.WriteLine("phase 1");
    			}
    			else {
    				Console.WriteLine();
    				Console.WriteLine("phase 2");
    			}
    		}
    		opt_run(sw);
    					// フェーズ2
    		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)
    						' フェーズ1
    			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)
    						' フェーズ2
    			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
    			

静岡理工科大学 菅沼ホーム 目次 索引