План производства

 

- среди выбранных коэффициентов  столбца выбирается тот, для  которого абсолютная величина  отношения соответствующего свободного  члена (находящегося в столбце  свободных членов) к этому элементу  минимальна. Этот коэффициент называется разрешающим, а строка, в которой он находится – ключевой; [5]

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

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

- строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.

- в новой таблице все элементы ключевого столбца равны 0, кроме разрезающего, он всегда равен 1.

- столбец, у которого в ключевой строке имеется 0, в новой таблице будет таким же.

- строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же.

-  в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

 

 

В результате получают новую  симплекс-таблицу, отвечающую новому базисному  решению.

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

 

1.3. Двойственная модель линейного программирования

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

На основе теории двойственности разработан алгоритм решения задач линейного программирования – двойственный симплексный метод и эффективные методы анализа моделей на чувствительность.

 

1.3.1. Построение двойственной  задачи

Двойственная обратная задача – задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой, задачи. [1]

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

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

Прямая задача линейного  программирования в стандартной  форме записывается следующим образом:

максимизировать

 (1.4)

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

  (1.5)

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

1) каждому ограничению  прямой задачи соответствует  переменная двойственной задачи;

2) каждой переменной прямой  задачи соответствует ограничение  двойственной задачи;

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

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

Запишем математическую модель двойственной задачи.

Определить вектор , который удовлетворяет ограничениям

  (1.6)

и обеспечивает минимальное  значение целевой функции

 (1.7)

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

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

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

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

3. Система ограничений  двойственной задачи записывается  в виде неравенств противоположного  смысла неравенствам системы  ограничений прямой задачи.

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

5. Двойственная задача  решается на минимум, если целевая  функция прямой задачи задается  на максимум, и наоборот.

6. Коэффициентами функции  цели двойственной задачи служат  свободные члены системы ограничений  прямой задачи.

7. Если переменная прямой  задачи , то j-е условие системы ограничений двойственной задачи является неравенством, если – любое число, то j-е условие двойственной задачи представляет собой уравнение.

8. Если i-е соотношение прямой задачи является неравенством, то соответствующая оценка i-го ресурса – переменная , если i-е соотношение представляет собой уравнение, то переменная двойственной задачи – любое число.

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

 

1.3.2. Сравнительная характеристика прямой и двойственной модели

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

2) Двойственная  модель. Переменные модели – это теневые цены ресурсов для прямой модели, т.е. величины, на которые увеличилось бы значение целевой функции при росте имеющегося запаса сырья соответствующего вида на единицу. Теневые цены характеризуют стоимость единицы сырья каждого вида. Целевая функция задачи – это общая еженедельная стоимость всех видов сырья, используемых при производстве продуктов. Каждое ограничение связано с одним из продуктов. В левой части каждого ограничения дана общая стоимость всех видов сырья, используемых при выпуске 1 единицы соответствующего продукта; в правой – прибыль от выпуска единицы соответствующего продукта. [2]

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

 

1.4. Двойственный симплексный  метод

Двойственный симплексный  метод основан на теории двойственности и используется для решения задач  линейного программирования, свободные  члены которых b_i (i=1,…m) могут принимать любые значения, а система ограничений задана неравенствами смысла «», «» или равенством «=».

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

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

Алгоритм двойственного  симплексного метода включает следующие  этапы.

1. Составление  псевдоплана. Систему ограничений исходной задачи требуется привести к системе неравенств смысла «». Для этого обе части неравенств смысла «» необходимо умножить на (−1). Затем от системы неравенств смысла «» переходят к системе уравнений, вводя неотрицательные дополнительные переменные, которые являются базисными переменными. Первый опорный план заносят в симплексную таблицу.

2. Проверка плана  на оптимальность. Если в полученном опорном плане не выполняется условие оптимальности, то решаем задачу симплексным методом. При этом столбец имеет значения по тем строкам, в которых значения в базисных переменных и коэффициенты ведущего столбца содержат одинаковые знаки (положительные или отрицательные). В случае разноименных знаков b_i и a_ik значения не определяют.

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

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

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

4. Расчет нового  опорного плана. Новый план получаем в результате

пересчета симплексной таблицы методом Жордана – Гаусса.

Далее переходим к этапу 2.

 

2. ПРАКТИЧЕСКИЙ РАЗДЕЛ

2.1. Содержательная постановка  задачи

Китайская компания с ограниченной ответственностью по производству гусеничных механизмов выпускает пять сходных друг с другом товаров – А, В, С и D. В нижеследующей таблице 2.1 представлены расходы ресурсов, необходимых для выпуска единицы каждого товара, а также недельные запасы каждого ресурса и цены продажи единицы каждого продукта.

Таблица 2.1

Исходные данные

Ресурсы	Товар				Недельный запас ресурсов
	А	В	С	D
Сырье, кг Сборка, ч  Обжиг, ч  Упаковка, ч	6,00 1,00 3 0,50	6,50 0,75 4,50 0,50	6,10 1,25 6 0,50	6,10 1,00 6 0,75	35000 6000 30000 4000
Цена продажи, ф.ст.	40	42	44	48