Контрольная работа: Линейная алгебра и математическое программирование

B(0,3) 3 C(3, )

2

1 D(3,1) X₁ + 4 X₂ ≤ 12

E(2,0) X₂ ≥ 0

A(0,0) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 X₁

X₁ ≥ 0

Найдем координаты точек A, B, C, D, E. Для этого последовательно решим несколько систем уравнений, образуемых из неравенств системы ограничений задачи линейного программирования.

Для точки А:

Отсюда, , т.е. А(0,0).

Для точки В: отсюда, , Х₂ = 3, т.е. В(0,3).

Для точки C: отсюда, , Х₂ = , т.е. С(3,).

Для точки D: отсюда, , Х₂ = 1, т.е. D(3,1).

Для точки E: отсюда, , Х₁ = 2, т.е. E(2,0).

Координаты точек: A(0,0) , B(0,3), C(3, ), D(3,1), E(2,0)

В соответствии с коэффициентами целевой функцией

z = 4 x₁ + x₂ max

построим вектор ( 4, 1) и прямую 4х₁ + х₂ = 0.

Перемещаем прямую по направлению вектора. Точкой выхода из области допустимых решений является точка С(3,).

В точке С(3,) и будет оптимальное решение (максимальное), то есть при х₁ = 3; х₂ = значение целевой функции будет максимальным

Zmax= 4 * 3 + = 14.

Проверка:

В соответствии с одной из теорем теории линейного программирования линейная функция z = 4 x₁ + x₂ достигает максимального значения в вершинах многогранника, т.е. в точках A(0,0) , B(0,3), C(3, ), D(3,1), E(2,0).

Вычислим значения z = 4 x₁ + x₂ в этих точках:

· z (A(0,0)) = 4*0 + 0 = 0

· z (B(0,3)) = 4*0 + 3 = 3

· z (D(3,1)) = 4*3 + 1 = 13

· z (E(2,0)) = 4*2 + 0 = 8

· z (C(3, )) = 4*3 + = 14. , что и подтверждаем максимальность значения целевой функции.

Задачи 31–40. На трех базах А₁ , А₂ , А₃ имеется однородный груз в количестве а₁ , а₂ , а₃ единиц. Этот груз нужно перевезти в пять пунктов В1, В2, В3, В4, В5 в количестве b1, b2, b3, b4, b5 единиц соответственно. Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов С: