Автор: Пользователь скрыл имя, 17 Января 2012 в 20:33, курсовая работа
Важное место в математике, а особенно в приложениях математики к реальным практическим задачам, занимает математическое программирование. Это математическая дисциплина, посвящена теории и методам решения задач о нахождении экстремумов функций на множествах
конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). Такие задачи имеют огромную область применения, не в последнюю очередь потому, что “любой процесс в первом приближении является линейным”.
1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
2. ПОСТАНОВКА И АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ ЛП ГРАФИЧЕСКИМ МЕТОДОМ.
3. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ГРАФИЧЕСКИМ МЕТОДОМ.
4. ПОСТАНОВКА И АЛГОРИТМ РЕШЕНИЯ СИМПЛЕКСНОГО МЕТОДА.
5. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ СИМПЛЕКСНЫМ МЕТОДОМ.
6. ВИДЫ ДВОЙСТВЕННЫХ ЗАДАЧ. ОСНОВНЫЕ ТЕОРЕМЫ ДВОЙСТВЕННОСТИ.
На основании 1-й теоремы двойственности получаем
Решение другой задачи найдем по соответствию между переменными:
Значение xj определяем по последней симплексной таблице в строке Δi в соответствующем столбце, причем значения xj берем по модулю:
Таким образом, решение исходной задачи:
Если исходная задача решена симплексным методом, то решение двойственной задачи может быть найдено по формуле
где С — матрица-строка коэффициентов при базисных переменных целевой функции в оптимальном решении исходной задачи; А-1 — обратная матрица для матрицы А, являющейся матрицей коэффициентов базисных переменных системы ограничений исходной задачи в оптимальном решении.
Решим симплексным методом исходную задачу вида
при ограничениях:
Таблица 4.2.
| БП | 1 | -1 | 0 | 0 | 0 | ||
| 0 | -2 | 1 | 1 | 0 | 0 | 2 | |
| 0 | 1 | -2 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 1 | 0 | 0 | 1 | 5 | |
| -1 | 1 | 0 | 0 | 0 | 0 | ||
| 0 | 0 | -3 | 1 | 2 | 0 | 6 | |
| 1 | 1 | -2 | 0 | 1 | 0 | 2 | |
| 0 | 0 | 3 | 0 | -1 | 1 | 3 | |
| 0 | -1 | 0 | 1 | 0 | 2 | ||
| 0 | 0 | 0 | 1 | 1 | 1 | 9 | |
| 1 | 1 | 0 | 0 | 1/3 | 2/3 | 4 | |
| -1 | 0 | 1 | 0 | -1/3 | 1/3 | 1 | |
| 0 | 0 | 0 | 2/3 | 1/3 | 3 |
Из табл. 4.2 следует, что опт = (4,1), L( )max = 3. Матрицы записываются в виде
тогда
Таким образом, решение двойственной задачи следующее:
Рассмотрим решение задач с использованием теорем двойственности.
Решив двойственную задачу графическим методом, получим
По 1-й теореме двойственности L( )min = S( )max = 33/2.
Подставим опт в систему ограничений двойственной задачи:
Так как х3 = х4 = 0, то система ограничений исходной задачи примет вид
Решая данную систему, получим
Рассмотрим решение задач с использованием обратной матрицы.
Пусть решение исходной задачи
Решение двойственной задачи найдем по формуле
где
Таким образом, oпт = (1/2, 2), при этом S( )max = 33/2.
Смешанные двойственные задачи можно решать с использованием теорем двойственности.
Найдем
оптимальное решение
По 1-й теореме двойственности
Так как х1 > 0, x3 > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств:
4.3. Примеры.
Пример 4.1. Для прямой задачи линейного программирования записать двойственную задачу и решить их обе графически
Двойственную задачу для прямой задачи линейного программирования запишем в матричной форме.
Решим прямую задачу. Область допустимых значений X представлена на рис.4.1. Область расположена в первой четверти и ограничена прямыми
На рис.4.1 эта область есть четырехугольник ОАВС. Через точку В проходит линия уровня, которая определяет решение.
рис.4.1.
Отметим, что точка В является пересечением прямых a, b и её координаты аналитически находятся как решение системы уравнений
Тогда В(1/9, 2/ 9). Значит
Аналогично находится область допустимых значений Y в двойственной задаче. Область расположена в первой четверти, ограничена прямыми
и не содержит начало координат. Область Y не ограничена и изображена на рис.4.2. У этой области только одна касательная из множества линий уровня. Она проходит через точку Е, координаты которой есть решение системы двух уравнений, т.е. уравнений прямых с, d. Уравнение касательной Тогда двойственная задача имеет решение
рис.4.2.
Пример 4.2. Решить задачу линейной программирования с использованием двойственной задачи
Графически эту стандартную задачу решить не удаётся, т.к. число неизвестных n = 4 > 2. Запишем для неё соответствующую двойственную задачу
В этой задаче только одна переменная – . более того, здесь область допустимых значений состоит из одной точки, числа . Эта точка определяет оптимальное решение двойственной задачи. Именно,
По теоремы двойственности Осталось подобрать допустимое (с неотрицательными координатами) что Один из таких векторов, например, По теореме двойственности получили одно из решений прямой задачи
Отметим, что в этой задаче существуют и другие решения задачи максимизации.
Пример 4.3. Решить задачу линейной программирования с использованием двойственной задачи
Графически эту стандартную задачу решить не удаётся, т.к. число неизвестных n = 4 > 2. Перепишем данную задачу в стандартной форме (как задачу минимизации)
В этой задаче по-прежнему четыре переменные, именно . Запишем двойственную задачу максимизации.
рис.4.3.
Полученную задачу можно решить графически. Область допустимых значений является шестиугольником ABCDEF и представлена на рис.4.3.
Рассмотрим линии уровня, имеющие вид , где c – любое действительное число. Максимальное решение реализуется в точке С(9, 1). Это общая точка шестиугольника ABCDEF и линии уровня p: . Тогда решение двойственной задачи для задачи из данного примера будет
По теореме двойственности имеем условие для исходной задачи
Несложно подобрать решение Таким образом, получаем решение исходной задачи