2. Тогда структурный вид двойственной задачи будет иметь вид:

Например, дана задача линейного программирования

Таблица 32

y1	1.	Х 1	+ х2	<	1000	B1
Y2	2.	100х1	+ 150 х2	<	1200	B2
Y3	3.	-10х1	+ 40х2	<	100	B3
Y4	4.		Х2	<	300	B4
Z

Соответствующая ей двойственная задача будет иметь вид:

у₁ > 0; у₂ > 0; у₃ > 0; у₄ > 0;

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

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

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

Пределы устойчивости оптимального решения при изменении коэффициентов целевой функции (С_j.)

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

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

Изменение коэффициентов в целевой функции при переменной, вошедшей в базисное решение.

При изменении коэффициента целевой функции на величину изменятся только элементы индексной строки:

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

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

Изменение коэффициента в целевой функции при переменной, не вошедшей в базисное решение

Изменение коэффициента при небазисной переменной приводит к изменению только одного элемента индексной строки, соответствующей этой переменной.

, где - величина, на которую был изменен коэффициент .

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

Демонстрационная задача (ДЗ): (Безгинов А.Н., «Линейные модели»).

В хозяйстве сложились следующие основные отрасли: молочное скотоводство (коровы), свиноводство, кормопроизводство и производство зерна. На продажу используется 90% зерна, остальное на корм скоту. В соответствии с планом поставок хозяйство должно произвести не менее трех тонн свинины. По условиям содержания животных хозяйство может содержать не более 110 коров. Общая площадь пашни в хозяйстве – 900 га. Запас кормов на пастбищах и сенокосах 1000 ц.к.е. другие исходные данные приведены в таблице 33.

Таблица 33

Исходные данные по некоторым ресурсам и технологическим коэффициентам для задачи ДЗ

Виды ресурсов, норм и т.д., единицы измерения	Нормативные коэффициенты для различных отраслей хозяйства				Ресурсы хозяйства
	Производство зерна	Скотоводство	Свиноводство	Производство кормов
Трудозатраты					40000
чел. ч./га,	5			50
чел. ч./гол.		50	100
Ден. затраты					90000
тыс.руб/га	70			300
тыс.руб/гол		25	100
Урожайность, ц.к.е./га	25			50
Нормы кормления, ц.к.е./гол: Общая		80	40
Концентраты		30	10
Продуктив-ность, л/гол		4000
кг/гол			100
Чистый доход, тыс.руб/ц.к.е.	10
тыс.руб/л		0,2
тыс.руб/кг			1

Доход хозяйства определяется продажей молока, свинины и части зерна. Необходимо определить оптимальное сочетание отраслей хозяйства. В ходе расчетов вычислить общий объем реальных денежных расходов хозяйства. Баланс кормов составить по всем видам животных, а также отдельно по коровам и свиньям.

В соответствии с исходными данными, сформируем группу основных переменных:

Х₁ – площадь пашни под зерновыми, га;

X₂ – поголовье коров, гол;

Х₃ – поголовье свиней, гол;

Х₄ - площадь пашни под кормовыми культурами, га;

X₅ – общие реальные денежные расходы хозяйства, руб.

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

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

Z = 10*0,9*25*X₁ + 0.2*4000*X₂ + 1*100*X₃ = 225*X₁ +800*X₂ + 100*X₃ .

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

1. Ограничение по площади пашни (учитываются все культуры, под которые отводится пашня).

Х₁ + Х₄ 900

2. Ограничение по трудовым ресурсам.

В соответствии с нормами трудозатрат (первая строка табл.1) имеем:

5*Х₁ + 50*Х₂ + 100*Х₃ + 50*Х₄ 40000

3. Ограничение по денежным ресурсам.

Х₅ 90000

4. Ограничение по кормовому балансу.

Общий вид ограничения таков:

«потребность в кормах” “производство кормов”

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

Конкретные ограничения составляются следующим образом.

По всем видам животных:

80*Х₂ + 40*Х₃ 0,1*25*Х₁ + 50*Х₄ + 1000

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

По концентратам:

30*Х₂ + 10*Х₃ 2,5*Х₁

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

5. Отдельно по коровам (по всем видам кормов):

80*Х₂ 2,5*Х₁ + 50*Х₄ + 1000

6. Отдельно по свиньям (по всем видам кормов):

40*Х₃ 2,5*Х₁ + 50*Х₄

7. Ограничение по поголовью коров:

Х₂ 110

8. Ограничение по гарантированному производству свинины:

100*Х₃ 3000

9. Уравнение для расчета общих денежных затрат (см. вторую строчку табл. 1):

70*Х₁ + 25*Х₂ + 100*Х₃ + 300*Х₄ = Х₅

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

С учетом всего сказанного получим следующую систему ограничений:

Х₁ + Х₄ 900 (1)

5*Х₁ + 50*Х₂ + 100*Х₃ + 50*Х₄ 40000 (2)

Х₅ 90000 (3)

-2,5*Х₁ + 80*Х₂ + 40*Х₃ - 50*Х₄ 1000 (4)

-2,5*Х₁ + 30*Х₂ + 10*Х₃ 0 (5)

-2,5*Х₁ + + 40*Х₃ – 50*Х₄ 0 (6)

Х₂ 110 (7)

100*Х₃ 3000 (8)

70*Х₁ + 25*Х₂ + 100*Х₃ + 300*Х₄ = 0 (9)

Добавим к этой системе требование, накладываемое на целевую функцию:

Z = 225*Х₁ + 800*Х₂ + 100*Х₃ max, (10)

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

Х 0, j = 1,…,5. (11)

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

Z =

i=1,…,m,

где m – общее число ограничений;

n – общее число основных переменных, а символ означает либо “ ” либо “ ” либо “ = ”.

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

Таблица 2