Выбераем разрешающий элемент
СОДЕРЖАНИЕ
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 |
Переходим к следующему улучшению, т.к. в строке С есть отрицательные элементы.