December 2016
Intermediate to advanced
440 pages
9h 44m
Japanese
Content preview from アルゴリズムクイックリファレンス 第2版
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
276
■
8
章 ネットワークフローアルゴリズム
8.8
割り当て
割り当て問題は、輸送問題の制限が厳しいものとなる。供給節点は、
1
つのユニッ
トしか供給できない。需要節点の需要も
1
つとなる。
8.8.1
解
割り当て問題を、単一ユニットを提供する供給節点と単一ユニットを必要とする
需要節点に制限した輸送問題に変換する。
8.9
線形計画法
本章で述べた問題は、すべて線形計画法（
LP
）を使って解くことができる。
LP
は
線形（一次）の等式および不等式によって与えられた制約下で線形目標関数を最適化
する強力な技法である（
Bazarra and Jarvis, 1977
）。
LP
の実際を示すために、図8-8の輸送問題を、
LP
ソルバーで解くことができ
るように一連の線形方程式に変換する。
Maple
という数学ソフトウェア（
http:
//
www.maplesoft.com
）を用いて計算する。既に述べたように、目標はコストを最小
に保ちながらネットワーク上のフローを最大化する
ことである。ネットワークの各
辺のフローに変数を与える。すなわち、変数
e13
は、
f(1, 3)
を表す。最小化される
関数は
Cost
であり、ネットワーク上の
4
つの辺の輸送コストの総和として定義され
る。このコスト方程式は、ネットワークフローについて既に述べたものと同じく、
次のような制約を持つ。
フロー保存
ソース節点から出る辺の総和は、その供給と等しくなければならない。
需要節点へ入る辺の総和は、需要と等しくなければならない。
容量制約
辺上のフロー
f(i
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.