Линейное программирование как обобщенный метод
Что же такое линейное программирование? Чтобы ответить на этот вопрос, будет полезно для начала вспомнить из линейной алгебры задачу системы ли- нейных уравнений. B матрично-векторной записи имеется вектор x неизвестных вещественных чисел, заданная матрица A и заданный вектор b; требуется решить уравнение Ax = b. Многим хорошо известен метод исключения Гаусса, позволяющий эффективно решать такие задачи.
Базовая задача линейного программирования может рассматриваться как более сложная версия этой задачи, в которой равенства заменены неравенствами. Говоря конкретнее, рассмотрим задачу определения вектора x, удовлетворяющего неравен- ству Ax > b. Под этой записью мы имеем в виду, что каждая координата вектора Ax должна быть больше либо равна соответствующей координаты вектора b.
Такие системы неравенств определяют области в пространстве. Например, предположим, x = (x1,x2) — двумерный вектор, и имеются четыре неравенства:xj > 0, x2 > 0
xj + 2x2 > 6 2xj + x2 > 6
В этом случае множество решений определяет область на плоскости, изобра- женную на рис. 11.10. Для заданной области, определяемой уравнением Ax > b, линейное программирование стремится минимизировать линейную комбинацию координат x по всем x, принадлежащим области.
Рис. 11.10. Область допустимых решений простой задачи линейного программирования |
Такая линейная комбинация может быть записана в виде ctx, где c — вектор коэффициентов, а c‘x обозначает скалярное произведение двух векторов.
Таким образом, стандартная форма линейного программирования как задачи оптими- зации выглядит следующим образом.Для заданной матрицы A с размерами m χ n, векторов b Rm и c Rn найти
вектор x e Rn для решения следующей задачи оптимизации:
miп(⅛ для x > 0; Ax > b).
c‘x часто называется целевой функцией линейной программы, а Ax > b называется набором ограничений. Например, в примере на рис. 11.10, допустим, определяет- ся вектор c (1,5, 1); другими словами, мы стремимся минимизировать величину 1,5x1 + x2 по области, определяемой неравенствами.
Задача решается выбором точки x = (2,2), в которой пересекаются две наклон- ные линии; в ней ctx = 5, и вы можете убедиться, что получить меньшее значение невозможно.
Задачу линейного программирования можно сформулировать как задачу при- нятия решения следующим образом:
Для заданной матрицы A, векторов b и c, и границы γ существует ли такое зна- чение x, для которого x > 0, Ax > b, и ctx < γ?
Чтобы избежать проблем, связанных с представлением вещественных чисел, мы будем считать, что координаты в векторах и матрице являются целыми числами.
Еще по теме Линейное программирование как обобщенный метод:
- Метод обобщения независимых характеристик.
- ИГНОРИРУЙТЕ ЛИНЕЙНЫЕ ПРЕДСКАЗАНИЯ И ИЗБЕГАЙТЕ ЛИНЕЙНЫХ ВЫВОДОВ! ВЕРЬТЕ СВОЕМУ СЕРДЦУ!
- ГЛАВА 18 ОБОБЩЕНИЕ МЕТОДА ГИПСОСОЗНАНИЯ И УКАЗАНИЯ ПО ЕГО ПРИМЕНЕНИЮ
- Нередко предлагаемое в вопросе действие респонденты оценивают как обобщенное, типичное, т.е. как действие, которое они обычно совершают.
- 7. Интересуйтесь тем, как ваш ребенок относится к слабым ученикам, как помогает им, какими методами завоевывает авторитет
- ОБОБЩЕНИЕ
- Линейно-функциональные структуры.
- ОБОБЩЕНИЕ ТЕОРЕТИЧЕСКОЕ
- ОБОБЩЕНИЕ ЭМПИРИЧЕСКОЕ
- Линейный и нелинейный умы
- Линейные структуры.
- Линейный ум-эго
- Модификации линейной организационной структуры.
- Иванова Г.С. Основы программирования, 2002
- Линейный и нелинейный ум
- Линейное и нелинейное мышление
- Линейное и нелинейное мышление
- Эстетика программирования
- Перефразирование и обобщение.
- Перефразирование и обобщение.