Дайте определение выпуклой оболочки системы точек. Пусть - выпуклая оболочка точек , , , . Принадлежат ли множеству точки: , ? Ответ обоснуйте.
то
есть выполнено условие того, что это
выпуклая линейная комбинация, а значит
X входит в состав выпуклой оболочки.
Предположим, что Y входит также в выпуклую
комбинацию, тогда все точки отрезка
[XY ] должны входить в линейную комбинацию,
но по исходным точкам видно (все они
находятся правей прямой x = -1), что вся
выпуклая комбинация расположена справа
от прямой x =-1, а точка Y - слева, что
подтверждает, что ни весь отрезок [XY ]
ни точка Y - не принадлежат выпуклой
оболочке.
11. Задачи линейного программирования
Приведите пример задачи линейного программирования, имеющей единственное решение. Ответ обоснуйте.
Можно
нарисовать бесконечную трапецию с
угловыми точками 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), так как первая
(максимальная) линия уровня проходит через этот луч.
Приведите к стандартной форме задачу линейного программирования, уменьшив число переменных:
Из последнего уравнения получаем 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