1. Принципы моделирования и анализа экономических процессов.

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

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

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

Основные этапы ИО:

1. Постановка задачи или построение описательной модели системы, явления или операции. Это наиболее ответственный этап ИО. В результате его выполнения определяются:

- набор показателей, достаточно полно характеризующих операцию (целенаправленное действие);

- способ ведения операции, при котором:

а) показатели операции не выходят за границы допустимой области;

б) целевая функция операции достигает наилучшего значения.

2. Построение математической модели. Этот этап включает в себя:

- формализацию показателей операции;

- определение (формализацию) допустимой области их изменения;

- построение целевой функции, определяющей эффективность операции.

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

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

4. Анализ модели и получение решения. Анализ модели производится:

а) при помощи методов и алгоритмов исследования условных экстремальных задач;

б) посредством статистического моделирования (метод Монте-Карло);

в) с помощью экспертных оценок;

г) по результатам специально организованных деловых игр.

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

6. Корректировка модели и решения. Для выполнения этого этапа используются ретроспективные данные или непосредственные практические испытания. При этом возможно неоднократное обращение к работам предыдущих этапов.

7. Реализация результатов решения. Задача исследователя операций – подготовить решение. Однако, работы по ИО имеют смысл, если они завершаются внедрением результатов исследования в производство. Поэтому исследователь должен обходиться более простыми методами, пользоваться убедительными аргументами, наглядно формулировать выводы.

Основные типы операций

В зависимости от изучаемого процесса, задачи и методы ИО разбиваются на следующие классы:

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

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

3. Операции на сетях и операции календарного планирования. Это область ИО, которая занимается исследованием и решением разнообразных проблем, связанных с системой, представимой в виде графа.

4. Конфликтные ситуации. Здесь исследуются модели принятия решений в условиях конфликта и неопределенности.

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

2. Производственная интерпретация задачи линейного программирования (ЛП).

ЗЛП можно рассматривать как аналитическое описание содержательной задачи, отражающее структуру и функционирование некоторой производственно-экономической системы (в дальнейшем: система-предприятие), что позволяет описывать самые разнообразные экономические и плановые задачи.

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

- технологией (экология);

- организацией (социальные аспекты);

- видом выпускаемой конечной продукции.

Каждый способ производства характеризуется:

а) набором нормативов затрат некоторых ресурсов (традиционные: живой труд, оборудование, сырье, электроэнергия, материалы; дополнительно: ресурсы экологические и социальные и так далее). Здесь заданы наличные объемы ресурсов ­– ;

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

Приведем пример агрегатов отраслей:

1. машиностроение и металлообработка;

2. строительство;

3. металлургия и химия;

4. топливо и энергия;

5. транспорт и связь;

6. сельское и лесное хозяйство.

И нормативы затрат ресурса, и нормативы выпуска конечного продукта берутся в расчете на единицу интенсивности применения способа, то есть это удельные затраты ресурса и удельный выпуск продукции. Задаются эти величины в виде так называемой матрицы затрат и выпуска продукции , – количество ограничений задачи. В) Кроме того, известен некоторый удельный показатель эффективности применения способа производства – вектор эффективности .

Таким образом, каждый способ производства на предприятии будет представлен системой нормативов затрат ресурсов (выпуска продукции) и результатов (эффективности) на единицу интенсивности применения способа: .

Обозначим через – количество единиц интенсивности применения способа (например, количество единиц продукции или показатели структуры производства).

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

.

Таким образом, различные комбинации дадут нам структуру затрат ресурсов и выпусков продукции, соответствующую плану .

Пусть рассматриваемая система-предприятие имеет:

- видов ресурсов, по которым требуется выполнение нестрогого баланса: не допускается превышение затрат ресурса над наличным объемом; тип ограничений ; объемы ресурсов ;

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

- видов продукции, выпускаемой по госзаказу; тип ограничений ; объемы госзаказа по продукции ;

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

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

,

где: – удельные затраты ресурса при использовании способа,

дает нам выражение суммарных затрат ресурса в плане задачи, а ограничения

, (1)

(2)

будут выражать условия соблюдения балансов по ресурсам.

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

(3)

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

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

При записи модели технологические ограничения обычно не выделяют в особую группу, а включают в соответствии с типом ограничения в (1), (2) или (3).

Целевая функция выражает суммарный искомый эффект предприятия при данном плане :

. (4)

Условие неотрицательности:

. (5)

Таким образом, задача ЛП в постановке (1)-(5) представляет собой задачу нахождения такого плана предприятия (набора интенсивностей использования способов производства), который удовлетворял бы:

а) условиям сбалансированности по всем видам ресурсов;

б) требуемым объемам выпуска продукции;

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

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

В эту общую схему планирования вписываются разнообразные частные задачи планирования и управления производством.

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

3. Табличная форма общей задачи ЛП.

При построении, численной реализации и анализе ЛП-модели очень важно одновременное представление ее формальной структуры и содержательного смысла: вид и структура ограничений, целевой функции, наименование и единицы измерения искомых переменных, показателей затрат и выпуска, объемы ресурсов, требуемых выпусков продукции. Это достигается системным упорядочиванием исходных условий задачи ЛП в таблице стандартной формы.

№ условий	Единицы измерения	Перечень и структура способов					Тип отно- ше- ния	Правая часть усло- вий	Содержание условий	Тип условия
		способ №1 <…>	способ №2 <…>	способ №3 <…>		способ № <…>
	перемен- ных условий				…
		<…>	<…>	<…>	…	<…>
0	<…>				…		=	max	<…>
1	<…>				…		≤		<…>	I. ресурсное нестрогое
…	…	…	…	…	…	…	…	…	…
	<…>				…		≤		<…>
	<…>	…	…	…	…	…	=	…	<…>	II. ресурсное строгое
	<…>	…	…	…	…	…	=	…	<…>
…	…	…	…	…	…	…	…	…	…
	<…>	…	…	…	…	…	=	…	<…>
	<…>	…	…	…	…	…	≥	…	<…>	III. госзаказ
	<…>	…	…	…	…	…	≥	…	<…>
…	…	…	…		…	…	…	…	…
	<…>	…	…	…	…	…	≥	…	<…>

4.Каноническая форма задачи ЛП.

Каноническая задача ЛП является частным случаем основной ЛП-модели (1)-(5).

Отметим, что определение термина «каноническая задача» не является общепринятым в ЛП.

Определение 1 Линейная система уравнений (ЛСУ) называется системой с базисом, если в каждом уравнении есть переменная, отсутствующая во всех остальных уравнениях и имеющая в данном уравнении коэффициент, равный единице (базисные переменные, базис; остальные - свободные).

Определение 2 ЛСУ будем называть канонической, если она является системой с базисом и свободные члены ее уравнений неотрицательны.

Определение 3 Задачу ЛП будем называть канонической, если ограничения представляют собой каноническую систему, а целевая функция выражена только через свободные неизвестные.

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

Задача ЛП, содержащая только ограничения типа легко сводится к канонической форме введением дополнительных переменных, приводящих условие-неравенство в строгое равенство:

(6)

Переменные имеют смысл недоиспользования ресурсов .

Каноническая задача ЛП решается стандартным симплекс-методом; опорное решение (первоначальный план) имеет вид .

Симплекс таблица для задачи (6) имеет вид:

Таблица 1.2 – Симплекс таблица для задачи (6)

		0		…		0	0	…	0
				…				…
0				…		1	0	…	0
0				…		0	1	…	0
…	…	…	…	…	…	…	…	…	…
0				…		0	0	…	1
строка		0,		…		0	0	…	0

Для канонической ЗЛП строка: в столбце стоит значение ноль или ; в столбцах замещения стоит .

Рассмотрим случай, когда ЗЛП представлена канонической системой условий (ЛСУ с базисом и ), а содержит базисные неизвестные. Тогда, выражая базисные неизвестные из через свободные, можно получить каноническую ЗЛП.

Получим правило пересчета на примере следующей ЗЛП:

(7)

Выразим базисные неизвестные ( , ) через свободные ( , ) и подставим в выражение для .

Обозначим . Тогда , то есть получили каноническую ЗЛП. Симплекс таблица для задачи (7) имеет вид:

Таблица 1.3 – Симплекс таблица для задачи (7)

		0
					1	0
					0	1
строка					0	0

Таким образом правило для пересчета строки в симплекс-таблице для ЗЛП с канонической системой ограничений и любой следующее:

- крайний левый элемент строки (столбец ) равен скалярному произведению на плюс и имеет смысл значения целевой функции на данном базисе;

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

Правило пересчета элементов матрицы на каждом шаге симплекс-метода – это формализация аналогичного процесса, когда мы выражаем новые базисные переменные через свободные.

5. Содержательная интерпретация алгоритма симплекс-метода.

Алгоритм симплекс-метода для ЗЛП на максимум с канонической системой ограничений

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

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

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

4. Выбираем разрешающий столбец ,

,

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

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

6. Заполняем новую симплекс-таблицу:

а) в вместо ставим ;

б) элементы разрешающего столбца полагаем равными нулю, на месте разрешающего элемента – единица;

в) элементы разрешающей строки равны элементам старой таблицы разделить на разрешающий элемент, таким образом, в будет стоять интенсивность способа или недоиспользование ресурса, или объем выпуска;

г) строки, для которых в разрешающем столбце ноль, и столбцы, для которых в разрешающей строке ноль, переписываются без изменения;

д) пересчитываем значения остальных элементов симплекс-таблицы, включая столбец свободных членов, по правилу:

новый элемент = старый элемент – (элемент разрешающей строки х

х элемент разрешающего столбца)/разрешающий элемент

или

.

Заметим, коэффициенты в строке, посчитанные по правилам п.1 и п.6 совпадают. Это можно использовать как тест на правильность заполнения симплекс-таблицы.

7. переходим на п.1 алгоритма, рассчитываем коэффициенты строки.

Примечания:

1. Числа в столбце – значения базисных переменных.

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

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

4. Признаком вырожденности решения является наличие в столбце свободных членов хотя бы одного нулевого элемента. Такая ситуация возникает, когда при выборе разрешающей строки получаем 2 (или несколько) одинаковых минимальных отношений . Следствием может быть зацикливание процедуры поиска оптимального плана. Симплекс-метод не требует строгой положительности , то есть , поэтому, в принципе, возможно появление конечного набора допустимых базисных решений, который будет повторяться в циклическом порядке. С другой стороны, симплекс-метод – «метод последовательного улучшения плана». Улучшение от шага к шагу предполагает, что базис, получившийся на предыдущем шаге, не появится в дальнейшем при последующих итерациях. Таким образом, алгоритмом симплекс-метода ситуацию зацикливания получить можно, но устранить нельзя. Отсюда, чтобы устранить зацикливание (или ликвидировать вырожденность матрицы условий), надо скорректировать исходную задачу так, чтобы «улучшалась». Для этого в исходной задаче к прибавляют , чтобы избежать возможности одновременного появления нескольких минимальных отношений при выборе .

Содержательная интерпретация коэффициентов в z-строке, основанная на теории двойственности, такова:

1. Для основных переменных степень нерентабельности продукции.

2. Для дополнительных переменных степень дефицитности ресурсов.

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

Коэффициенты в z-строке в столбцах замещения для этих переменных показывают степень напряженности плановых заданий.

6.Метод искусственного базиса (сведение основной задачи к 2-м каноническим, сведение основной задачи к задаче со смешанным базисом).

Сведение основной задачи ЛП к двум каноническим

Исходная задача (8) решается в два этапа.

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

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

2. в качестве целевой функции на первом этапе берется

Получим:

(10)

Задача (10) решается симплекс-методом. При этом имеют место следующие утверждения, которые мы примем без доказательств.

Утверждение 1 Для того, чтобы линейная система условий исходной задачи (8) обладала планами необходимо и достаточно, чтобы минимальное значение вспомогательной задачи было равно нулю, то есть в оптимальном плане искусственные переменные отсутствуют.

Утверждение 2 Если линейная система условий исходной задачи (8) обладает планами, то существует равносильная ей каноническая система, которую можно получить из последней симплекс-таблицы вспомогательной задачи.

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

Переход ко второму этапу осуществляется следующим образом:

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

б) значения коэффициентов функции цели заменяются на исходные из задачи (8) в строке и столбце ;

в) осуществляется переход к п.1 алгоритма симплекс-метода – расчет строки, и задача решается симплекс-методом.

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

1.5 Сведение общей задачи лп к задаче со смешанным базисом

Пусть дана задача ЛП в виде (1)-(5):

Последовательно выполняем следующие действия:

1. вводим дополнительные переменные со знаком минус (перевыполнение плана) в ограничения типа :

2. вводим в ограничения типа дополнительные переменные со знаком плюс (недоиспользование ресурсов):

3. вводим в ограничения типа искусственные переменные (недовыполнение плана, невязка по ресурсу):

а) исходные ограничения:

б) вновь полученные ограничения:

4. вводим в функцию цели искусственные переменные с коэффициентом и со знаком минус:

по п.п 2,3,4 строим симплекс-таблицу.

0

…

0

…

0

0

…

0

…

…

…

…

…

…

…

0

…

0

…

0

1

…

0

0

…

0

0

…

0

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

0

…

0

…

0

0

…

1

0

…

0

0

…

0

…

0

…

0

0

…

0

1

…

0

0

…

0

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

0

…

0

0

…

0

0

…

1

0

…

0

…

-1

…

0

0

…

0

0

…

0

1

…

0

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

0

…

-1

0

…

0

0

…

0

0

…

1

строка

7.Двойственные задачи ЛП.

Симметричные двойственные задачи

Прямая: Двойственная:

(1) (2)

Производственная интерпретация:

а) прямая – из общей задачи ЛП, рассмотренной ранее, без плановых, строгих ресурсных и технологических ограничений.

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

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

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

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

Несимметричные двойственные задачи

(3) (4)

Задача (3) – основная ЗЛП, задача (4) – стандартная задача минимизации, но на переменные не накладываются условия неотрицательности.

Определение 1 Всякое решение системы неравенств задачи (4) называется псевдопланом.

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

Замечание Пару несимметричных задач легко свести к паре симметричных, заменив каждое равенство парой неравенств , .

Запишем теперь более общую ЗЛП:

(5)

Двойственная задача к задаче (5) строится по правилам:

1. ограничения типа сводятся к ;

2. записывается двойственная как для (1), если есть ограничение типа , то на соответствующую переменную двойственной задачи не накладывается ограничение на знак. Тогда:

Прямая: Двойственная:

9. Объективно обусловленная оценка, как мера дефицитности ресурса, допустимые пределы варьирования лимитом ресурса.

Итак, для ЗЛП смешанного типа имеем -строку вида:

основные – интенсивность способов

перевы-полнение плана

недоисполь- зование ресурсов

невязки по ресурсам, искусственные

недовыполнение плана, искусственные

шапка

…

…

…

…

…

-строка

оценка нерента-бельности продукции

оценка напряженности плановых заданий

оценка дефицитности ресурсов

Коэффициенты, стоящие в z-строке, называются оценками соответствующих переменных и используются двояко:

1) Оценка используется как мера дефицитности ресурсов, нерентабельности способов, напряженности плановых заданий (по второй теореме двойственности):

- ресурс полностью использованный имеет оценку, не равную нулю; оценка частично использованного ресурса равна нулю;

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

Численное значение оценки указывает на степень дефицитности, нерентабельности, напряженности: чем больше оценка, тем больше степень (для задач на min – больше по абсолютной величине).

2) Оценка используется как мера влияния ограничений на функцию цели (по первой теореме двойственности):

- оценка дефицитного ресурса показывает, насколько численно улучшится значение функции цели при приросте ресурса на единицу;

- для плановой продукции оценка напряженности планового задания показывает, насколько ухудшится значение функции цели, если план увеличить на единицу.

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

2.2.1 Рассмотрим, как ведет себя свободная переменная при увеличении

ресурса .

Запишем исходное ограничение по ресурсу :

(1)

Теперь увеличим ресурс, подставим в (1):

и преобразуем:

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

Определим допустимый предел увеличения . «Допустимый», то есть не меняющий базис; базис изменится в тот момент, когда, по крайней мере, одна переменная станет равной нулю. Для любой базисной переменной справедливо равенство (мы работаем с оптимальным планом, поэтому вместо - , вместо - ):

(2)

где: и - это множество номеров соответственно свободных и базисных переменных; - номер ограничения.

Перепишем (2), имея в виду, что из всех свободных переменных, только :

здесь - столбец замещения переменной .

Чтобы базис не изменился, потребуем:

(3)

Так как , изменить базис могут только те коэффициенты столбца замещения , для которых .

Таким образом, нижняя граница (так как уменьшается) равна:

(4)

Тогда верхняя граница увеличения ресурса равна:

(5)

2.2.2 Рассмотрим как ведет себя при уменьшении дефицитного ресурса . Если уменьшается - , то его недоиспользование увеличивается на ту же величину, то есть .

Запишем (2), имея в виду, что из всех свободных только и потребуем выполнения условия неизменности базиса:

Так как , изменить базис могут те коэффициенты столбца замещения, для которых .

Тогда верхняя граница увеличения вычисляется так:

(6)

Объединяя (4) и (6) запишем допустимый интервал варьирования переменной, означающей недоиспользование ресурса:

(8)

Нижняя граница уменьшения ресурса:

(7)

Объединяя (5) и (8) получим пределы изменения дефицитного ресурса:

(9)

10. Оценка нерентабельности продукции; допустимые пределы выпуска продукции.

Итак, для ЗЛП смешанного типа имеем -строку вида:

основные – интенсивность способов

перевы-полнение плана

недоисполь- зование ресурсов

невязки по ресурсам, искусственные

недовыполнение плана, искусственные

шапка

…

…

…

…

…

-строка

оценка нерента-бельности продукции

оценка напряженности плановых заданий

оценка дефицитности ресурсов

Коэффициенты, стоящие в z-строке, называются оценками соответствующих переменных и используются двояко:

1) Оценка используется как мера дефицитности ресурсов, нерентабельности способов, напряженности плановых заданий (по второй теореме двойственности):

- продукция, вошедшая в оптимальный план рентабельна, оценка нерентабельности – ноль; нерентабельная продукция имеет ненулевую оценку;

Численное значение оценки указывает на степень дефицитности, нерентабельности, напряженности: чем больше оценка, тем больше степень (для задач на min – больше по абсолютной величине).

2) Оценка используется как мера влияния ограничений на функцию цели (по первой теореме двойственности):

- оценка нерентабельной продукции показывает, насколько ухудшится значение функции цели, если включить в производство единицу нерентабельной продукции;

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

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

Корректировка по нерентабельной продукции

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

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

при , то есть

11.Допустимые пределы варьирования плана выпуска продукции; степень жесткости плановых заданий.

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

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

или

Таким образом, при увеличении гарантированного выпуска перевыполнение плана увеличивается на ту же величину и .

Запишем условие неизменности базиса:

При имеем аналогично (6):

(10)

Найдем верхнюю границу гарантированного выпуска:

(11)

2.3.2 Рассмотрим, как ведет себя при уменьшении плана, то есть .

Запишем из исходной системы:

или

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

Тогда аналогично (4) имеем:

(12)

Отсюда нижняя граница гарантированного выпуска равна:

(13)

Объединяя (10) и (12) получим допустимый интервал варьирования переменной, означающей перевыполнение плана:

(14)

Объединяя (11) и (13) получим пределы изменения гарантированного выпуска:

Итак, для ЗЛП смешанного типа имеем -строку вида:

основные – интенсивность способов

перевы-полнение плана

недоисполь- зование ресурсов

невязки по ресурсам, искусственные

недовыполнение плана, искусственные

шапка

…

…

…

…

…

-строка

оценка нерента-бельности продукции

оценка напряженности плановых заданий

оценка дефицитности ресурсов

Коэффициенты, стоящие в z-строке, называются оценками соответствующих переменных и используются двояко:

1) Оценка используется как мера дефицитности ресурсов, нерентабельности способов, напряженности плановых заданий (по второй теореме двойственности):

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

Численное значение оценки указывает на степень дефицитности, нерентабельности, напряженности: чем больше оценка, тем больше степень (для задач на min – больше по абсолютной величине).

2) Оценка используется как мера влияния ограничений на функцию цели (по первой теореме двойственности)

- для плановой продукции оценка напряженности планового задания показывает, насколько ухудшится значение функции цели, если план увеличить на единицу.

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

12.Корректировка оптимального плана по ресурсу и продукции.

Корректировка оптимального плана по ресурсу

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

2.2.1 Рассмотрим, как ведет себя свободная переменная при увеличении

ресурса .

Запишем исходное ограничение по ресурсу :

(1)

Теперь увеличим ресурс , подставим в (1):

и преобразуем:

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

Определим допустимый предел увеличения . «Допустимый», то есть не меняющий базис; базис изменится в тот момент, когда, по крайней мере, одна переменная станет равной нулю. Для любой базисной переменной справедливо равенство (мы работаем с оптимальным планом, поэтому вместо - , вместо - ):

(2)

где: и - это множество номеров соответственно свободных и базисных переменных; - номер ограничения.

Перепишем (2), имея в виду, что из всех свободных переменных, только :

здесь - столбец замещения переменной .

Чтобы базис не изменился, потребуем:

(3)

Так как , изменить базис могут только те коэффициенты столбца замещения , для которых .

Таким образом, нижняя граница (так как уменьшается) равна:

(4)

Тогда верхняя граница увеличения ресурса равна:

(5)

2.2.2 Рассмотрим как ведет себя при уменьшении дефицитного ресурса . Если уменьшается - , то его недоиспользование увеличивается на ту же величину, то есть .

Запишем (2), имея в виду, что из всех свободных только и потребуем выполнения условия неизменности базиса:

Так как , изменить базис могут те коэффициенты столбца замещения, для которых .

Тогда верхняя граница увеличения вычисляется так:

(6)

Объединяя (4) и (6) запишем допустимый интервал варьирования переменной, означающей недоиспользование ресурса:

(8)

Нижняя граница уменьшения ресурса:

(7)

Объединяя (5) и (8) получим пределы изменения дефицитного ресурса:

(9)