ВУЗы и колледжи

Помогите пожалуйста Решить задачу линейного программирования графическим способом:

F=2x1+2x2->min
x1+x2 больше или равно 1
-x1+x2 меньше или равно 1
x1=0, x2=1

min=2
Наташа Шубара
Наташа Шубара
80 220
Лучший ответ
В инете полно калькуляторов, решающих подобные задачи, причем, с подробным отчетом.
Гугли.
А вообще, именно здесь вообще нечего наводить тень на плетень...
Ты ищешь МИНИМУМ функции F= 2*(х1+х2). С другой стороны, в первом ограничении стоит пропорциональное выражение: х1+х2≤1. Его минимум равен 1. Иными словами, х1+х2=1. Минимум функции, соответственно, равен 2.
Можно подставить выразить одну переменную через другую и подставить в другое ограничение и посмотреть, что же там получается:
х1≥0; х2≤1.
Таким образом, решением будет любая комбинация, удовлетворяющая этой паре неравенств и уравнению х1+х2=1.
Например: (0;1); (1/2;1/2); (1;0); (2;-1) и т. д. Решений - бесконечно много.
Светлана Марченко К тому же там в вопросе речь идет о графическом способе решения, а не аналитическом.
Для наглядности заменяем х1 на х, х2 на у.
По данным ограничениям две полуплоскости - смотри скрин.
F = 2x + 2у -> min
x + у ≥ 1
у - x ≤ 1
Но по смыслу нужно добавить еще два ограничения:
х ≥ 0
у ≥ 0
Иначе можно будет брать отрицательные значения х и у, что противоречит физическому смыслу задач линейной оптимизации - второй скрин.
Получаем область (целевой многоугольник), в которой выполняются все ограничения.
Эта область должна быть ограничена снизу - если нас интересует минимум целевой функции.
Из теории линейной оптимизации известно, что минимум целевой функции лежит в одной из вершин целевого многоугольника (как и максимум, но тогда область должна быть ограничена сверху).
Имеем две вершины:
x=0, y = 1
F = 2x + 2у = 0 + 2 = 2 -> min
или
x = 1, y = 0
F = 2 + 0 = 2 -> min

Получаем две пары решений, в которых минимум целевой функции:

x1=0 x2=1
x1=1 x2=0

Эта задачка - редкий случай, когда всё ребро целевого многоугольника является решением (зелёное). Когда это ребро параллельно прямой х+у=1. Любая точка на этом ребре - есть решение.
Например:
х=0,5, у=0,5
F = 2x + 2у = 2*0,5 + 2*0,5 = 1+1 = 2 -> min
И так любая пара, подходящая под условие: х1+х2=1.
Дмитрий Назаров Добавлять здесь дополнительные ограничения недопустимо. Задача абстрактная, а искусственные условия неотрицательности переменных "убивают" большую часть решений.