【Ruby】【アルゴリズム】線形計画法の実装

　
Wikiで「アルゴリズム」を読んで勉強していたら、
「設計パラダイムによる分類」というところには、こんな分類が書いてあった。

分割統治法
動的計画法
貪欲法
線形計画法
還元
探索と数え上げ

　
ほかの分類は全部書いたことあるけど、線形計画法、はまだ書いた事ない。
ということで、実装してみる。
　
あ、あと「貪欲法」も書いたことない。。

　
問題と、そもそもの考え方は、ここを見て勉強。
システム工学講義資料その１　
システム工学講義資料その２

　
参考にしたサイトはこちら
JSで挑戦!線形計画法をプログラミングで解くためのアルゴリズム実装 - nigoblog

問題

あるレストランで，手持ちの材料からハンバーグとオムレツを作って利益を最大にしたいと考えている．手持ちの材料は，
• ひき肉 3800 [g]
• タマネギ 2100 [g]
• ケチャップ 1200 [g]
であり，それぞれの品を作るのに必要な材料の量は，
• ハンバーグ 1個あたり，ひき肉 60 [g]，タマネギ 20 [g]，ケチャップ 20 [g]
• オムレツ1個あたり，　ひき肉 40 [g]，タマネギ 30 [g]，ケチャップ 10 [g]
であるとする．(他に必要な材料は十分な量があるものとする)
販売価格は，
• ハンバーグ 400 [円/個]
• オムレツ 300 [円/個]
とする．総売上を最大にするには，それぞれハンバーグとオムレツを幾つずつ作れば良いか?

ピボット行の選択

参考サイトには以下の要領でピボットを見つけると書いてある。

ピボット列は
「単価と売上の式より、最大の係数のものから選択」
ピボット行は
「最大限使えるリソースに対するピボット列にかかる係数の商で最小のもの」
となります。

しかし実際、ピボット行は
「最大限使えるリソースに対するピボット列にかかる係数の商で最小かつ正のもの」
を選択する必要がある。

実装したコード

リファクタリングは明日します。。
こうやって見てみると、インスタンス変数に情報を持たせた弊害で、
実行関数が何を対象に処理を行っているのか見えづらくなっている

実行関数↓

@situation = init_situation
liner_programming
show_answer

分かりづらいよね。
素直に引数に入れて引き回したら、こう書けて、わかりやすくなる↓

liner_programming(init_situation)
show_answer(situation)

インスタンス変数にするのも考え物だ。
　

実装したコード

require 'matrix'

def find_pivot_column
  return @situation.last.index(@situation.last.max)
end

def find_pivot_row(col)
  min_val, min_row = nil,nil
  @situation.each_with_index do |row, row_index|

    #制約式のみ実行．最大式の任意の列はピポット列にならない
    next if row_index == @situation.length-1
    candidate = @situation[row_index].last.to_f/@situation[row_index][col]
    next if candidate < 0
    if (min_val.nil? || min_val > candidate)
      min_val = candidate
      min_row = row_index
    end
  end
  min_row
end

def elimination(pivot_row, pivot_column)
  quotient = @situation[pivot_row][pivot_column].to_f
  @situation[pivot_row].map!{|x| x/quotient}
  @situation.each_with_index do |line, row_index|
    next if row_index == pivot_row
    what_times = line[pivot_column]
    line.length.times do |column_index|
      line[column_index] -= @situation[pivot_row][column_index]*what_times
    end
  end
  @situation
end

def ok?
  @situation.last[0..@situation.last.length-2].each do |x|
    return false if x > 0
  end
  true
end

def liner_programming
  return if ok?
  pivot_column = find_pivot_column
  pivot_row = find_pivot_row(pivot_column)
  elimination(pivot_row, pivot_column)
  liner_programming
end

def show_answer
  @situation.each do |line|
    puts "count_hamburg: #{line.last}" if line[0].to_i == 1
    puts "count_omelette: #{line.last}" if line[1].to_i == 1
  end
  puts "total_sales: #{@situation.last.last*(-1)}"
end

init_situation = [
[60,  40,  1, 0, 0, 3800], #<= 制約式
[20,  30,  0, 1, 0, 2100], #<= 制約式
[20,  10,  0, 0, 1, 1200], #<= 制約式
[400, 300, 0, 0, 0, 0]]    #<= 最大式

@situation = init_situation
liner_programming
show_answer

■実行結果

count_omelette: 50.0
count_hamburg: 30.0
total_sales: 27000.0

情報系の学生って、、すごい。