Алгоритм составления двойственной задачи

1. Привести все неравенства системы ограничений исходной задачи к одному виду: если в исходной задаче ищут максимум целевой функции, то все неравенства системы ограничений привести к виду , а если минимум – к виду . Для этого неравенства, в которых данное требование не выполняется, умножить на (-1).

2. Составить расширенную матрицу системы ограничений исходной задачи – матрицу А, в которую включить строку коэффициентов при переменных в целевой функции.

3. Найти матрицу А₁, транспонированную к матрице А.

4. Сформулировать двойственную задачу на основании полученной матрицы А₁ и условия неотрицательности переменных.

Задача 5.Составить двойственную задачу к следующей ЗЛП:

при ограничениях:

1. Исходная задача на минимизацию, все неравенства приведены к виду .

2. Составим расширенную матрицу системы

3. Найдем матрицу , транспонированную к матрице .

4. Двойственная задача:

при ограничениях

Двойственная задача может быть решена симплекс-методом, а так же с помощью функции Поиск решения в табличных редакторах Microsoft Excel и OpenOffice.org Calc (Л.Р. №1, Л.Р. №2)

Если же исходная задача уже решена симплекс-методом, то решение двойственной задачи может быть найдено по формуле:

(5)

Где С- матрица-строка коэффициентов при базисных переменных целевой функции входящих в оптимальный базис исходной задачи (в первоначальном виде); A^-1- обратная матрица для матрицы А, являющейся матрицей коэффициентов при переменных, входящих в оптимальный базис (взятых из первоначальной системы ограничений исходной задачи).

Рассмотрим последний шаг решения прямой задачи 3 с помощью симплекс-таблиц из Л.Р. №2 (таблица 11).

Таблица 11

БП	СЧ							Оценочное отношение
						4/9	-1/9
						1/3	-1/3
						-1/3	1/3
						-4/9	1/9
						2/3	1/3

Составим матрицу А из коэффициентов при переменных, входящих в оптимальный базис (взятых из первоначальной системы ограничений исходной задачи)

; .

Найдем обратную матрицу A^-1 в табличном редакторе Microsoft Excel или OpenOffice.org Calc с помощью встроенных функций МОБР() (MINVERSE()).

.

Заметим, что обратную матрицу A^-1 можно было выписать из последней симплекс-таблицы, она расположена в столбцах дополнительных переменных.

Тогда .

Операцию умножения матриц так же можно выполнить в редакторах Microsoft Excel или OpenOffice.org Calc с помощью встроенных функций МУМНОЖ() (MMULT()).

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

.

Задание

1. Для задачи 5 найти решение прямой и двойственной задачи с помощью функции Поиск решения в Microsoft Excel или OpenOffice.org Calc.

2. Составить математическую модель двойственной ЗЛП для задач 1 и 2. Из решения прямой задачи 1 и 2 (Л.Р. №2) получить решение двойственной. Расчеты выполнить на листе Microsoft Excel или OpenOffice.org Calc используя функции МОБР() (MINVERSE()), МУМНОЖ() (MMULT()).

3. Составить двойственную задачу к следующей ЗЛП:

при ограничениях:

, , .

Решив одну из них, найти оптимальное решение другой. Провести анализ полученных результатов.

Контрольные вопросы

1. Перечислить свойства взаимно двойственных задач.

2. Сформулировать алгоритм составления математической модели двойственной задачи.

3. Как найти решение двойственной задачи, если исходная (прямая задача) уже решена симплекс-методом?

4. В каком виде должна быть записана модель ЗЛП для решения симплекс-методом?

5. С помощью каких функций двойственная задача может быть решена в табличных редакторах Microsoft Excel или OpenOffice.org Calc?

Лабораторная работа №4

Транспортная задача (ТЗ). Экономико-математическая модель транспортной задачи. Нахождение опорного решения ТЗ.

Метод «северо-западного угла».

Метод минимального элемента

Цель лабораторного занятия:

Освоение приемов записи математической модели закрытой транспортной задачи в табличном редакторе Microsoft Excel и OpenOffice.org Calc с помощью встроенных функций СУММ() (SUM()) СУММПРОИЗВ() (SUMPRODUCT()). Приобретение навыков построения первоначального опорного плана ТЗ с помощью метода «северо-западного угла» и метода минимального элемента.

Задачи лабораторного занятия:

1. Построение математической модели закрытой транспортной задачи в табличном редакторе Microsoft Excel и OpenOffice.org Calc.

2. Определение исходного опорного плана ТЗ (метод «северо-западного угла» и метод минимального элемента).

3. Анализ полученных результатов.

4. Оформление отчета.

Содержание

1. Краткие теоретические сведения.

2. Задание.

3. Контрольные вопросы.

Краткие теоретические сведения

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

В общем виде транспортную задачу можно представить следующим образом: в m пунктах производства имеется однородный груз в количествах, соответственно, Этот груз необходимо доставить в n пунктов назначения в количествах, соответственно, Стоимость перевозки 1 ед. груза (тариф) из пункта в пункт равна .

Требуется составить план перевозок так, чтобы:

1. мощности (запасы) всех поставщиков были реализованы;

2. спросы всех потребителей были удовлетворены;

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

Исходные данные транспортной задачи записываются в виде таблицы 12:

Таблица 12

Поставщики	Мощности (запасы) поставщиков	Потребители и их спрос
		…	n
		…
				…
				…
…	…
m				…

Так же исходные данные могут быть представлены в матричном виде:

-вектор мощностей (запасов) поставщиков;

- вектор спроса потребителей;

- матрица стоимостей перевозок.

Виды транспортных задач

В зависимости от соотношения между суммарными запасами груза у поставщиков и суммарными потребностями в нем потребителей транспортные задачи делятся на два вида: закрытые и открытые.

Определение 1. Если сумма запасов груза у поставщиков равна суммарной потребности в нем потребителей, т.е.

(6)

то транспортная задача называется закрытой.

Определение 2. Если условие (6) не выполняется, т.е.

то транспортная задача называется открытой.

Теорема 1(необходимое и достаточное условие разрешимости ТЗ). Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т.е. чтобы выполнялось равенство (6).