Приведите пример задачи линейного программирования, множеством оптимальных решений которой является луч. Ответ обоснуйте

Приведите пример задачи линейного программирования, множеством оптимальных решений которой является отрезок. Ответ обоснуйте.

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

Задачи линейного программирования

Можно нарисовать бесконечную трапецию с угловыми точками A(2, 0), B(4, 2) и бесконечным лучом вправо x2 = 2: (4, 2), (5, 2)...(10, 2)....

Нарисовав вектор vz(-2, 1) целевой функции и обозначив линии уровня целевой функции (перпендикулярные вектору линии), то сразу видно, что оптимальное решение в точке (2, 0) и z(2, 0) = -4.

Можно нарисовать бесконечную трапецию с угловыми точками A(2, 0), B(4, 2) и бесконечным лучом вправо x2 = 2: (4, 2), (5, 2)...(10, 2)....

Нарисовав вектор vz(-1, 1) целевой функции и обозначив линии уровня целевой функци (перпендикулярные вектору линии), то сразу видно, что оптимальное решение будетдостигаться на отрезке [A,B] A(2, 0), B(4, 2), так как первая (максимальная) линия уровня проходит через этот отрезок.

z = 3x2 → max

−x1 + x2 + 2 ≤ 0

x2 ≤ 2

x1 ≥ 0; x2 ≥ 0

Можно нарисовать бесконечную трапецию с угловыми точками A(2, 0), B(4, 2) и бесконечным лучом вправо x2 = 2: (4, 2), (5, 2)...(10, 2)....

Нарисовав вектор vz(0, 3) целевой функции и обозначив линии уровня целевой функци (перпендикулярные вектору линии), то сразу видно, что оптимальное решение будет достигаться на луче из точки B направо параллельно оси Ox1, где B(4, 2), так как первая

(максимальная) линия уровня проходит через этот луч.

102. Приведите к стандартной форме задачу линейного программирования, уменьшив число переменных:

Из последнего уравнения получаем x1 = −4x2 − 3x3 + 1 ≥ 0 и подставляем вместо

x1 выражения правой части в первые два неравенства и в целевую функцию, получим

задачу:

z = x3 + 3(−4x2 − 3x3 + 1) + 5x2 → max

(−4x2 − 3x3 + 1) + 5x2 + x3 ≥ 3

(−4x2 − 3x3 + 1) + x2 + 8x3 ≥ 7

−4x2 − 3x3 + 1 ≥ 0

x1 ≥ 0; x2 ≥ 0

Приведя слагаемые и упростив выражения, получим:

z = −8x3 − 7x2 + 3 → max

x2 − 2x3 ≥ 2

−3x2 + 5x3 ≥ 6

−4x2 − 3x3 + 1 ≥ 0

x1 ≥ 0; x2 ≥ 0

103. Приведите к канонической форме задачу линейного программирования:

z = x3 + 2x1 + 3x2 → max

x1 + 2x2 + 3x3 ≥ 8

x1 + 5x2 + x3 ≥ 4

x1 + 2x2 + 7x3 = 5

x1 ≥ 0; x2 ≥ 0; x3 ≥ 0

Введем новые переменные

x4 = x1 + 2x2 + 3x3 − 8 ≥ 0

x5 = x1 + 5x2 + x3 − 4 ≥ 0

и используем их в первых двух неравентсвах, приведя задачу к канонической форме:

z = x3 + 2x1 + 3x2 → max

x1 + 2x2 + 3x3 = 8+x4

x1 + 5x2 + x3 = 4+x5

x1 + 2x2 + 7x3 = 5

x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0; x5 ≥ 0

Дата добавления: 2015-03-31