Question

Решить задачу линейного программирования: L max = ₓ₁ + ₓ₂ ₓ₁+2ₓ₂≤10 ₓ₁+2ₓ₂≥2 2ₓ₁+ₓ₂≤10 ₓ₁≥0 ,ₓ₂≥0

Answer 1

Переход к КЗЛП.

F(X) = x1+x2 → max при ограничениях:

x1+2x2≤10

x1+2x2≥2

2x1+x2≤10

x1 ≥ 0, x2 ≥ 0

F(X) = x1+x2

В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.

x1+2x2+x3 = 10

x1+2x2-x4 = 2

2x1+x2+x5 = 10

Переход к СЗЛП.

Расширенная матрица системы ограничений-равенств данной задачи:

1 2 1 0 0 10

1 2 0 -1 0 2

2 1 0 0 1 10

 

 

Приведем систему к единичной матрице методом жордановских преобразований.

1. В качестве базовой переменной можно выбрать x3.

2. В качестве базовой переменной можно выбрать x4.

Получаем новую матрицу:

1 2 1 0 0 10

-1 -2 0 1 0 -2

2 1 0 0 1 10

3. В качестве базовой переменной можно выбрать x5.

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).

Соответствующие уравнения имеют вид:

x1+2x2+x3 = 10

-x1-2x2+x4 = -2

2x1+x2+x5 = 10

Выразим базисные переменные через остальные:

x3 = -x1-2x2+10

x4 = x1+2x2-2

x5 = -2x1-x2+10

Подставим их в целевую функцию:

F(X) = x1+x2

или

F(X) = x1+x2 → max

Система неравенств:

-x1-2x2+10 ≥ 0

x1+2x2-2 ≥ 0

-2x1-x2+10 ≥ 0

Приводим систему неравенств к следующему виду:

x1+2x2 ≤ 10

-x1-2x2 ≤ -2

2x1+x2 ≤ 10

F(X) = x1+x2 → max

Упростим систему.

x1+2x2 ≤ 10

-x1-2x2 ≤ -2

2x1+x2 ≤ 10

F(X) = x1+x2 → max

Если задача ЛП решается на поиск min-го значения, то стандартная форма будет иметь следующий вид:

-x1-2x2 ≤ -10

x1+2x2 ≤ 2

-2x1-x2 ≤ -10

F(X) = -x1-x2 → min

Answer 2

Для решения задачи линейного программирования (ЛП) сначала определим целевую функцию и ограничения, а затем воспользуемся методом симплекс-метода для нахождения оптимального решения.

Целевая функция: L = x₁ + x₂

Ограничения:

1. x₁ + 2x₂ ≤ 10
2. x₁ + 2x₂ ≥ 2
3. 2x₁ + x₂ ≤ 10
4. x₁ ≥ 0
5. x₂ ≥ 0

Преобразуем ограничения 2 и 3 для того, чтобы они имели форму ≤:

2. -x₁ - 2x₂ ≤ -2
3. 2x₁ + x₂ ≤ 10

Составим таблицу симплекс-метода:

luaCopy code
|  Базис  |  x₁  |  x₂  |  Свободный член  |
|---------|------|------|------------------|
|   S₁    |   1  |   2  |        10        |
|   S₂    |   2  |   1  |        10        |
|  -Lmax  |   -1 |  -1  |        0         |

Согласно симплекс-методу, будем искать оптимальное решение, выбирая наибольший коэффициент в строке -Lmax (последняя строка), который соответствует переменной, которую мы добавим в базис. В данной таблице это переменная x₁.

Вычислим отношения свободных членов к коэффициентам x₁ в строках S₁ и S₂:

1. 10 / 1 = 10
2. 10 / 2 = 5

Минимальное значение из этих отношений - 5. Это означает, что переменная x₁ будет вводиться в базис из строки S₂.

Произведем пересчет строк:

luaCopy code
|  Базис  |  x₁  |  x₂  |  Свободный член  |
|---------|------|------|------------------|
|   S₁    |   0  |   3  |        5         |
|    x₁   |   1  | 0.5  |        5         |
|  -Lmax  |   0  |  -1  |       -5         |

Далее, мы будем искать новую переменную для ввода в базис. В данной таблице это переменная x₂, так как ее коэффициент в строке -Lmax наименьший (отрицательный).

Вычислим отношения свободных членов к коэффициентам x₂ в строках S₁ и x₁:

1. 5 / 3 = 1.67
2. 5 / 0.5 = 10

Минимальное значение из этих отношений - 1.67. Это означает, что переменная x₂ будет вводиться в базис из строки S₁.

Произведем пересчет строк:

luaCopy code
|  Базис  |   x₁   |   x₂   |  Свободный член  |
|---------|--------|--------|------------------|
|   x₂    |   0    |   1.5  |       1.67       |
|    x₁   |   1    |  0.33  |       3.33       |
|  -Lmax  |   0    |  -0.5  |      -3.33       |

Теперь в строке -Lmax все коэффициенты неотрицательные, что означает, что мы достигли оптимального решения. Переменные в базисе: x₁ = 3.33, x₂ = 1.67. Значение целевой функции Lmax = 3.33 + 1.67 = 5.

Итак, оптимальное решение задачи линейного программирования:

x₁ = 3.33 x₂ = 1.67 Lmax = 5