Обработка результатов эксперимента

15 16 17 18 19 20 21

Таблица 1.43

Таблица 1.42

Таблица 1.41

Таблица 1.40

Тогда

Таблица 1.39

	x₁₁	x₁₂	x₁₃	x₂₁	x₂₂	x₂₃
U₁
U₂
V₁
V₂
V₃
C

Тогда двойственная задача формулируется так:

максимизировать целевую функцию

F^*= 40U₁ + 25U₂ + 10V₁ + 35V₂ + 20V₃

при следующих ограничениях:

U₁ + V₁ 7,

U₁ + V₂ 2,

U₁ + V₃ 4,

U₂ + V₁ 3,

U₂ + V₂ 8,

U₂ + V₃ 9.

Заметим, что все ограничения исходной задачи имеют вид равенств, поэтому все переменные двойственной задачи (U₁, U₂, V₁, V₂, V₃) могут принимать отрицательные значения.

Напомним, что математическая модель (прямой) транспортной задачи имеет вид

F = min

при условиях

Математическая модель двойственной транспортной задачи в общем виде имеет вид

F^*= ® max

при условиях (в координатной форме)

U₁ + V₁ C₁₁,

U₁ + V₂ C₁₂,

......

U₁ + V_n C_1n,

U₂ + V₁ C₂₁,

U₂ + V₂ C₂₂,

......

U₂ + V_n C_2n,

......

U_m + V₁ C_m1,

......

U_m + V_n C_mn.

Пример. Для построения прямой задачи, состоящей в определении max целевой функции:

F =2 x₁ +7 x₂ max

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

(1.67)

- 2 x ₁ + 3 x ₂

14, (I)

x ₁ + x ₂ 8, (II)

составить двойственную задачу и найти решение обеих задач.

Рис. 1.14

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

(1.68)

- 2y₁ + y₂

2, (III)

3y₁ + y₂ 7, (IV)

;

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

F* = 14y₁ + 8y₂min.

Рис. 1.15

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

В прямой задаче max целевой функции достигается в точке A (X₁= 2; X₂ = 6) (рис. 1.14).

Минимальное значение целевая функция F* двойственной задачи принимает в точке K (рис. 1.15). Следовательно, Y*₁= 1, Y*₂= 4 - оптимальный план двойственной задачи и F*_min= 46.

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

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

Прямая задача:

F = x₁+ 14x₂+ 13x₃+ 12x₄min

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

- 3 x₁ + x₂ + 2 x₃ + 3 x₄ 1,

2 x₁ + 2 x₂ + x₃ - x₄ 1,

С учетом сделанных выше замечаний двойственная задача будет иметь вид

- 3y₁ + 2y₂ 1,

y₁ + 2y₂ 14,

2y₁ + y₂ 13,

3y₁- y₂ 12.

F* = y₁+ y₂max.

Будем решать эти задачи с помощью симплекс-метода. Для этого приведем ограничение и целевую функцию двойственной задачи к основному виду:

y₃= 1 - (- 3y₁ + 2y₂),

y₄= 14 - (y₁ + 2y₂),

y₅= 13 - (2y₁ + y₂),

y₆= 12 - (3y₁- y₂).

F* = 0 - (- y₁- y₂) max.

Для записи прямой задачи в симплексную таблицу двойственной задачи преобразуем эту прямую задачу таким образом:

- 3 x₁ + x₂ + 2 x₃ + 3 x₄ - x₅ = 1,

2 x₁ + 2 x₂ + x₃ - x₄ - x₆ = 1.

x₅ = - 1 - [ (- 3)(- x₁) + 1(- x ₂) + 2(- x₃) + 3(- x ₄) ],

x₆ = - 1 - [ 2(- x₁) + 14(- x₂) + 1(- x ₃) - 1(- x₄) ],

F = 0 - [ 1(- x₁) + 14(- x ₂) + 13(- x₃) + 12(- x ₄) ] min.

Далее записываем обе задачи в двойственную симплекс-таблицу (табл. 1.40).

	x _баз	x₅	x₆	B _y
y _баз	y₁	y₂	F
- x₁	y₃	-3
- x₂	y₄
- x₃	y₅
- x₄	y₆		- 1
B_x	F	- 1	- 1

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

	x _баз	x₂	x₃	B _y
	y _баз	y₄	y₅	F
- x₁
- x₅
- x₆
- x₄
B_x	F	1/3	1/3

Из этой таблицы находим решение двойственной пары:

max F = 9; min F = 9;

y₄= 0; y₅= 0; y₃= 3; y₁= 4; y₂= 5; y₆= 5.

x₁ = 0; x ₅= 0; x ₆= 0; x ₄= 0; x ₂= 1/3; x ₃= 1/3.

Окончательно прямая задача имеет следующее решение:

max F = 9;

x₁ = 0; x ₂= 1/3; x ₃= 1/3; x ₄= 0.

В заключение рассмотрим экономическую интерпретацию двойственных задач.

Пример [ 7 ].Для производства трех видов изделий A, B и C используются три различных вида сырья. Каждый из видов сырья может быть использован в количестве соответственно не больше 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в

табл. 1.42.

Вид сырья	Нормы затрат сырья на единицу продукции
A	B	C
I
II
III
Цена единицы продукции

Обозначим через x ₁ число производимых изделий A, x ₂- изделий B, x ₃- изделий C.

Тогда целевая функция будет: F = 10 x₁+ 14 x₂+ 12 x₃ max

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

4 x₁ + 2 x₂ + x₃ 180,

3 x₁ + x₂ + 3 x₃ 210,

x₁ + 2 x₂ + 5 x₃ 244,

Это прямая задача.

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

F* = 180y₁ + 210y₂+ 244y₃min.

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

4 y₁ + 3y ₂ + y₃ 10,

2y ₁ + y₂ + 2y ₃ 14,

y ₁ + 3y ₂ + 5y ₃ 12,

Чтобы найти решение этих задач, следует отыскать решение какой-либо одной из них. Находим решение прямой задачи. Опуская выкладки, имеем: оптимальным планом производства изделий является такой, при котором изготовляется 82 изделия B и 16 изделий C. При этом остается неиспользованным 80 кг сырья II вида, а общая стоимость составляет F = 1340 усл. ед.

Решение двойственной задачи дает следующие результаты:

y * ₁ = 23/4; y* ₂ = 0; y*₃=5/4; F* =1340.

Переменные y * ₁и y * ₃обозначают условные двойственные оценки единицы сырья I и III видов соответственно. Эти оценки отличны от нуля, а сырье I и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции.

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

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

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

23 + 5/4 > 10,

23/2 + 5/2 = 14,

23/4 + 25/4 = 12.

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

Второе и третье ограничения двойственной задачи выполняются как строгие равенства, что означает: двойственные оценки сырья, используемого для производства единицы соответственно B и C, равны в точности их ценам. Значит, их выпуск экономически целесообразен. Их производство и предусмотрено оптимальным планом прямой задачи.

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

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

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

		Производительность
		C₁	C₂	C₃	...	C_j	...	C_n
Век-	y₁	a₁₁	a₁₂	a₁₃	...	a_1j	...	a_1n	b₁	Ре-
тор	y₂	a₂₁	a₂₂	a₂₃	...	a_2j	...	a_2n	b₂
	...	...	...	...	...	...	...	...	...	сур-
оце-	y_i	a_i1	a_i2	a_i3	...	a_ij	...	a_in	b_i
нок	...	...	...	...	...	...	...	...	...	сы
	y_m	a_m1	a_m2	a_m3	...	a_mj	...	a_mn	b_m
		x₁	x₂	x₃	...	x_j	...	x_n
		План производства

Постройте математические модели двойственных задач по отношению к следующим задачам:

1. X₁+ 3X₃- 4X₅8,

X₁- 2X₂+ X₃+ 3X₄- 2X₅= 6,

2X₁+ 3X₂- 2X₃- X₄+ X₅4,

F = X₁- 2X₂+ X₃- X₄+ X₅min.

2. X₁- 2X₂+ 3X₄+ X₅= 8,

X₁+ X₃+ X₄- 2X₅= 6,

F = - 2X₂+ X₄+ 3X₅max.

3. X₁- 2X₂+ X₄= 8,

X₁+ X₃- 3X₄= 6,

F = - 3X₂- X₄max.

4. 2X₁- X₂+ X₃- 3X₄- X₅= 10,

X₁+ 2X₂- X₃+ 2X₄+ X₅8,

2X₁ - X₂+ 3X₃- X₄+ 2X₅4,

F = 2X₁- X₂+ X₃- 3X₄+ X₅min.

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

5. - X₁+ 3X₂6,

3X₁- X₂6,

F = X₁+ X₂max.

6. - 2X₁+ X₂2,

X₁- X₂2,

F = 2X₁+ X₂max.

7. 3X₁- X₂1,

- X₁+ 3X₂5,

F = 2X₁+ X₂min

8. - X₁+ 2X₂+ X₃= 4,

X₁- X₂+ X₄= 3,

F = 3X₁+ X₂max

9. X₁- X₂1,

X₁- X₂1,

F = X₁- X₂max.

10. 3X₁+ 5X₂+ X₃+ X₄= 32,

X₁- 3X₂- X₃+ X₄= - 8,

F = 3X₁- X₂- X₃+ X₄max.

Найдите решение двойственной задачи, используя решение исходной задачи, полученное симплекс-методом:

11. - X₁+ X₂+ X₃= 1,

X₁- X₂+ X₄= 1,

X₁ + X₂+ X₅= 2.

F = 2X₁- X₂+ 3X₃- 2X₄+ X₅max.

12. X₁+ 2X₂- X₃+ X₄= 0,

2X₁- 2X₂+ 3X₃+ 3X₄= 9,

X₁ - X₂+ 2X₃- X₄= 0.

F = - 3X₁+ X₂+ 3X₃- 34X₄min.

13. 5X₁+ 12X₂+ 2X₃= 9,

3X₁+ 10X₂+ 4X₃= 11,

F = - 2X₂+ X₄+ 3X₅max.

14. X₁+ 4X₂+ X₃= 2,

X₁+ 2X₂- X₃= 0,

F = X₁+ 10X₂+ 8X₃max.

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

1. Аппроксимации – экспериментальные точки надо соединить плавной кривой и подобрать ее функциональное выражение (рис. 2.1,а).

2. Интерполяции – на основе обработки экспериментальных данных требуется найти координату какой-либо неизвестной точки (x, y) на данном интервале, в пределах диапазона измеряемой величины (рис. 2.1,б).

3. Экстраполяции – на основе обработки экспериментальных данных требуется найти координату какой-либо неизвестной точки (x, y) за пределами диапазона измеряемой величины (рис. 2.1,в).

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

Рис. 2.1

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

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

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

Основная идея МНК заключается в следующем. Пусть результаты измерений представлены значениями:

X	x₁	x₂	…	x_n
Y	y₁	y₂	…	y_n

И пусть y = j(x) - искомая эмпирическая формула.

Требуется так подобрать параметры функции j(x), чтобы разности j(x_i) – y_i (i= 1, n) были наименьшими. Так как разности могут быть как положительными, так и отрицательными (рис. 2.2), то за критерий качества аппроксимации принимают наименьшую сумму квадратов разностей:

(2.1)

Рассмотрим наиболее часто встречающиеся на практике случаи, когда функция j(x):

1). линейная;

2). квадратическая (парабола);

3). гиперболическая.

Рис. 2.2

Аппроксимация линейной функцией

Пусть из опыта получена следующая совокупность значений x_i и y_i: i= 1, n. Требуется подобрать по МНК параметры a₀ и a₁ линейной функции y = a₀x + a₁, изображающей данную экспериментальную зависимость. Найдем значения a₀ и a₁, при которых достигается минимум суммы квадратов отклонений.