|
|
Схема решения задачи (1.1)-(1.3) графическим методом.Стр 1 из 2Следующая ⇒ 1. Записывают уравнения граничных прямых. 2. Строят графики граничных прямых на плоскости. 3. Выделяют область решения неравенств системы (1.2). 4. Строят многоугольник решений. 5. Строят график линейно формы (1.1). 6. Определяют экстремальную точку многоугольника. 7. Вычисляют значение линейной формы в полученной точке. Пример. Используя графический метод, найти максимум линейной формы
при условиях:
Решение. Записывают уравнения граничных прямых и их графики строят на плоскости в выбранной системе координат:
Выделяют область решения каждого неравенства с помощью вспомогательной точки, в качестве которой удобнее всего взять 0(0,0), и как пересечение построенных полуплоскостей строят многоугольник решений Ω.Выражение линейной формы приравнивают любому произвольному числу и строят график, соответствующий полученному уравнению прямой:
Прямая проходит через начало координат
Параллельно перемещая прямую Z в направлении вектора
Известно, что, система двух линейных уравнений с двумя неизвестными
где Матрицы
называется соответственной основной и расширенной матрицами системы (1). Чтобы исключить неизвестное
Если
Знаменатели выражений для неизвестных В нашем случае получим
Ответ: maxZ=50, x1=5, x2=3. При решении задачи линейного программирования графическим методом могут встретиться следующие случаи.
Рис1). Задача имеет единственное решение Рис..2). Задача имеет бесконечное множество решений
Рис.3).Линейная форма не ограниченаРис.4).Система ограничений несовместна
Дана общая задача ЛП:
при условиях:
Вводя 4 добавочных неизвестных
Базис Пусть В итоге получим: min при условиях:
Допустимое базисное решение следующее: Итак, самая «ненадёжная» переменная Из «ненадёжного» уравнения для
находим и подставляем Получим: min при условиях:
Допустимое базисное решение:
При этом
Достигнуто оптимальное решение: Покажем решение данного примера графически.
Рис.2
На координатные оси нанесем систему неравенств (см. пример). Выпуклая область (рис.2) соответствует совокупности решений системы неравенств.Минимальное и максимальное значения целевой функции
  ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
и еще через одну точку, координаты которой легко определить (
; 
(7,5)
, видим, что экстремальной точкой является точка С(5, 3) – точка пересечения прямых 
.
записывается в следующем виде:
- заданные числа из К.
, умножим первое из уравнений на 
, второе на 
и сложим их. В результате получим уравнение
, то из этого уравнения и аналогичного уравнения, получающегося путем исключения 
, получим
здесь одинаковы и представляют собой многочлен от элементов основной матрицы А. Значение этого многочлена называют определителем или детерминантом матрицы А и обозначают 
или 
.
(1)
;
;
;
;
получим каноническую систему уравнений (
базис):
; свободные переменные 
положим их равными 0.
тогда 
В выражении для F можно увеличивать 
при этом F будет уменьшаться. Примем 
будет увеличивать до 5, т.к. при этом 
Поскольку 
«ненадежнее» всех в базисе, выведем его из базиса, а в базис введем 
Выразим F и новые базисные переменные через 
найдём 
и подставим его в выражения (1),(2),(3).
(*)
.
Свободные переменные 
.Положим их равными 0.Решая пример далее, видим, что 
будет возрастатать (а нам нужно 
минимизировать).Значит 
. Свободную переменную 
можно увеличивать, но до 
иначе 
будет отрицательна 
.)
Выводим 
Свободные переменные 
.
*).
Здесь можно увеличивать 
В процессе перехода от одного базисного решения к другому значение F постоянно уменьшалось.
достигаются в точках пересечения этого многогранника решений с «опорными» прямыми 
Выпишем 
из базисных решений:
указывает положительное направление, при движении в котором F увеличивается. Целевая функция задачи ЛП достигает минимума (максимума) в крайней точке выпуклой области. Если F принимает оптимальное значение в нескольких точках, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек (случай, когда целевая функция достигает минимума на грани многогранника) [1]. Множество всех планов задачи ЛП выпукло [1-4]. Отыскание оптимума целевой функции сводится к перебору крайних точек выпуклого многогранника.