Принципы решения некоторых задач математического программирования
Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
Рубрика | Математика |
Вид | контрольная работа |
Язык | русский |
Дата добавления | 27.11.2011 |
Размер файла | 333,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Задача №1
;
двойственность транспортный задача симплексный
1. Решить задачу графическим методом.
2. Решить задачу симплексным методом.
3. Построить для задачи двойственную.
4. Решить двойственную задачу с помощью первой основной теоремы теории двойственности.
5. Решить двойственную задачу с помощью второй основной теоремы теории двойственности.
Задача №2
j / i |
1 |
2 |
3 |
4 |
||
1 |
1 |
2 |
2 |
1 |
50 |
|
2 |
2 |
2 |
1 |
2 |
70 |
|
3 |
1 |
2 |
1 |
3 |
30 |
|
40 |
25 |
60 |
25 |
1. Построить математическую модель транспортной задачи.
2. Найти опорный план перевозок транспортной задачи методом северо-западного угла.
3. Найти опорный план перевозок транспортной задачи методом минимального элемента.
4. Решить методом потенциалов транспортную задачу дважды, используя найденные в пунктах 2 и 3 опорные планы перевозок.
Решение:
Задача №1:
1. Графический метод
Преобразуем задачу на минимум к задаче на максимум:
=
Основные ограничения задачи содержат 3 уравнения с 5-ю неотрицательными переменными. Так как число переменных n = 5 и число ограничений т = 3 отличаются на 2, то можно предположить, что эту задачу можно решить графическим методом. Соотношение n-m = 2 сохранится, если основные ограничения задачи линейно независимые.
Преобразуем исходную задачу, разделив переменные на базисные и свободные, предварительно записав целевую функцию как уравнение
Все вычисление проведём в таблице, используя метод полного исключения (Метод Жардана - Гаусса). ? - контрольная сумма.
X1 |
X2 |
X3 |
X4 |
X5 |
B |
|
1 |
4 |
1 |
0 |
1 |
15 |
|
4 |
-3 |
-1 |
1 |
1 |
6 |
|
2 |
-4 |
-1 |
1 |
0 |
-3 |
|
-1 |
1 |
-1 |
-2 |
1 |
0 |
|
1 |
4 |
1 |
0 |
1 |
15 |
|
0 |
-19 |
-5 |
1 |
-3 |
-54 |
|
0 |
-12 |
-3 |
1 |
-2 |
-33 |
|
0 |
5 |
0 |
-2 |
2 |
15 |
|
1 |
4 |
1 |
0 |
1 |
15 |
|
0 |
-19 |
-5 |
1 |
-3 |
-54 |
|
0 |
7 |
2 |
0 |
1 |
21 |
|
0 |
-33 |
-10 |
0 |
-4 |
-93 |
|
1 |
-3 |
-1 |
0 |
0 |
-6 |
|
0 |
2 |
1 |
1 |
0 |
9 |
|
0 |
7 |
2 |
0 |
1 |
21 |
|
0 |
-5 |
-2 |
0 |
0 |
-9 |
|
-1/3 |
1 |
1/3 |
0 |
0 |
2 |
|
2/3 |
0 |
1/3 |
1 |
0 |
5 |
|
7/3 |
0 |
-1/3 |
0 |
1 |
7 |
|
-5/3 |
0 |
-1/3 |
0 |
0 |
1 |
Выполнив 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 |
ВЕКТОРЫ |
|||||
A1 |
A2 |
A3 |
A4 |
A5 |
||||
A2 |
0 |
2 |
-1/3 |
1 |
1/3 |
0 |
0 |
|
A4 |
0 |
-5 |
2/3 |
0 |
1/3 |
1 |
0 |
|
A5 |
0 |
7 |
7/3 |
0 |
-1/3 |
0 |
1 |
|
? |
1 |
-5/3 |
0 |
-1/3 |
0 |
1 |
||
2-я итерация |
||||||||
А2 |
0 |
3 |
0 |
1 |
1/21 |
0 |
1/7 |
|
А4 |
0 |
3 |
0 |
0 |
3/7 |
1 |
-2/7 |
|
А1 |
5/3 |
3 |
1 |
0 |
-1/7 |
0 |
5/7 |
|
? |
6 |
0 |
0 |
-12/21 |
0 |
5/7 |
||
3-я итерация |
||||||||
А2 |
0 |
8/3 |
0 |
1 |
0 |
-1/9 |
11/63 |
|
А3 |
1/3 |
7 |
0 |
0 |
1 |
7/3 |
-2/3 |
|
А4 |
5/3 |
4 |
1 |
0 |
0 |
1/3 |
1/3 |
|
? |
10 |
0 |
0 |
0 |
4/3 |
1/3 |
На первой итерации видим, что среди ? есть отрицательные - это значит что решение не оптимально. Вектор А1 выводим в базис, так как . Для того чтобы выбрать какой элемент мы будем выводить из базиса делаем следующее: элемент столбца делим на элемент столбца по принципу первый на первый, второй на второй. Из полученных результатов деления выбираем наименьшее положительное.
Из этого следует что выводим элемент . Далее пересчитываем таблицу по методу Жардано-Гаусса и получаем таблицу второй итерации.
Видим, что среди ? есть отрицательные - это значит что решение не оптимально. Вектор выводим в базис потому, что . По вышеизложенному принципу выбираем элемент для вывода из базиса. Выводим из базиса . Далее пересчитываем таблицу по методу Жардана-Гаусса и получаем таблицу третей итерации.
Видим, что среди ? нет отрицательных - это значит что решение оптимально.
3. Двойственная задачи
Любая задача математического программирования имеет обратную ей задачу, так называемую двойственную ей задачу, причем соблюдается условие: и на оборот.
Строим двойственную задачу по такому принципу: A [] - матрица задачи, тогда матрица обратной задачи будет, причем.
Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод), получим:
Тогда двойственная этой задачи будет иметь вид:
4. Решение двойственной задачи с помощью первой основной теоремы теории двойственности
Первая теорема двойственности позволяет решить двойственную задачу по решению прямой задачи, используя полученные симплекс таблицы.
Теорема: Если одна из двойственных задач имеет оптимальное решение, то и двойственная ей задача имеет оптимальное решение, причем - эти задачи совпадают.
Из доказательства теоремы следует, что . Матрица решений получается перемножением матриц (вектор-строка коэффициентов в целевой функции при базисных переменных); (матрица обратная матрицы , составленная из векторов оптимального базиса, тоесть матрица на исходных векторах, но взятых из последней симплекс таблицы).
Решаем двойственную задачу с помощью симплексных таблиц (см. Симплекс метод).
БАЗИС |
С |
A0 |
ВЕКТОРЫ |
|||||
A1 |
A2 |
A3 |
A4 |
A5 |
||||
A2 |
0 |
2 |
-1/3 |
1 |
1/3 |
0 |
0 |
|
A4 |
0 |
-5 |
2/3 |
0 |
1/3 |
1 |
0 |
|
A5 |
0 |
7 |
7/3 |
0 |
-1/3 |
0 |
1 |
|
? |
1 |
-5/3 |
0 |
-1/3 |
0 |
1 |
||
2-я итерация |
||||||||
А2 |
0 |
3 |
0 |
1 |
1/21 |
0 |
1/7 |
|
А4 |
0 |
3 |
0 |
0 |
3/7 |
1 |
-2/7 |
|
А1 |
5/3 |
3 |
1 |
0 |
-1/7 |
0 |
5/7 |
|
? |
6 |
0 |
0 |
-12/21 |
0 |
5/7 |
||
3-я итерация |
||||||||
А2 |
0 |
8/3 |
0 |
1 |
0 |
-1/9 |
11/63 |
|
А3 |
1/3 |
7 |
0 |
0 |
1 |
7/3 |
-2/3 |
|
А4 |
5/3 |
4 |
1 |
0 |
0 |
1/3 |
1/3 |
|
? |
10 |
0 |
0 |
0 |
4/3 |
1/3 |
Отсюда следует, что:
5. Решение двойственной задачи с помощью второй основной теоремы теории двойственности
Вторая теорема двойственности также позволяет решить двойственную задачу, используя решение первой задачи и используя ограничения.
Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод) и возьмем точку А (см. Графический метод) получим:
А=(4; 7)
Отсюда следует, что необходимо искать и .
Решив, систему уравнений получим: .
Отсюда
Ответ: Максимальная прибыль будет равна 10.
Задача №2
1. Построение математической модели транспортной задачи
Транспортные задачи - это задачи в которых нужно решить проблему: доставку продукции от множества поставщиков к множеству потребителей с минимальными затратами на транспортировку.
Для решения этих задач нужно знать матрицу поставщиков , матрицу потребителей и матрицу перевозок . Матрица перевозок показывает стоимость перевозки от i поставщика к j потребителю.
Обычно условие такой задачи задается или сводится к таблице перевозок. Верхняя строчка таблицы показывает ресурсы поставщиков, самый левый столбец указывает потребности потребителя. Остальная матрица таблицы показывает затраты на доставку продукции от поставщиков к потребителям.
Решение задачи будет определение количество товара, которое необходимо поставить от каждого поставщика к каждому потребителю.
Исходя из условий задачи получаем:
Матрица поставщиков имеет вид:
Матрица потребителей имеет вид:
Матрица перевозок имеет вид:
Система ограничений по поставки имеет вид:
Система ограничений по потреблению имеет вид:
Функция цели имеет вид:
2. Поиск опорного плана транспортной задачи методом северо-западного угла
Выбираем первую пустую северо-западную клетку, и заполняем ее максимальным допустимым значением. После выбираем следующую северо-западную клетку и заполняем. Процедура повторяется до тех пор, пока не будут удовлетворены все поставщики и потребители. В итоге получаем опорный план методом северо-западного угла:
i / j |
40 |
25 |
60 |
25 |
|
50 |
1 40 |
2 10 |
2 |
1 |
|
70 |
2 |
2 15 |
1 55 |
2 |
|
30 |
1 |
2 |
1 5 |
3 25 |
Стоимость перевозок: L=40+20+30+55+5+75=225
3. Поиск опорного плана транспортной задачи методом минимального элемента
Выбираем клетку с наименьшей стоимостью перевозки и заполняем ее максимально допустимым значением. После выбираем следующую клетку и заполняем ее. Процедура повторяется до тех пор, пока не будут удовлетворены все поставщики и потребители. В итоге получаем опорный план методом минимального элемента.
i / j |
40 |
25 |
60 |
25 |
|
50 |
1 40 |
2 |
2 |
1 10 |
|
70 |
2 |
2 |
1 60 |
2 10 |
|
30 |
1 |
2 25 |
1 |
3 5 |
Стоимость перевозок: L=40+50+60+10+20+15=195
4. Решение транспортной задачи методом потенциалов
Введем для обозначения потенциалов буквы: для обозначения потенциала строки букву «U», обозначения потенциалов столбца букву «V». Возьмем опорный план, найденный в третьем пункте задачи, и заполним таблицу с учетом потенциалов. Причем для потенциалов будет выполняться условие: .
i / j |
40 |
25 |
60 |
25 |
U |
|
50 |
1 40 |
2 |
2 |
1 10 |
U1 |
|
70 |
2 |
2 |
1 60 |
2 10 |
U2 |
|
30 |
1 |
2 25 |
1 |
3 5 |
U3 |
|
V |
V1 |
V2 |
V3 |
V4 |
Составить систему уравнений по заполненным клеткам.
Поскольку уравнений шесть, а неизвестных переменных семь, зададим потенциал . Отсюда , , и , , , .
Составляем косвенные стоимости () для пустых клеток по найденным потенциалам.
Определяем оценки (г) для пустых клеток по формуле: прямая минус косвенная стоимость.
Поскольку отрицательных оценок есть, то данный план не оптимален. Составляем новый план с другим позиционированием коэффициентов.
i / j |
40 |
25 |
60 |
25 |
U |
|
50 |
1 25 |
2 |
2 |
1 25 |
U1 |
|
70 |
2 |
2 10 |
1 60 |
2 |
U2 |
|
30 |
1 15 |
2 15 |
1 |
3 |
U3 |
|
V |
V1 |
V2 |
V3 |
V4 |
Составить систему уравнений по заполненным клеткам.
Поскольку уравнений шесть, а неизвестных переменных семь, зададим потенциал . Отсюда , , и , , , .
Составляем косвенные стоимости () для пустых клеток по найденным потенциалам.
Определяем оценки (г) для пустых клеток по формуле: прямая минус косвенная стоимость.
Так как отрицательных оценок нет, то план перевозок оптимален. L=175
Ответ: Себестоимость перевозок равна L=175.
Размещено на Allbest.ru
Подобные документы
Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа [23,5 K], добавлен 12.06.2011Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
курсовая работа [219,4 K], добавлен 17.04.2013Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа [517,9 K], добавлен 30.04.2011Двойственные задачи в линейном программировании. Симметричные и несимметричные двойственные задачи. Связь исходной и двойственной задач. Анализ моделируемой ситуации (моделируемого объекта). Реализация двойственности на Visual Basic for Application.
курсовая работа [703,5 K], добавлен 14.10.2011Формирование нижних и верхних оценок целевой функции. Алгоритм метода ветвей и границ, решение задач с его помощью. Решение задачи коммивояжера методом ветвей и границ. Математическая модель исследуемой задачи, принципы ее формирования и порядок решения.
курсовая работа [153,2 K], добавлен 25.11.2011Применение математических и вычислительных методов в планировании перевозок. Понятие и виды транспортных задач, способы их решения. Особенности постановки задачи по критерию времени. Решение транспортной задачи в Excel, настройка параметров решателя.
курсовая работа [1,0 M], добавлен 12.01.2011Решение систем уравнений по правилу Крамера, матричным способом, с использованием метода Гаусса. Графическое решение задачи линейного программирования. Составление математической модели закрытой транспортной задачи, решение задачи средствами Excel.
контрольная работа [551,9 K], добавлен 27.08.2009Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлен 30.11.2010