Принципы решения некоторых задач математического программирования

Принципы решения некоторых задач математического программирования

Задача №1

;

двойственность транспортный задача симплексный

1. Решить задачу графическим методом.

. Решить задачу симплексным методом.

. Построить для задачи двойственную.

. Решить двойственную задачу с помощью первой основной теоремы теории двойственности.

. Решить двойственную задачу с помощью второй основной теоремы теории двойственности.

Задача №2

1. Построить математическую модель транспортной задачи.

. Найти опорный план перевозок транспортной задачи методом северо-западного угла.

. Найти опорный план перевозок транспортной задачи методом минимального элемента.

. Решить методом потенциалов транспортную задачу дважды, используя найденные в пунктах 2 и 3 опорные планы перевозок.

Решение:

Задача №1:

. Графический метод

Преобразуем задачу на минимум к задаче на максимум:

 =

Основные ограничения задачи содержат 3 уравнения с 5-ю неотрицательными переменными. Так как число переменных n = 5 и число ограничений т = 3 отличаются на 2, то можно предположить, что эту задачу можно решить графическим методом. Соотношение n-m = 2 сохранится, если основные ограничения задачи линейно независимые.

Преобразуем исходную задачу, разделив переменные на базисные и свободные, предварительно записав целевую функцию как уравнение

Все вычисление проведём в таблице, используя метод полного исключения (Метод Жардана - Гаусса). ∑ - контрольная сумма.

Выполнив 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. Симплекс метод

Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод), получим:

Составим таблицу итераций:

На первой итерации видим, что среди ∆ есть отрицательные - это значит что решение не оптимально. Вектор А1 выводим в базис, так как . Для того чтобы выбрать какой элемент мы будем выводить из базиса делаем следующее: элемент столбца  делим на элемент столбца  по принципу первый на первый, второй на второй. Из полученных результатов деления выбираем наименьшее положительное.

Из этого следует что выводим элемент . Далее пересчитываем таблицу по методу Жардано-Гаусса и получаем таблицу второй итерации.

Видим, что среди ∆ есть отрицательные - это значит что решение не оптимально. Вектор  выводим в базис потому, что . По вышеизложенному принципу выбираем элемент для вывода из базиса. Выводим из базиса . Далее пересчитываем таблицу по методу Жардана-Гаусса и получаем таблицу третей итерации.

Видим, что среди ∆ нет отрицательных - это значит что решение оптимально.

3. Двойственная задачи

Любая задача математического программирования имеет обратную ей задачу, так называемую двойственную ей задачу, причем соблюдается условие:  и на оборот.

Строим двойственную задачу по такому принципу: A [] - матрица задачи, тогда матрица обратной задачи будет, причем.

Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод), получим:

Тогда двойственная этой задачи будет иметь вид:

4. Решение двойственной задачи с помощью первой основной теоремы теории двойственности

Первая теорема двойственности позволяет решить двойственную задачу по решению прямой задачи, используя полученные симплекс таблицы.

Теорема: Если одна из двойственных задач имеет оптимальное решение, то и двойственная ей задача имеет оптимальное решение, причем  - эти задачи совпадают.

Из доказательства теоремы следует, что . Матрица решений  получается перемножением матриц  (вектор-строка коэффициентов в целевой функции при базисных переменных);  (матрица обратная матрицы , составленная из векторов оптимального базиса, тоесть матрица на исходных векторах, но взятых из последней симплекс таблицы).

Решаем двойственную задачу с помощью симплексных таблиц (см. Симплекс метод).

Отсюда следует, что:

5. Решение двойственной задачи с помощью второй основной теоремы теории двойственности

Вторая теорема двойственности также позволяет решить двойственную задачу, используя решение первой задачи и используя ограничения.

Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод) и возьмем точку А (см. Графический метод) получим:

 А=(4; 7)

Отсюда следует, что необходимо искать  и .

Решив, систему уравнений получим: .

Отсюда

Ответ: Максимальная прибыль будет равна 10.

Задача №2

1.      Построение математической модели транспортной задачи

Транспортные задачи - это задачи в которых нужно решить проблему: доставку продукции от множества поставщиков к множеству потребителей с минимальными затратами на транспортировку.

Для решения этих задач нужно знать матрицу поставщиков , матрицу потребителей  и матрицу перевозок . Матрица перевозок показывает стоимость перевозки от i поставщика к j потребителю.

Обычно условие такой задачи задается или сводится к таблице перевозок. Верхняя строчка таблицы показывает ресурсы поставщиков, самый левый столбец указывает потребности потребителя. Остальная матрица таблицы показывает затраты на доставку продукции от поставщиков к потребителям.

Решение задачи будет определение количество товара, которое необходимо поставить от каждого поставщика к каждому потребителю.

Исходя из условий задачи получаем:

Матрица поставщиков имеет вид:

Матрица потребителей имеет вид:

Матрица перевозок имеет вид:

Система ограничений по поставки имеет вид:

Система ограничений по потреблению имеет вид:

Функция цели имеет вид:

2.      Поиск опорного плана транспортной задачи методом северо-западного угла

Выбираем первую пустую северо-западную клетку, и заполняем ее максимальным допустимым значением. После выбираем следующую северо-западную клетку и заполняем. Процедура повторяется до тех пор, пока не будут удовлетворены все поставщики и потребители. В итоге получаем опорный план методом северо-западного угла:

Стоимость перевозок: L=40+20+30+55+5+75=225

3. Поиск опорного плана транспортной задачи методом минимального элемента

Выбираем клетку с наименьшей стоимостью перевозки и заполняем ее максимально допустимым значением. После выбираем следующую клетку и заполняем ее. Процедура повторяется до тех пор, пока не будут удовлетворены все поставщики и потребители. В итоге получаем опорный план методом минимального элемента.

Стоимость перевозок: L=40+50+60+10+20+15=195

4. Решение транспортной задачи методом потенциалов

Введем для обозначения потенциалов буквы: для обозначения потенциала строки букву «U», обозначения потенциалов столбца букву «V». Возьмем опорный план, найденный в третьем пункте задачи, и заполним таблицу с учетом потенциалов. Причем для потенциалов будет выполняться условие: .

Составить систему уравнений по заполненным клеткам.

Поскольку уравнений шесть, а неизвестных переменных семь, зададим потенциал . Отсюда , ,  и , , , .

Составляем косвенные стоимости () для пустых клеток по найденным потенциалам.

Определяем оценки (г) для пустых клеток по формуле: прямая минус косвенная стоимость.

Поскольку отрицательных оценок есть, то данный план не оптимален. Составляем новый план с другим позиционированием коэффициентов.

Составить систему уравнений по заполненным клеткам.

Поскольку уравнений шесть, а неизвестных переменных семь, зададим потенциал . Отсюда , ,  и , , , .

Составляем косвенные стоимости () для пустых клеток по найденным потенциалам.

Определяем оценки (г) для пустых клеток по формуле: прямая минус косвенная стоимость.

Так как отрицательных оценок нет, то план перевозок оптимален. L=175

Ответ: Себестоимость перевозок равна L=175.