Математическая модель задачи ДЗ

(неканоническое представление)

Основные переменные и ограничения	Х1	Х2	Х3	Х4	Х5	Тип ограни-чений	Правые части огранич-й
1. Ресурс пашни
2.Трудовые ресурсы
3.Денежные ресурсы
4. Баланс кормов	-2.5			-50
5.Баланс концентр-в	-2.5
6.Б-с кормов(свиньи)	-2.5			-50
7.Поголовье коров
8.Произв-во свинины
9.Денежные затраты					-1	=
Коэффициенты целевой функции						max

Приведение задач линейного программирования к каноническому представлению.

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

Вначале каждому ограничению типа нестрогого неравенства " " или " " сопоставим свою дополнительную переменную. Проделаем это следующим образом.

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

Рассмотрим, например, процесс такого изменения для 8-го неравенства - типа " " (соответствующую дополнительную переменную обозначим Х₆). В результате придем к следующему представ­лению ограничения:

100*Х₃ – Х₆ =3000

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

Х₆ = 100*Х₅ - 3000

Именно в этом смысл термина "избыточная переменная".

От 1-го неравенства (типа " "), введя дополнительную переменную Х₇, придем к следующему ограничению:

X₁ + Х₄ * Х₇ = 900

Величина Х₇ в этом равенстве называется остаточной переменной. Ее значение показывает, насколько левая часть исходного неравенства (1) меньше правой:

X₇ = 900 – X₁ – X₄,

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

Помимо избыточных и остаточных переменных в левые части ограничения типа

" " и " = " вводят со знаком " + " еще дополнительные неотрицательные переменные, называемые искусственными.

Итак, в результате придем к следующей канонической системе ограничений (вформе уравнений):

Х₁ +Х₄ +Х₇ 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)

в которой X₁,...,X₅ - основные, Х₆ - избыточная, Х₇, …,Х₁₃, - остаточные и Х₁₄, Х₁₅ – искусственные переменные.

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

Уравнение целевой функции:

Z = 225*Х₁ + 800*Х₂ + 10*Х₃ – М*Х₁₄ – М*Х₁₅ max,

где M – большое число (больше остальных коэффициентов целевой функции).

Таблица 3

Последняя симплекс-таблица задачи ДЗ

(Zmах = 240538)

Номер строки	Базисные перем-е	Ном.огр. для доп.пер-х	Аiо	Коэффициенты замещения
Аi6(X14) (изб.огр.8)	Аi7(X7) (ост.огр.1)	(ост.огр.4)	(ост.огр.5)
	Х12(ОСТ.)			0.2831	6.15	-0.877	2.338
	Х8 (ОСТ.)			0.86	-10	0.2	-2.2
	Х9 (ОСТ)			1.478	-89.62	4.208	-12.05
	Х2 (ОСН.)	-	60.15	0.0035	0.0769	0.0015	0.029
	Х3 (ОСН.)	-		-0.01
	Х1 (ОСН.)	-	841.8	0.0025	0.923	0.0184	-0.049
	Х13(ОСТ.)		69.85	-0.0035	-0.077	-0.015	-0.029
	Х5 (ОСН.)	-		-1.478	89.62	-4.2	12.05
	Х4 (ОСН.)	-	58.15	-0.0025	0.0769	-0.018	0.049
(Zj – Cj)		2.385	269.2	5.385	12.31

К основным блокам информации относятся:

1). Собственно оптимальное решение - значения переменных, попавших в число базисных (см. 2-й и 4-й столбцы таблицы). Напомним, что небазисные переменные равны нулю.

2). Значения целевой функции, которое дается начальным элементом индексной строки - (Z₀-C₀), расположенным на пересечении столбца А_i0 и строки (Z_j-C_j). В данном случае оно равно 240538.

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

4). Коэффициенты замещения.