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