Аналитическое решение задачи

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

Первоначальный опорный план принимает вид:

X₀ = (0; 0; 120; 90; 40)

Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции с противоположным знаком.

Базисные переменные	*					Свободные члены	Отношение
*
F	-5	-2

Построение нового базиса

Чтобы построить новый базис, среди отрицательных оценок (строка F) находим наибольшую по абсолютной величине (максимум по модулю).

Столбец * называется разрешающим или ключевым.

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

Строка, в которой находится наименьшее значение называется разрешающей или ключевой ( *).

Определение нового плана

Все элементы ключевой строки делим на ключевое (разрешающее) число. Это число, стоящее на пересечении ключевой строки и ключевого столбца. Полученную строку обозначаем *. С помощью строки * получаем нули в ключевом столбце. Для того чтобы получить нули в i- тойстроке симплекс - таблицы нужно из старой i- тойстроки вычесть строку *, умножив на соответствующее число.

Например, в нашем случаем, чтобы получить строку нужно из неё вычесть строку * и умножить на 1.

Получаем новую таблицу.

Базисные переменные						Свободные члены	Отношение
		0,5	1/4
		2,5	-1/4
		0,5	-1/4
F		0,5	5/4			150*

Если все значения в строке F положительны, значит мы нашли оптимальное решение (*).

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

4 Аналитическое решение взаимодвойственной задачи

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

Анализ оптимальных решений взаимодвойственных задач позволяет ответить на множество вопросов оптимального моделирования деятельности объектов (ценность ресурсов, чувствительность решения, целесообразность и т.д).

Для двойственных задач характерна теорема двойственности:

Если одна взаимодвойственная задача линейного программирования имеет конечной оптимум, то и д1войственная задача к ней также имеет конечный оптимум; при чем оптимумы обеих задач совпадают.

- план выпуска продукции

- минимальное прибыль

Система ограничений:

Нужно найти такой набор ресурсов Z, при котором общие затраты будут минимальны при условии, что затраты на ресурсы будут не менее прибыли от реализации этой продукции.

Приведем систему ограничений к каноническому виду.

- опорный план

F		0,5	5/4			150*

- опорный план

- оптимум задачи

Компоненты оптимального решения двойственной задачи о прибыли имеют важную трактовку: Они называются объективно-обуславливаемые оценками ресурсов и могут служить ориентирами в определении временной цены ресурсов по которой предприятие готово приобретать ресурсы для дальнейшей работы.

Оптимальные цены должны удовлетворять условия:

За каждый вид ресурсов предприятие готово уплатить не более той суммы, которая может быть выдана при переработке сырья в готовую продукцию. Если >0, то при оптимальном выпуске продукции i -тый ресурс полностью используется и предприятие заинтересовано в пополнении ресурсов. Если =0, то i -тый ресурс не использован и предприятие не заинтересовано в пополнении запаса ресурса.

Определяем ценность ресурсов:

По условия нашей задачи

"труд" - > 0 - полностью использован, необходимо пополнение запасов

"сырьё" и "оборудование" - и = 0 - не использован, запас не требуется

Определяем интервалы устойчивости двойственной оценки для задачи:

Запишем в кононической форме

X =(30; 0;0;60;10)

=30; =60; =10

,

Находим матрицу D:

;

Для вычисления интервалов устойчивости принимаем:

Интервалы устойчивости первого ресурса - "труд":

∆

∆

При изменении запасов ресурсов "труд" в пределах 0-360 ед. его двойственная оценка не меняется.

Интервалы устойчивости второго и третьего ресурса - "сырье" и "оборудование":

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

Нижние границы:

5 Постановка задачи для составления программы

Литература

1 С. И. Шелобаев "Экономико-математические методы и модели", М., 2005, ЮНИТИ

2 В. В. Федосеев, А. Н. Гармаш, И. В. Орлова и др. "Экономико-математические методы и прикладные модели", М., 2005, ЮНИТИ

3 А. И. Ларионов, Г. И. Юрченко, А. А. Новосёлов "Экономико-математические модели в планировании" М., 1991, Высшая школа

4 Б. Банди "Основа ЛП", М., 1989, "Радио и связь"

5 Г. Л. Портыка, И. И. Попов "Математические методы", М., 1989, "Форум Инфро-М"