Принципы решения некоторых задач математического программирования
Контрольная работа - Математика и статистика
Другие контрольные работы по предмету Математика и статистика
Задача №1
;
двойственность транспортный задача симплексный
1. Решить задачу графическим методом.
. Решить задачу симплексным методом.
. Построить для задачи двойственную.
. Решить двойственную задачу с помощью первой основной теоремы теории двойственности.
. Решить двойственную задачу с помощью второй основной теоремы теории двойственности.
Задача №2
j / i1234112215022212703121330402560251. Построить математическую модель транспортной задачи.
. Найти опорный план перевозок транспортной задачи методом северо-западного угла.
. Найти опорный план перевозок транспортной задачи методом минимального элемента.
. Решить методом потенциалов транспортную задачу дважды, используя найденные в пунктах 2 и 3 опорные планы перевозок.
Решение:
Задача №1:
. Графический метод
Преобразуем задачу на минимум к задаче на максимум:
=
Основные ограничения задачи содержат 3 уравнения с 5-ю неотрицательными переменными. Так как число переменных n = 5 и число ограничений т = 3 отличаются на 2, то можно предположить, что эту задачу можно решить графическим методом. Соотношение n-m = 2 сохранится, если основные ограничения задачи линейно независимые.
Преобразуем исходную задачу, разделив переменные на базисные и свободные, предварительно записав целевую функцию как уравнение
Все вычисление проведём в таблице, используя метод полного исключения (Метод Жардана - Гаусса). ? - контрольная сумма.
X1X2X3X4X5B14101154-3-11162-4-110-3-11-1-21014101150-19-51-3-540-12-31-2-33050-221514101150-19-51-3-5407201210-33-100-4-931-3-100-602110907201210-5-200-9-1/311/30022/301/31057/30-1/3017-5/30-1/3001
Выполнив 4 шага вычислений метода полного исключения, мы получили следующую систему уравнений:
Разрешив эту систему относительно базисных переменных , , и учитывая, что мы получим следующую задачу:
Эта задача содержит 2 переменных и её можно решить графическим методом. Запишем уравнения границ области, точки для их построения и укажем полуплоскости, определяемые неравенствами основных ограничений задачи
(1) (0; 6) (-6; 0)
(2) (0; 15) (7,5; 0)
(3) (0; - 21) (3; 0)
Строим область допустимых решений системы неравенств в прямоугольной системе .
Область D - это точки 1-ой четверти. Вектор L в данном случае имеет вид L = (1,6; 0,3).
Строим прямую Z перпендикулярно вектору L. Таким образом, получаем пересечение перпендикуляра с прямыми 2) и 3), в результате чего получаем точку А. В соответствии в этим составляем систему уравнений. Решая систему уравнении: находим координаты этой точки.
А = (4; 7), подставим в целевую функцию получим следующие значения:
, , получим: .
2. Симплекс метод
Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод), получим:
Составим таблицу итераций:
БАЗИССA0ВЕКТОРЫA1A2A3A4A5A202-1/311/300A40-52/301/310A5077/30-1/301?1-5/30-1/3012-я итерацияА203011/2101/7А403003/71-2/7А15/3310-1/705/7?600-12/2105/73-я итерацияА208/3010-1/911/63А31/370017/3-2/3А45/341001/31/3?100004/31/3
На первой итерации видим, что среди ? есть отрицательные - это значит что решение не оптимально. Вектор А1 выводим в базис, так как . Для того чтобы выбрать какой элемент мы будем выводить из базиса делаем следующее: элемент столбца делим на элемент столбца по принципу первый на первый, второй на второй. Из полученных результатов деления выбираем наименьшее положительное.
Из этого следует что выводим элемент . Далее пересчитываем таблицу по методу Жардано-Гаусса и получаем таблицу второй итерации.
Видим, что среди ? есть отрицательные - это значит что решение не оптимально. Вектор выводим в базис потому, что . По вышеизложенному принципу выбираем элемент для вывода из базиса. Выводим из базиса . Далее пересчитываем таблицу по методу Жардана-Гаусса и получаем таблицу третей итерации.
Видим, что среди ? нет отрицательных - это значит что решение оптимально.
3. Двойственная задачи
Любая задача математического программирования имеет обратную ей задачу, так называемую двойственную ей задачу, причем соблюдается условие: и на оборот.
Строим двойственную задачу по такому принципу: A [] - матрица задачи, тогда матрица обратной задачи будет, причем.
Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод), получим:
Тогда двойственная этой задачи будет иметь вид:
4. Решение двойственной задачи с помощью первой основной теоремы теории двойственности
Первая теорема двойственности позволяет решить двойственную задачу по решению прямой задачи, используя полученные симплекс таблицы.
Теорема: Если одна из двойственных задач имеет оптимальное решение, то и двойственная ей задача имеет оптимальное решение, причем - эти задачи совпадают.
Из доказательства теоремы следует, что . Матрица решений получается перемножением матриц (вектор-строка коэффициентов в целевой функции при базисных переменных); (матрица обратная матрицы , составленная из векторов оптимального базиса, тоесть матрица на исходных векторах, но взятых из последней симплекс таблицы).
Решаем двойственную задачу с помощью симплексных таблиц (см. Симплекс метод).
БАЗИССA0ВЕКТОРЫA1A2A3A4A5A202-1/311/300A40-52/301/310A5077/30-1/301?1-5/30-1/3012-я итерацияА2