Выбераем разрешающий элемент
СОДЕРЖАНИЕ
1.Задача линейного программирования. Симплекс метод
2. Транспортная задача
3. Динамическое программирование
4. Сетевое планирование и управление
Задача линейного программирования. Симплекс метод.
Автопредприятие имеет n автомобилей и отправляет их на m маршрутов. Для погрузки и выгрузки предприятие и клиенты располагают погрузочно-разгрузочной техникой: автокранами – , автопогрузчиками –
, стационарными кранами –
, кранами на гусеничном ходу –
. Затраты времени на оборот автомобиля на маршрутах соответственно
,
,
,
, затраты времени на выполнение погрузочно-разгрузочных работ техникой: в – автокранами, p – автопогрузчиками, ф – стационарными кранами, г – кранами на гусеничном ходу.
Решить задачу как оптимизационную по максимальному использованию имеющейся техники.
Виды техники | Маршруты, m | ∑ | |||
Автомобили | 220/ ![]() | 170/ ![]() | 50/ ![]() | 190/ ![]() | |
Автокраны | 75/ ![]() | 105/ ![]() | 30/ ![]() | 60/ ![]() | |
Автопогрузчики | 65/ ![]() | 60/ ![]() | 75/ ![]() | 45/ ![]() | |
Стационарные Краны | 65/ ![]() | - | - | - | |
Краны на гусеничном ходу | - | - | 100/ ![]() | - |
Выразив автокраны, автопогрузчики, стационарные краны и краны на гусеничном ходу через автомобили получаем следующие неизвестные:
X1, X2, X3, X4 – количество автомобилей на первом, втором, третьем и четвертом маршрутах соответственно.
Составляем систему ограничений
+
+
+
≤ 170
0.34 + 0.61
+ 0.6
+ 0.31
≤ 9
0.29 + 0.35
+ 1.5
+ 0.23
≤ 13
0.29 ≤ 14
2 ≤ 6
Составляем функцию цели
X1+X2+X3+ X4 + 0.34X1 + 0.61X2 +0.6X3 + 0.31X4 + 0.29X1 + 0.35X2 + 1.5X3 + 0.23X4 +0.29X1 +2X3
MAX
1.92 + 1.45
+ 5.1
+ 1.54
MAX
Из неравенств составляем равенства
+
+
+
+
= 170
0.34 + 0.61
+ 0.6
+ 0.31
+
= 9
0.29 + 0.35
+ 1.5
+ 0.23
+
= 14
0.29 +
= 4
2 +
= 6
Где ,
,
,
,
– количество неиспользованной техники соответственно
Выразим неиспользованную технику из уравнений
= 170 – (
+
+
+
)
= 9 – (0.13
+ 0.11
+ 0.3
+ 0.25
)
= 14 – (0.2
+ 0.13
+ 0.95
+ 0.21
)
= 4– 0.2
= 6 – 1.15
Функцию цели приравниваем к 0
F = 1.92 + 1.45
+ 5.1
+ 1.54
MAX
F = - 1.92 - 1.45
- 5.1
- 1.54
= 0
Составляем первую симплекс таблицу
В первую симплекс таблицу заносятся коэффициенты при свободных неизвестных из системы уравнений. Все известные в системе уравнений делятся на свободные и базисные.
- ![]() | - ![]() | - ![]() | - ![]() | ||
![]() | |||||
![]() | 0.34 | 0.61 | 0.6 | 0.31 | |
![]() | 0.29 | 0.35 | 1.5 | 0.23 | |
![]() | 0.23 | ||||
![]() | |||||
C | -1.92 | -1.95 | -5.1 | -1.54 |
Для того, чтобы перейти к новому базисному плану необходимо свободные и базисные поменять местами так, чтобы в конечном результате C ≥ 0.
Произведем улучшение начального базисного плана, для этого необходимо найти такие базисную и свободную, которые необходимо поменять местами, а в результате будет получена новая матрица с новым планом. Для этого существует алгоритм симплекс метода:
Выбераем разрешающий элемент
1.1 Выбираем разрешающий столбец. Находим в строке С наибольший по модулю отрицательный элемент (-3,4) и покажем им разрешающий столбец.
1.2 Выбираем разрешающую строку. Для этого рассмотрим все положительные элементы разрешающего столбца. 0 и отрицательные элементы не рассматриваются. Делим свободные члены на элемент разрешающего столбца а данной стороке. Минимальное из отношений показывает на разрешающую строку.
На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент.
Разрешающий элемент показывает, какую свободную и базисную необходимо поменять местами.
2. В новой матрице элемент, стоящий на месте разрешающего элемента предыдущей матрицы получается путем деления единицы на разрешающий элемент: =
,
- разрешающий элемент.
Остальные элементы, стоящие на месте разрешающей строки определяются делением соответствующих элементов предыдущей матрицы на разрешающий элемент: =
,
- элемент разрешающей строки.
Остальные элементы, стоящие на месте разрешающего столбца определяются аналогично, но знак меняется на противоположный:
=
,
- элемент разрешающего столбца.
Все другие элементы новой матрицы определяются по формуле:
=
– соответствующий элемент предыдущей матрицы
- элемент предыдущей матрицы, стоящий на пересечении строки i рассматриваемого элемента и разрешающего столбца.
- элемент предыдущей матрицы, стоящий на пересечении разрешающей строки и столбца j рассматриваемого элемента.
Улучшения производятся до тех пор, пока в С строке не будет отрицательных элементов.
Вторая симплекс таблица
-X1 | -X2 | -X3 | -X4 | ||
Y1 | -0.5 | ||||
Y2 | 0.4 | 0.61 | -0.3 | 0.31 | 7.2 |
Y3 | 0.29 | 0.35 | -0.75 | 0.23 | |
Y3 | 0.23 | ||||
X3 | 0.5 | 0.3 | |||
C | -1.92 | -1.95 | 2.55 | -1.54 | 30.6 |
Переходим к следующему улучшению, т.к. в строке С есть отрицательные элементы.