- •Практикум решения задач по дисциплине «Системный анализ»
- •Решение задач Линейного программирования графическим методом
- •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.4 Задача 1
Решить задачу линейного программирования Симплекс методом:
-
Составляем первую укороченную симплекс-таблицу СТ1:
БП СП |
B |
||
3 |
-2 |
6 |
|
-1 |
2 |
4 |
|
3 |
2 |
12 |
|
Z |
-1 |
-2 |
0 |
Все элементы столбца свободных членов положительные, следовательно можно применить “Алгоритм 1 Симплекс преобразования на основе укороченных симплекс таблиц”
-
Выбираем разрешающий столбец l соответствующий наименьшему отрицательному элементу в Z строке:
Следовательно, .
БП СП |
B |
||
3 |
-2 |
6 |
|
-1 |
2 |
4 |
|
3 |
2 |
12 |
|
Z |
-1 |
-2 |
0 |
-
Выбираем разрешающую строку k, которая соответствует наименьшему положительному из отношений элементов правой части уравнений на соответствующие элементы разрешающего столбца:
Следовательно, , так как минимальное положительное отношение соответствует второй строке.
БП СП |
B |
||
3 |
-2 |
6 |
|
-1 |
2 |
4 |
|
3 |
2 |
12 |
|
Z |
-1 |
-2 |
0 |
-
Элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом :
-
Переходим к новой симплекс таблице СТ2 по следующим правилам:
-
Меняем местами СП и БП соответствующие разрешающему элементу.
-
БП СП |
B |
||
|
|
|
|
|
|
|
|
|
|
|
|
Z |
|
|
|
-
На месте разрешающего элемента в новой таблице стоит величина ему обратная:
-
БП СП
B
Z
БП СП |
B |
||
|
|
|
|
|
|
|
|
Z |
|
|
|
-
Все элементы разрешающего столбца делятся на разрешающее число, включая элемент последней строки, с обратным знаком:
БП СП |
B |
||
|
1 |
|
|
|
-1 |
|
|
Z |
|
1 |
|
-
Все остальные элементы матрицы вычисляются по формулам:
Например, вычислим некоторые элементы таблицы :
Полученная СТ2 следующая:
БП СП |
B |
||
2 |
1 |
10 |
|
4 |
-1 |
8 |
|
Z |
-2 |
1 |
4 |
-
В Z строке есть отрицательные элементы (-2), следовательно оптимальное решение не найдено и необходимо выполнить симплекс преобразование для СТ2.
-
Рассмотрим СТ2:
БП СП |
B |
||
2 |
1 |
10 |
|
4 |
-1 |
8 |
|
Z |
-2 |
1 |
4 |
-
Выбираем разрешающий столбец l соответствующий наименьшему отрицательному элементу в Z строке:
Следовательно, .
БП СП |
B |
||
2 |
1 |
10 |
|
4 |
-1 |
8 |
|
Z |
-2 |
1 |
4 |
-
Выбираем разрешающую строку k, которая соответствует наименьшему положительному из отношений элементов правой части уравнений на соответствующие элементы разрешающего столбца:
Следовательно, , так как минимальное положительное отношение соответствует третьей строке.
БП СП |
B |
||
2 |
1 |
10 |
|
4 |
-1 |
8 |
|
Z |
-2 |
1 |
4 |
-
Элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом :
-
Переходим к новой симплекс таблице СТ2 по следующим правилам:
-
Меняем местами СП и БП соответствующие разрешающему элементу.
-
БП СП |
B |
||
|
|
|
|
|
|
|
|
|
|
|
|
Z |
|
|
|
-
На месте разрешающего элемента в новой таблице стоит величина ему обратная:
БП СП |
B |
||
|
|
|
|
|
|
|
|
|
|
||
Z |
|
|
|
-
Все элементы разрешающей строки делятся на разрешающее число, включая элемент последнего столбца:
БП СП |
B |
||
|
|
|
|
|
|
|
|
2 |
|||
Z |
|
|
|
-
Все элементы разрешающего столбца делятся на разрешающее число, включая элемент последней строки, с обратным знаком:
БП СП |
B |
||
-1 |
|
|
|
|
|
||
2 |
|||
Z |
|
|
-
Все остальные элементы матрицы вычисляются по формулам:
После вычисления всех элементов таблицы СТ3 выглядит так:
БП СП |
B |
||
-1 |
2 |
2 |
|
3 |
|||
2 |
|||
Z |
8 |
-
В Z строке нет отрицательных элементов, следовательно, оптимальное решение найдено и максимум целевой функции для заданной системы ограничений равен 8 при этом , (см столбце свободных членов)
Ответ: Zmax=8 при этом ,