- •Содержание
- •Введение
- •1. Содержание и порядок выполнения расчетно – графической работы
- •2. Разбор типового задания Техническая постановка задачи
- •Математическая постановка задачи
- •Приведение задачи к канонической форме
- •Нахождение начального опорного плана
- •Постановка l- задачи
- •Решение l- задачи
- •0 Итерация
- •Формирование начального опорного плана исходной злп
- •Решение исходной злп первым алгоритмом симплекс-метода Описание первого алгоритма симплекс-метода
- •Порядок вычислений по первому алгоритму:
- •Решение исходной задачи
- •Формирование м-задачи
- •Решение м-задачи вторым алгоритмом симплекс-метода Описание второго алгоритма симплекс-метода
- •Порядок вычислений по второму алгоритму
- •Решение м-задачи
- •Постановка двойственной задачи
- •Формирование решения двойственной задачи
- •3. Индивидуальные задания
- •Список литературы
Постановка l- задачи
В нашем случае ЗЛП (2.15)-(2.16) имеет матрицу условий
Она уже содержит три столбца которые можно использовать для построения единичного базиса. Недостаёт лишь одного столбца. Поэтому в нашем случае следует ввести только одну неотрицательную искусственную переменную в левую часть четвёртого уравнения системы ограничений (2.16). Тогда вспомогательная задача для нахождения начального опорного плана задачи (2.15) - (2.16) запишется так:
|
(2.20) |
|
(2.21) |
Определим начальный опорный план полученной задачи. При постановке этой задачи сформирован единичный базис искомого начального опорного плана задачи. Его компоненты являются небазисными и поэтому приравниваются нулю. Тогда из системы ограничений (2.21) найдутся значения базисных компонент
Итак, в качестве начального опорного плана задачи может быть взят вектор
Решение l- задачи
Решение L- задачи будем проводить в соответствии с первым алгоритмом симплекс-метода (описание алгоритма приводится ниже). Составим таблицу, соответствующую исходному опорному плану (0-й итерации). Так как - базис начального опорного плана , является единичной матрицей, то обратная матрица также является единичной и поэтому коэффициентами разложения векторов условий по этому базису являются коэффициенты системы (2.21).
Для заполнения -й строки симплекс-таблицы вычислим значения линейной формы и оценок , векторов условий по приведённым в описании первого алгоритма формулам (см. раздел 4) следующим образом:
|
Весь процесс решения приведен в табл. 3.1, которая состоит из двух частей, отвечающих 0-й (исходная таблица) и 1-й итерациям.
Заполняем таблицу 0-й итерации.
Среди оценок имеются отрицательные. Значит, исходный опорный план не является оптимальным. Перейдем к новому базису путём операции однократного замещения. В базис будет введён вектор с наименьшей оценкой . Значения вычисляются для всех позиций столбца (так как все элементы разрешающего столбца положительны). Наименьший элемент достигается на четвертой позиции базиса. Значит, четвертая строка является разрешающей строкой, и вектор подлежит исключению из базиса.
Составим таблицу, отвечающую первой итерации.
В столбце , в четвертой позиции место вектора займёт вектор . Соответствующий ему коэффициент линейной формы помещаем в четвертой позиции столбца . Главная часть таблицы 1 заполняется по данным таблицы 0 в соответствии с рекуррентными формулами. Так как после завершения первой итерации все оценки , то полученный опорный план является оптимальным опорным планом L- задачи. Максимальное значение линейной формы задачи равно нулю .
Таблица 2.1
0 Итерация
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
51 |
3 |
5 |
2 |
4 |
1 |
0 |
0 |
0 |
0 |
12 3/4 |
2 |
0 |
|
268 |
22 |
14 |
18 |
30 |
0 |
1 |
0 |
0 |
0 |
8 4/15 |
3 |
0 |
|
106 |
10 |
14 |
8 |
16 |
0 |
0 |
1 |
0 |
0 |
6 5/8 |
4 |
-1 |
|
50 |
22 |
14 |
18 |
30 |
0 |
0 |
0 |
-1 |
1 |
1 2/3 |
m+1 |
- |
- |
-50 |
-22 |
-14 |
-18 |
-30 |
0 |
0 |
0 |
1 |
0 |
|
1 итерация
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
44 1/3 |
1/15 |
3 2/15 |
-2/5 |
0 |
1 |
0 |
0 |
2/15 |
-2/15 |
|
2 |
0 |
|
218 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
-1 |
|
3 |
0 |
|
79 1/3 |
-1 11/15 |
6 8/15 |
-1 3/5 |
0 |
0 |
0 |
1 |
8/15 |
-8/15 |
|
4 |
0 |
|
1 2/3 |
11/15 |
7/15 |
3/5 |
1 |
0 |
0 |
0 |
-1/30 |
1/30 |
|
m+1 |
- |
- |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|