--PAGE_BREAK--Симплексный метод решения задач линейного программирования
Данный метод состоит в целенаправленном переборе опорных решений задачи линейного программирования. Он позволяет за конечное число шагов расчета либо найти оптимальное решение, либо установить его отсутствие.
Для реализации симплексного метода – последовательного улучшения решения – необходимо освоить три основных элемента:
· способ определения какого – либо первоначального допустимого базисного решения задачи;
· правило перехода к лучшему (точнее, не худшему) решению;
· критерий проверки оптимальности найденного решения.
III
Задание:
Решить задачу симплексным методом.
Z(x)=x1-x2+x3→ max
При ограничениях:
4x1+2x2+x3≥ 6
-x1+x2+x3= 1
x1-x2+4x3≤ 24
Учитывая условия неотрицательности:
xj ≥ 0 , j=1,2,3
Для нахождения первоначального базисного решения разобьем переменные на две группы – основные и свободные. В качестве основных переменных на первом шаге следует выбирать такие mпеременные, каждая из которых входит только в одно из mуравнений системы, в которые не входит не одна из этих переменных. Свободные переменные удовлетворяют этому правилу.
Iшаг:
Основные переменные: х2, х4, х5
Свободные переменные: х1, х3
С помощью дополнительных неотрицательных переменных перейдём к системе уравнений:
x2=1+x1-x3
x4=-4+6x1-3x3
x5=25+3x3
Получим первое базисное решение, которое является недопустимым т.к. присутствует отрицательный компонент
X1=(0,1,0,-4,25) – недопустимое базисное решение.
х3=min{1,∞,}=1
IIШаг
Основные переменные: х1, х2, х5
Свободные переменные: х3, х4
Выразимновыеосновныепеременныечерезнеосновные: х1=2/3+х3/2+х4/6
x2=5/3+x3/2+x4/6
x5=25+x3
Получим второе базисное решение, которое является допустимым т.к. отрицательных компонентов нет.
X2=(,,0,0,25) – допустимое базисное решение.
Выражаем линейную функцию через неосновные переменные:
Z(x)=2/3+x3/2+x4/6-5/3-x3/2-x4/6+25+x3=24+x3=24.
Так как в выражении линейной функции через неосновные переменные отсутствуют отрицательные коэффициенты при неосновных переменных, то решение оптимально.
продолжение
--PAGE_BREAK--Транспортная задача линейного программирования
Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача – это задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления.
Исходные данные транспортной задачи записываются в таблице вида:
b1
b2
…
bn
a1
c11
c12
…
c1n
a2
c21
c22
…
c2n
…
…
…
…
…
am
cm1
cm2
…
cmn
Где ai– объемы поставок, bj– объемы потребления, сmn– стоимости перевозок.
Переменными транспортной задачи являются xij– объемы перевозок от каждого i-го поставщика каждому j-му потребителю. В рассмотренной задаче предполагается, что суммарные запасы поставщиков равны суммарным запасам потребителей, такая задача называется задачей с правильным балансом, а ее модель – закрытой. Если же равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель – открытой. Для того, чтобы транспортная задача имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т. е. задача должна бать с правильным балансом.
Метод северо-западного угла
Согласно данному методу запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика. Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+ n-1.
Метод минимальной стоимости
Этот метод состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель).
Алгоритм решения транспортных задач методом потенциалов:
· Проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводиться фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок;
· Построить начальное опорное решение, проверить правильность его построения по количеству занятых клеток (их должно быть m+ n— 1);
· Построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений ui+ vj= cijпри xij>=0, которая имеет бесконечное множество решений. Для нахождения частного решения системы одному из потенциалов задают произвольно некоторое значение. Остальные потенциалы считаются по формулам ui= cij— vjи vj= cij— ui.
· Проверить выполнение условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток Dij= ui+ vj— cij, если Dij>=0, то полученное решение считается оптимальным, если нет то подлежит улучшению;
· Перейти к новому опорному решению, на котором значение целевой функции будет меньше. Для этого строят циклы.
IV
Задание:
I
способ: распределение поставок
методом минимальной стоимости.
Распределим поставки методом наименьшей стоимости, посчитаем потенциалы и значение целевой функции.
1
2
1
3
-2
200
400
100
200
100
300
200
1
1
12
2
5
200
[-1]
1
100
2
3
8
4
7
=0=
100
3
200
3
5
4
6
9
[-1]
=0=
200
2
400
4
4
3
8
2
100
=0=
300
1
400
5
3
7
10
1
300
100
F=3000
-1
1
2
-1
-3
200
400
100
200
100
300
200
1
1
12
2
5
200
2
100
2
3
8
4
7
100
=0=
4
200
3
5
4
6
9
200
=0=
3
400
4
4
3
8
2
100
=0=
300
2
400
5
3
7
10
1
300
100
F=2600
Клеток с отрицательными потенциалами нет, значит, мы нашли оптимальный план распределения поставок. Fmin= 2600
II
способ: распределение поставок
методом северо-западного угла
1
2
1
6
-1
200
400
100
200
100
300
200
1
7
12
2
5
200
[-4]
1
100
2
3
8
4
7
=0=
100
=0=
3
200
3
5
4
6
9
[-1]
200
[-3]
2
400
4
4
3
8
2
100
100
200
=0=
[-1]
1
400
5
3
7
10
1
100
300
F=4800
Распределим поставки методом северо-западного угла, посчитаем потенциалы и значение целевой функции.
-1
1
2
-1
-2
200
400
100
200
100
300
200
1
7
12
2
5
200
2
100
2
3
8
4
7
100
=0=
4
200
3
5
4
6
9
200
=0=
3
400
4
4
3
8
2
300
100
=0=
[-1]
2
400
5
3
7
10
1
100
300
F=2900
-1
1
2
-1
-3
200
400
100
200
100
300
200
1
7
12
2
5
200
2
100
2
3
8
4
7
100
=0=
4
200
3
5
4
6
9
200
=0=
3
400
4
4
3
8
2
100
300
2
400
5
3
7
10
1
300
100
F=2600
Клеток с отрицательными потенциалами нет, значит мы нашли оптимальный план распределения поставок. Fmin=2600
Транспортная задача с ограничениями на пропускную способность
Если требуется при решении транспортной задачи ограничить перевозки от поставщика с номером lк потребителю с номером k. Возможны ограничения двух типов xlk>= aи xlk=
1. Если xlk>= a, то необходимо, прежде чем решать задачу, сократить запасы l-го поставщика и запросы k-го потребителя на величину а (зарезервировать перевозку xlk= a). В полученном оптимальном решении следует увеличить объем перевозки xlkна величину а.
2. Если xlk= продолжение
--PAGE_BREAK--
V
Задание:
I
способ: распределение поставок
методом минимальной стоимости
x21== 1000
1000
1000
2000
2000
500
5
6
3
8
1000
1
1
2
3
1500
2
5
4
4
2000
6
3
5
9
Вместо 1 потребителя вводим двух других. Сокращаем запасы 4 поставщика и запросы 4 потребителя на 1000.
500
1000
2000
1000
500
500
5
6
3
8
5
1000
1
1
2
3
M
1500
2
5
4
4
2
1000
6
3
5
9
6
Решаем транспортную задачу как обычно.
Данная задача с неправильным балансом, добавляем фиктивного потребителя с потребностями равными 1000, и стоимостями перевозок равными 0. Распределим поставки методом наименьшей стоимости, посчитаем потенциалы и значение целевой функции.
V1 = 1
V2 = 1
V3 = 3
V4 = 3
V5 = 1
500
1000
2000
1000
500
U1 = 0
500
5
6
500 3
8
5
U2 =
1000
500 1
500 1
-1 2
3
M
U3 = 1
1500
2
5
1000 4
4
500 2
U4 = 2
1000
6
500 3
500 5
9
6
U5 = -3
1000
1000 0
F=11500
V1 = 1
V2 = 1
V3 = 2
V4 = 2
V5 = 0
500
1000
2000
1000
500
U1 = 1
500
5
6
500 3
8
5
U2 =
1000
500 1
0 1
500 2
3
M
U3 = 2
1500
-1 2
5
1000 4
4
500 2
U4 = 2
1000
6
1000 3
5
9
6
U5 = -2
1000
0
1000 0
F=11000
V1 = 1
V2 = 1
V3 = 2
V4 = 2
V5 = 0
500
1000
2000
1000
500
U1 = 1
500
5
6
500 3
8
5
U2 =
1000
1
0 1
1000 2
3
M
U3 = 2
1500
500 2
5
500 4
4
500 2
U4 = 2
1000
6
1000 3
5
9
6
U5 = -2
1000
0
1000 0
Клеток с отрицательными потенциалами нет, значит мы нашли оптимальный план распределения поставок. Fmin= 10 500
Запишем оптимальное решение исходной задачи. Для этого увеличим объем перевозки x44 на 1000 единиц и объединим объемы перевозок 1 и 5 потребителя. Получим
1000
1000
2000
2000
500
5
6
500 3
8
1000
1
1
1000 2
3
1500
1000 2
5
500 4
4
2000
6
1000 3
5
1000 9
1000
1000 0
F= 19 500
II
способ: распределение поставок
методом северо-западного угла
Распределим поставки методом северо-западного угла, посчитаем потенциалы и значение целевой функции.
V1 = 7
V2 = 7
V3 = 5
V4 = 9
V5 = 9
500
1000
2000
1000
500
U1 = -2
500
500 5
6
3
8
5
U2 = -6
1000
1
1000 1
2
3
M
U3 = -1
1500
-4 2
-1 5
1500 4
-4 4
-6 2
U4 = 0
1000
-1 6
-4 3
500 5
500 9
-3 6
U5 = -9
1000
500 0
500 0
продолжение
--PAGE_BREAK--