Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного программирования)

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

Телешовой Елизаветы, гр. 726,

Теория двойственности в задачах линейного программирования.

Задача:

Для изготовления определенного сплава из свинца, цинка и олова используется сырье из тех же металлов, отличающееся составом и стоимостью.

Определить, сколько нужно взять сырья каждого вида, чтобы изготовить с минимальной себестоимостью сплав, содержащий олова не более 30%, цинка не менее 10%, свинца не более 40%.

Решение задачи:

Пусть х_i  – доля сырья i-го вида в единице полученного сплава. Тогда функция цели (себестоимость единицы сплава в у.е.) запишется следующим образом:

Система ограничений будет иметь вид:

    (1).

Запишем систему в каноническом виде:

    (2).

Решим поставленную задачу методом искусственного  базиса. Для этого составим расширенную задачу:

    (3).

Составим вспомогательную целевую функцию:  из первого ограничения, а  из третьего получаем:

;

;

Тогда:

Запишем начальную симплекс-таблицу:

Оптимальная симплекс-таблица будет иметь вид:

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

Экономически полученное решение интерпретируется следующим образом: для получения единицы сплава минимальной себестоимости необходимо взять 40% сырья №2 и 60% сырья №3. При этом сплав содержит ровно 30% олова, более 20% (точнее, 42%) цинка и менее 40% (28%) свинца. Минимальная себестоимость единицы сплава составляет 5,28 у.е.

Математическая модель и экономический смысл двойственной задачи.

Задача, двойственная к исходной, строится следующим образом:

1) Исходная задача – на минимум, следовательно, двойственная задача – на максимум.

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

 =>

3) Число переменных в двойственной задаче равно числу ограничений в исходной, т.е. 4, и наоборот, число ограничений в двойственной задаче равно числу переменных в исходной, т.е. 5. Переменная  двойственной задачи соответствует первому ограничению исходной задачи, переменная – четвёртому.

4) Коэффициентами при переменных  и  в целевой функции двойственной задачи являются свободные члены ограничений исходной задачи (все ограничения одного типа), т.е. вектор

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

5) Т.к. все переменные исходной задачи неотрицательны, то все ограничения двойственной задачи будут неравенствами типа « может принимать любые значения, а  – только положительные.

Таким образом, математическая модель двойственной задачи следующая:

   (4).

Проанализируем теперь экономический смысл двойственной задачи. Для этого сначала рассмотрим экономический смысл переменных  и  имеет размерность [у.е./ед. сплава], величина  не представляется возможным в силу условия задачи. Что касается экономического смысла переменных  и

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

Целевая функция данной двойственной задачи экономически интерпретируется как максимальная прибыль фирмы-поставщика ресурсов.