УПРАЖНЕНИЯ 7.1.2
1. Представленные ниже системы уравнений а) и б) имеют единственные базисные решения, система в) - бесконечно много решений, а г) не имеет решения. Докажите это, представив решения графически на плоскости. На основании данных примеров выведите общие закономерности, определяющие у системы уравнений единственное решение, бесконечно много решений или отсутствие решений.
а) в)
х,+3х, = 2, Зх,+х2 = 3. 2х, + 6х2 = 4, х, + 3х2 = 2.
б) г)
2*, + Зх2 = 1, 2х,-х2 = 2. 2л;, - 4х2 = 2, -х, + 2х2 = 1.
Определите графически, какая из следующих систем уравнений имеет единственное решение, бесконечно много решений или не имеет решений.
а) в) Д)
1 -з)Ц (l, -1
г) е)
<\ О
3. Дана следующая система уравнений.
Определите, какой из следующих наборов векторов образует базис.
a) (Р„ Р2, Р3)
b) (Р„ Р2, Р4)
c) (Р2,Р3,Р4)
d) (Р„ Р2, Р3, Р4)
4. Истинны или ложны следующие утверждения?
a) Если матрица В не вырождена, то система ВХ = b имеет единственное решение.
b) Система ВХ = b не имеет решения, если матрица В вырождена и вектор b независим относительно векторов, составляющих матрицу В.
c) Система ВХ = b имеет бесконечно много решений, если матрица В вырождена и вектор b зависим относительно векторов, составляющих матрицу В.
7.1.2. Матричное представление симплекс-таблиц
В этом разделе мы используем матричную алгебру для построения симплекс-таблиц. Рассмотрим стандартную задачу ЛП
максимизировать г = СХ при ограничениях АХ = b, X > 0.
Эту задачу ЛП можно также записать следующим образом.
Для любой симплексной итерации будем обозначать через Хв базисный вектор переменных, а через Св - вектор коэффициентов целевой функции, соответствующих этому базису. Поскольку все небазисные переменные равны нулю, стандартная задача ЛП будет сведена к задаче с целевой функцией г = СВХВ и ограничениями ВХВ = Ь, где текущее решение удовлетворяет следующему уравнению.
ся в-] | | с, в-V |
В" ; | | , в-ь , |
Здесь при обращении матрицы использовались формулы из раздела А.2.7.
Симплекс-таблица получается из исходной задачи ЛП путем вычислений по следующей формуле.
С, В
-С А
Выполнив вычисления по этой формуле, получаем такую симплекс-таблицу.
Базис | | Решение |
| С8В"1Р;-С, | CsB"1b |
В"1 Р,
В этой таблице необходимо вычислить только обратную матрицу В-1, так как другие элементы таблицы получаются из исходных данных задачи.
Представленная симплекс-таблица имеет большое значение, так как является основой всех вычислительных алгоритмов линейного программирования. В частности, на ней основаны модифицированный симплекс-метод, метод решения задач с ограниченными переменными и метод декомпозиции, которые будут описаны в следующих разделах.
Пример 7.1.3
Рассмотрим следующую задачу ЛП.
Максимизировать г = дс, + 4х2 + 7х3 + 5х4
при ограничениях
2хх +хг + 2х3 + 4.х4 = 10, 3*, - х2 - 2х3 + 6xt = 5, х„ х2, х3, xt>0. Пусть В = (Р,, Р2) является допустимым базисом.
На основании В = (Р,,Р2) имеем Х, = (х,,х/ и Св = (1,4). Вычисляем обратную матрицу В"1:
Находим текущее базисное решение
3 -1
х.=Г I = в ь =
5 5 3 2 v5 5J
Далее вычисляем в симплекс-таблице значения коэффициентов ограничений:
(±0(2 1 2 Л) (1 0 0 2 В"(Р„Р,.Р,,Р4)= < 5
1 " 3 4 1 -МЗ -1 -2 6 [0 1 2 0
Теперь находим коэффициенты г-строки симплекс-таблицы:
Св[В-,(Р1.Р2,Рз,Р4)]-С = (1,4) ° ° -(1,4,7,5) = (0.0.1.-3). Наконец, вычисляем значение целевой функции:
г = СйВ-,Ь = СвХв=(1,4)
= 19 ,
Таким образом, получаем значения следующей симплекс-таблицы.
Еще раз подчеркнем, что в этой таблице основные вычисления связаны с нахождением обратной матрицы В-1, другие элементы таблицы получаются на основе вычисленной матрицы В"1 и исходных данных задачи.
УПРАЖНЕНИЯ 7.1.3
1. Пусть в примере 7.1.3 В = (Р3, Р4). Покажите, что соответствующее базисное решение является допустимым и постройте соответствующую симплекс-таблицу.
2. Дана следующая задача ЛП.
Максимизировать г = 5xt + 12х2 + 4х3
при ограничениях
х, + 2х2 + х3 + х4 = 10,
3* 4 ~
Определите, какие из следующих наборов векторов образуют базис: (Р,, Р2),
(р2, р3), (р3, р4).