- •Практикум решения задач по дисциплине «Системный анализ»
- •Решение задач Линейного программирования графическим методом
- •1.1 Задача 1
- •Задача 2
- •Задача 3
- •Задача 4
- •Задача 5
- •Задача 6
- •Решение задач Линейного программирования симплекс-методом
- •2.1 Алгоритм 1 Симплекс преобразования на основе укороченных симплекс таблиц
- •2.2 Алгоритм 2 Симплекс преобразования на основе укороченных симплекс таблиц
- •2.3 Алгоритм 3 Симплекс преобразования на основе укороченных симплекс таблиц для решения двойственной задачи Линейного программирования
- •2.4 Задача 1
- •2.5 Задача 2
- •2.6 Задача 3
- •2.7 Задача 4
- •Решение матричных игр 2 X n и m X 2 графоаналитическим методом
- •3.1 Задача 1 ( решение игры 2 X n)
- •3.2 Задача 2 ( решение игры m X 2)
- •3.3 Задача 3
2.7 Задача 4
Для заданной задачи линейного программирования составить двойственную задачу Линейного программирования и решить ее Симплекс методом:
Решение
-
Для заданной задачи Линейного программирования Двойственная Задача Линейного программирования выглядит следующим образом:
-
Строим симплекс таблицу для заданной двойственной задачи Линейного программирования
СП БП |
C |
|||
3 |
-1 |
3 |
-1 |
|
-2 |
2 |
2 |
-2 |
|
T |
6 |
4 |
12 |
0 |
-
Выбираем разрешающую строку k , соответствующую наименьшему отрицательному элементу в С столбце
Следовательно, k=2.
СП БП |
C |
|||
3 |
-1 |
3 |
-1 |
|
-2 |
2 |
2 |
-2 |
|
T |
6 |
4 |
12 |
0 |
-
Выбираем разрешающий столбец l, который соответствует наименьшему положительному из отношений элементов T-строки на соответствующие элементы разрешающей строки:
Следовательно, l=2.
СП БП |
C |
|||
3 |
-1 |
3 |
-1 |
|
-2 |
2 |
2 |
-2 |
|
T |
6 |
4 |
12 |
0 |
-
Элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом : 2
-
Переходим к новой симплекс таблице по следующим правилам:
-
Меняем местами СП и БП соответствующие разрешающему элементу.
-
СП БП |
C |
|||
|
|
|
|
|
|
|
|
|
|
T |
|
|
|
|
-
На месте разрешающего элемента в новой таблице стоит величина ему обратная:
СП БП |
C |
|||
|
|
|
|
|
|
|
|
||
T |
|
|
|
|
-
Все элементы разрешающей строки делятся на разрешающее число с обратным знаком, включая элемент последнего столбца:
СП БП |
C |
|||
|
|
|
|
|
1 |
-1 |
1 |
||
T |
|
|
|
|
-
Все элементы разрешающего столбца делятся на разрешающее число, включая элемент последней строки:
СП БП |
C |
|||
|
|
|
||
1 |
-1 |
1 |
||
T |
|
2 |
|
|
-
Все остальные элементы матрицы вычисляются по формулам:
Например, вычислим некоторые элементы таблицы :
Полученная СТ2 следующая:
СП БП |
C |
|||
2 |
4 |
-2 |
||
1 |
-1 |
1 |
||
T |
10 |
2 |
8 |
4 |
-
В С столбце есть отрицательные элементы ( -2), поэтому оптимальное решение не найдено и необходимо сделать еще одно симплекс преобразование.
-
Выбираем разрешающую строку k , соответствующую наименьшему отрицательному элементу в С столбце
Следовательно, k=1.
СП БП |
C |
|||
2 |
4 |
-2 |
||
1 |
-1 |
1 |
||
T |
10 |
2 |
8 |
4 |
-
Выбираем разрешающий столбец l, который соответствует наименьшему положительному из отношений элементов T-строки на соответствующие элементы разрешающей строки:
Следовательно, l=3.
СП БП |
C |
|||
2 |
4 |
-2 |
||
1 |
-1 |
1 |
||
T |
10 |
2 |
8 |
4 |
-
Элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом :
-
Переходим к новой симплекс таблице по следующим правилам:
-
Меняем местами СП и БП соответствующие разрешающему элементу.
-
СП БП |
C |
|||
|
|
|
|
|
|
|
|
|
|
T |
|
|
|
|
-
На месте разрешающего элемента в новой таблице стоит величина ему обратная:
СП БП |
C |
|||
|
|
|
||
|
|
|
|
|
T |
|
|
|
|
-
Все элементы разрешающей строки делятся на разрешающее число с обратным знаком, включая элемент последнего столбца:
СП БП |
C |
|||
|
|
|
|
|
T |
|
|
|
|
-
Все элементы разрешающего столбца делятся на разрешающее число, включая элемент последней строки:
СП БП |
C |
|||
|
|
|
||
T |
|
|
2 |
|
-
Все остальные элементы матрицы вычисляются по формулам:
Например, вычислим некоторые элементы таблицы :
Полученная СТ3 следующая:
СП БП |
C |
|||
T |
6 |
3 |
2 |
8 |
-
Все элементы С столбца положительные, следовательно оптимальное решение найдено.
-
Введем соответствие между СП и БП Прямой и Двойственных задач Линейного программирования
СП |
|
|
БП |
|||||
|
|
|||||||
↕ |
↕ |
↕ |
|
|
↕ |
↕ |
||
|
|
|||||||
БП |
|
|
СП |
Транспонируя симплекс таблицу для двойственной задачи ЛП и вводя переменный xi вместо переменных (±yi), получаем оптимальный план решения прямой задачи – необходимо смотреть соответствующие значения в столбце свободных членов.
СП БП |
B |
||
2 |
|||
Z |
8 |
Таким образом, оптимальное решение – максимум целевой функции Z =8 - достигается при , Это полностью совпадает с результатом решения прямой задачи Линейного Программирования ( см. Задачу 1)
Ответ: Zmax=8 при этом ,