2015-05-30
370
Рассмотрим сеть (рис. 3.3) с одним истоком (вершина 1) и одним стоком (вершина 4), на которой заданы пропускные способности дуг c1=11, с2=7, с3=5, с4=8. Обозначим величину потока из вершины 1 в вершину 2 через х1, из 2 в 4 – через х2, из 1 в 3 – через х3, из 3 в 4 – через х4. Произвольно задавать хi (i=1..4) нельзя. Эти числа должны удовлетворять ряду ограничений.
2 7
11 х1 х2 4
1 х3 х4
5 3 8
Рис. 3.3
1. Поток дуги не может быть больше её пропускной способности:
0£ х1£11, 0£ х2£7, 0£ х3£5, 0£ х4£8.
2. Для любой вершины, не являющейся ни истоком, ни стоком, суммарный поток входящих дуг равен суммарному потоку выходящих дуг:
х1–х2=0, х3–х4=0.
3. Вводится понятие суммарного потока Ф на конечных дугах сети, отличное от понятия потока на дуге xi, i=1..4. Сумма потоков, исходящих из начальной вершины, равен сумме потоков, входящих в конечную вершину:
х1+х3=Ф, х2+х4=Ф.
Возникает задача: определить величину максимального потока в графе при заданных пропускных способностях, т.е. найти хi, i=1..4, удовлетворяющие условиям 1 – 3, максимизирующие целевую функцию Fmax=Ф.
Существуют различные методы решения задач линейного программирования. Одним из наиболее распространённых методов решения задачи ЛП является симплексный метод. Он позволяет за конечное число шагов определить область допустимых базисных решений и найти оптимальное решение задачи.
Сначала необходимо представить задачу в удобном для программирования виде. Для этого заменим в уравнениях Ф на х5, а часть равенств представим в виде неравенств (для решения задачи стандартным симплекс-методом). Получаем задачу ЛП:
Fmax=x5.
В соответствии с этим можно записать начальную симплекс -таблицу.
Таблица 3.1
| – x1 | – x2 | – x3 | – x4 | – x5 | B | |
| –1 | ||||||
| –1 | ||||||
| Y3 | –1 | |||||
| Y4 | –1 | |||||
| Y5 | –1 | |||||
| Y6 | –1 | |||||
| Y7 | ||||||
| Y8 | ||||||
| Y9 | ||||||
| Y10 | ||||||
| Fmax | –1 |
Решая задачу, получим конечную симплекс-таблицу с решением прямой задачи:
Таблица 3.2
| – y9 | – y4 | – y8 | B | |||
| X1 | ||||||
| X2 | ||||||
| Y3 | ||||||
| X4 | –1 | |||||
| Y5 | –1 | –1 | ||||
| Y6 | –1 | |||||
| Y7 | –1 | –1 | ||||
| X5 | –1 | |||||
| X3 | ||||||
| Y10 | –1 | –1 | –1 | |||
| Fmax | –1 |
Решение задачи для исходных переменных:
x1=7; x2=7; x3=5; x4=5; x5=12;
при этом Fmax=12.
