1.3. Базисные решения.

Изучаемые вопросы:

• Свободные и базисные переменные;

• Построение двойственных переменных, соответствующих данному базисному решению.

Заметим, что ограничения задачи линейного программирования в канонической форме i = 1, 2,…,mзадают системуmуравнений сnнеизвестными. Допустим, чтоn >mи ранг матрицы этой системы равенm. Среди бесконечного множества решенийбазисные решенияэтой системы получаются следующим образом: (n -m) переменных приравняем 0. Эти переменные назовемсвободными. Значения остальных переменных получаем из решения системы относительноmостальных переменных. Эти переменные назовембазисными. Базисное решение называетсядопустимым, если оно неотрицательно.

По каждому допустимому базисному решению прямой задачи найдем значения двойственных переменных y₁,y₂, …,y_m. Для этого все ограничения двойственной задачи, соответствующие базисным переменнымx_j, заменим равенствами

: .

Решение полученной системы определяет теневые цены, соответствующие данному базисному решению.

Пример 1.3.1

Запишем систему ограничений прямой задачи

, (1.1.11)

(1.1.12)

и двойственной задачи

, (1.2.10)

, (1.2.11)

, (1.2.12)

. (1.2.13)

1. Пусть x₁,x₂– свободные переменные (т.е.x₁ =x₂ = 0). Тогда базисные переменныеs₁иs₂найдем из системы (11),(12) приx₁ =x₂= 0. Отсюда следует, что базисные переменныеs₁= 1000,s₂= 25.

Таким образом, базисный план имеет вид: x₁ =0,x₂ = 0,s₁ =1 000,s₂ = 25.

Он означает, что продукция не производится. В этом случае выручка составит: Z= 40x₁+ 100x₂= 0

Найдем теперь теневые цены, соответствующие этому базисному решению.

Все ограничения двойственной задачи, соответствующие базисным переменным s₁, s₂заменим равенствами, т.е.

, (1.2.10)

, (1.2.11)

, (1.2.12)

. (1.2.13)

Отсюда следует, что y₁ =0, y₂ =0 . Найдем величины:

₁ = 5y₁+ 0,1y₂– 40 = -40,

₂ = 10y₁+ 0,3y₂- 100 = -100,

т.е. оба производства прибыльны: единица первого продукта увеличивает выручку на 40, а второго – на 100.

2. Пусть s₁,s₂– свободные переменные (т.е.s₁ =s₂ = 0). Тогда базисные переменныеx₁иx₂найдем из системы

5x₁+ 10x₂= 1000,

0,1x₁+ 0,3x₂= 25.

Отсюда следует, что базисные переменные x₁ = 100, x₂ = 50. Таким образом, базисное решение имеет вид: x₁ = 100, x₂ = 50, s₁ = 0, s₂ = 0.

Найдем теперь теневые цены, соответствующие этому базисному решению. Все ограничения двойственной задачи, соответствующие базисным перемен-ным x₁,x₂, заменим равенствами, т.е.

, (1.2.10)

, (1.2.11)

, (1.2.12)

. (1.2.13)

Отсюда следует, что y₁ =4, y₂ = 200. Значения приведенных затрат ₁ = 0, ₂ = 0, т.е. оба производства рентабельные. Двойственные переменные y₁ = 4, y₂ = 200 являются допустимым решением двойственной задачи. Заметим, что решение прямой задачи x₁ = 100, x₂ = 50, s₁=0, s₂=0.

и решение двойственной задачи y₁ =4, y₂ = 200 являются допустимыми решениями. Значения целевых функций равны:

Z=40∙100 + 100∙50 = 9000,W=1000∙4 + 25∙200=9000.

Вопросы для самопроверки

1. Какие переменные называются свободными?

12. Какие переменные называются базисными?

13. Какое базисное решение является допустимым?