1. Каждому неравенству системы ограничений исходной задачи поставить в соответствие переменную двойственной задачи - u_i.

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

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

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

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

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

7. Целевая функция двойственной задачи меняет свое значение на сходное. Если целевая функция исходной задачи стремится к максимуму (Z max), то целевая функция двойственной задачи - к минимуму (W min), и наоборот.

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

Запишем исходную задачу, поставив каждому ограничению исходной задачи в соответствие переменную двойственной:

Найти решения Х (Х₁, …, Х_j, …, X_n), удовлетворяющие следующей системе неравенств (задача 1):

u₁ а₁₁х₁ + … + а_1j х _j + … + а_1n x_n а ₁₀,

u_i а_i1х₁ + … + а _{i j} х _j + … + а _{i n} x_n а_{i 0},

u_r а _r1х₁ + … + а _rj х _j + … + а _rn x_n а _r0

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

х _j 0, j = 1, …, n, где i = 1, …, r,

для которого целевая функция:

Z = C₁х₁ + … + C_jх _j … + C _nx_n + C₀

достигает максимума.

Запишем двойственную задачу: найти решение U (u₁, ..., u_i, …, u_r), удовлетворяющее системе неравенств (задача 2):

а₁₁u₁ + … + а_i1u_i + … + а _r1 u_r C₁,

а_1j u₁ + … + а _{i j} u_i + … + а _rj u_r C_j,

а_1n u₁ +… + а _{i n}u_i + … + а _rn u_r C _n

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

u_i 0, i = 1,…, r, для которого

W = а₁₀u₁ + … + а_i0u_i + … + а _r0 u_r + C₀.

Задача (2) является двойственной к задаче (1).

Основная теорема двойственности:

1. Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений Х_опт и U_опт выполняется равенство Z_max = W_min.

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

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

Запишем исходную и двойственную задачи в канонической форме и приведенные к единичному базису.

Исходная задача:

а₁₁х₁ + … + а_1j х _j + … + а_1n x_n + x_n+1 = а ₁₀ ,

а_i1х₁ + … + а _{i j} х _j + … + а _{i n} x_n + x_{n+ I} = а_{i 0} ,

а _r1х₁ + … + а _rj х _j + … + а _rn x_n + x_{n+ r} = а _r0 .

Х _j 0, j = 1 ч n, Х_{n+ i} 0, где i = 1 ч r .

Двойственная задача:

-а₁₁u₁ - … - а_i1u_i - … - а _r1u_r + u_r+1 = -C₁,

-а_1j u₁ - … -а _{i j} u_i - … - а _rju_r + u_r+j = -C_j,

-а_1n u₁ - … - а _{i n}u_i - … -а _rnu_r u_{r+ n} = -C _n.

u_i 0, i = 1ч r, u_r+j 0, j = 1ч n.

Теперь можно записать соответствие переменных:

х₁ … х _j … x_n x_{n + 1. .} x_{n + i.} x_{n + r}

u_{r + 1 …}u_{r + j …}u_{r + n} u_{1 . . .} u_{i ….} u_r

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

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

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

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

Исходная задача: х1 + х2 1, (-1) х1 + х2 2, Хj 0, j = 1ч2. Zmax = х1 - х2	u1 -х1 - х2 -1, u2 х1 + х2 2, Хj 0, j = 1 ч 2. Zmax = х1 - х2.	-х1 - х2 + х3 = -1, х1 + х2 + х4 = 2, Хj 0, j = 1 ч 4. Zmax = х1 - х2 + 0 • х3 + 0• х4.
Двойственная задача -u1 + u2 1, (-1) -u1 + u2 -1, ui 0, i = 1ч2. Wmin = -u1 + 2 u2.	u1 - u2 -1 (-1), u1 - u2 1, ui 0, i = 1ч 2. Wmin = -u1 + 2 u2.	u1 - u2 + u3= -1, u1 - u2 + u4 = 1, ui 0, i = 1ч 4. Wmin = -u1 + 2 u2 + 0 • u 3 + 0 • u 4.

Соответствие переменных:

Свободные переменные исходной задачи	Базисные переменные исходной задачи

х₁ х₂ х₃ х₄

u₃ u₄ u₁ u₂

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

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

х₁ + х₂ - х₃ + у₁ = 1,

х₁ + х₂ + х₄ = 2,

х_j 0, j = 1ч 4.

Т_max= х₁ - х₂ - Му₁.

Таблица 3.14 Первая симплексная таблица

Св.П	Cj	0	1	-1	0
Б.П.	Ci	ai0	X1	X2	X3	ai0/aip
У1	-М	1	(1)	1	-1	1<
X4	0	2	1	1	0	2
Z		0	-1	1	0
	М	-1	-1	-1	1

_{Таблица 3.15 Вторая симплексная таблица}

Св.П	Cj	0	-1	0
Б.П.	Ci	ai0	X2	X3	ai0/aip
Х1	1	1	1	-1
X4	0	1	0	(1)
Z		1	2	-1

Выбор разрешающего столбца и разрешающей строки происходит однозначно.

_{Таблица 3.16 Оптимальное решение}

Св.П	Cj	0	-1	0
Б.П.	Ci	ai0	X2	X4	ai0/aip
Х1	1	2	1	1
X3	0	1	0	1
Z		2	2	1

В табл. 3.16 получено оптимальное решение:

Z_max = 2 при X_opt(2, 0, 1, 0).

Зная соответствие переменных исходной и двойственной задач, из последней симплексной таблицы можно записать решение двойственной. Так как переменные двойственной задачи u₁ и u₃ соответствуют переменным исходной задачи х₃ и х₁, а в последней симплексной таблице эти переменные являются базисными, то u₁ и u₃ принимают значение равное нулю. Переменные u₂ и u₄ соответствуют х₄ и х₂, а в последней симплексной таблице эти переменные являются свободными, следовательно, u₂ принимает значение, равное оценке свободной переменной х₄, а u₄ - значение, равное оценке свободной переменной х₂ в целевой функции, т. е. u₂ = 1, а u₄ = 2. Таким образом, решение двойственной задачи будет следующим: W_min = 2 при U_opt(0, 1, 0, 2).

3.5 Транспортная задача

3.5.1 Общая постановка задачи

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

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

В общем виде задачу можно представить следующим образом: в т пунктах производства А₁, А₂, …, А_т имеется однородный груз в количестве соответственно a₁, а₂,…, а_т. Этот груз необходимо доставить в n пунктов назначения В₁, В₂, …, В _n в количестве соответственно b₁, b₂, ..., b_n. Стоимость перевозки единицы груза (тариф) из пункта А_i в пункт B_j равна С_ij.

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

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

Если = , то задача называется закрытой.

Если ? ,то задача называется открытой.

Обозначим через X_ij количество груза, перевозимого из пункта А_i в пункт В_j. Рассмотрим закрытую транспортную задачу.

Постановка задачи (на минимум стоимости перевозок груза).

Найти значения переменных Х_ij, где i = 1,…, m (m - число строк), а j = 1, …, n (n - число столбцов), обеспечивающих целевой функции Z = минимум и удовлетворяющих следующим ограничениям:

1. Сумма всех грузов, перевозимых от i-го поставщика, должна быть равна запасу груза у этого поставщика:

= a_i ,

где i = 1, …, m.

2. Сумма всех грузов, доставляемых j-му потребителю, должна равняться потребности этого потребителя:

= b_j,

где j = 1, …, n.

3. Условия неотрицательности.

Х_ij ? 0, где i = 1, …, m; j = 1, …, n.

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

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

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

· нахождение исходного опорного решения;

· проверка этого решения на оптимальность;

· переход от одного опорного решения к другому и доведение его до оптимального методом потенциалов.

Рассмотрим каждый из этих этапов.

3.5.2 Нахождение исходного опорного решения

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

Таблица 3.17 Распределительная таблица

Поставщики	Потребители	Запасы
	В1	. . .	Вj	. . .	Вn
A1	C11 x11		C1j x1j		C1n x1n	a1
. . .	. . .	…	…	…	…	…
Ai	Ci1 Xi1		Cij Xij		Cin Xin	ai
. . .	. . .	. . .	. . .	. . .	. . .	. . .
Am	Cm1 Xm1		Cmj xmj		Cmn xmn	am
Потребности	b1		bj		bn	? ai ? bj

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

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

Опорный план транспортной задачи может иметь (m + n - 1) отличных от нуля неизвестных. В этом случае план является невырожденным.

Если отличных от нуля неизвестных меньше, чем (m + n - 1), то такой план - вырожденный. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми.

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

Рассмотрим нахождение исходного опорного решения транспортной задачи на конкретном примере.

Пример 1. На складах А₁, А₂, А₃ имеются запасы продукции в количестве 200, 180, 220 т соответственно. Потребители В₁, В₂, В₃ должны получить эту продукцию в равном количестве - 200, 200, 200 т соответственно. Расходы по перевозке 1 т продукции заданы в табл. 3.18 (усл. ед.). Составить опорный план методом минимального элемента в таблице и методом «северо-западного угла» и определить стоимость перевозки по каждому плану.

Таблица 3.18 Исходная задача

8	7	6	200
4	10	8	180
2	3	9	220
200	200	200

Проверяем, является ли данная транспортная задача закрытой:

= 200 + 180 + 220 = 600,

= 200 + 200 + 200 = 600,

= , следовательно, данная транспортная задача закрытая.

Найдем исходное опорное решение по методу минимального тарифа (табл. 3.19-3.22).

Таблица 3.19 Первый опорный план (шаг 1)

8 Х	7	6	200
4 Х	10	8	180
2 200	3	9	220 20
200 0	200	200	600 600

Таблица 3.20 Первый опорный план (шаг 2)

8 Х	7	6	200
4 Х	10	8	180
2 200	3 20	9 Х	220 20 0
200	200	200	600 600
0	180

Таблица 3.21 Первый опорный план (шаг 3)

8 Х	7 Х	6 200	200 0
4 Х	10	8 Х	180
2 200	3 20	9 Х	220 20 0
200	200	200	600 600
0	180	0

Таблица 3.22 Первый опорный план (шаг 4)

8 Х	7 Х	6 200	200 0
4 Х	10 180	8 Х	180 0
2 200	3 20	9 Х	220 20 0
200	200	200	600 600
0	180 0	0

Стоимость перевозки при исходном опорном решении составляет:

Z = 200 · 6 + 180 · 10 + 200 · 2 + 20 · 3 = 3460.

Далее для исходной задачи (табл. 3.18) составляем опорный план методом «северо-западного угла» (диагональный метод) (табл. 3.23).

При этом методе на каждом шаге построения первого опорного плана заполняется верхняя левая клетка («северо-западный угол») оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки переменного х₁₁ и заканчивается в клетке неизвестного х_mn, т. е. идет как бы по диагонали таблицы перевозок.

Таблица 3.23 Второй опорный план

8 200	7 Х	6 Х	200
4 Х	10 180	8 Х	180
2 Х	3 20	9 200	220
200	200	200	600 600

Z = 200 · 8 + 180 · 10 + 200 · 9 + 20 · 3 = 5260.

Как видим, стоимость перевозки по первому опорному плану (табл. 3.22) значительно ниже, чем по второму (табл. 3.23). Это свидетельствует о том, что метод минимального тарифа эффективнее метода «северо-западного угла». Исходное опорное решение, построенное диагональным методом, как правило, оказывается весьма далеким от оптимального, так как при его определении совершенно игнорируются величины затрат С_ij. Поэтому требуется в дальнейших расчетах много итераций для достижения оптимального плана. Число итераций можно сократить, если исходный план строить по более рациональ-ному методу аппроксимации. Данный метод особенно удобен для задач малой размерности, так как в большинстве случаев приводит к оптимальному решению. Пример составления опорного плана методом аппроксимации можно найти в учебном пособии [4].

В распределительной таблице добавляются нулевой столбец (слева) и нулевая строка (сверху).

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

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

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

Для строки противоположным рядом будем считать столбец, а для столбца - строку.

Здесь возможны следующие моменты:

· условие выполнено для одной клетки. Тогда с нее начинаем заполнение таблицы;

· условие выполнено для нескольких клеток. Тогда заполняется та, которой в противоположном ряду соответствует большая разность. Если противоположные разности равны, то заполняем обе клетки;

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

Рассмотрим нахождение исходного опорного решения методом аппроксимации на конкретном примере (табл. 3.24).

Таблица 3.24 Исходная задача

8	7	6	9	200
4	10	8	3	180
2	3	6	5	220
5	4	8	9	100
100	150	200	250

Проверяем, является ли данная транспортная задача закрытой:

= 200 + 180 + 220 + 100 = 700;

= 100 + 150 + 200 + 250 = 700;

= , следовательно, данная транспортная задача закрытая.

Находим разность по строкам и по столбцам (табл. 3.25).

Таблица 3.25 Составление опорного плана методом аппроксимации (шаг 1)

	2	1	0	2
1	8 х	7	6	9	200
1	4 х	10 х	8 х	3 180	180 0
1	2 100	3	6	5	220 120
1	5 х	4	8	9	100
	100 0	150	200	250 70	700 700

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

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

Таблица 3.26 Составление опорного плана методом аппроксимации (шаг 2)

		1	0	4
1	8 х	7	6	9	200
	4 х	10 х	8 х	3 180
2	2 100	3	6	5	120
4	5 х	4 100	8 х	9 х	100 0
		150 50	200	70	700 700

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

Для четвертой строки: наименьшая стоимость равна 4, а наименьшая стоимость противоположного ряда (второй столбец) равна 3. Разность между ними равна 1.

Для четвертого столбца: наименьшая стоимость равна 5, а наименьшая стоимость третьей строки равна 3. Разность между ними равна 2. Наименьшее значение имеет первая разность, поэтому заполняем клетку, расположенную в четвертой строке и во втором столбце.

Из рассмотрения выходит четвертая строка.

Таблица 3.27 Составление опорного плана методом аппроксимации (шаг 3)

		4	0	4
1	8 х	7 х	6	9	200
	4 х	10 х	8 х	3 180
2	2 100	3 50	6	5	120 70
	5 х	4 100	8 х	9 х
		50 0	200	70	700 700

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

Таблица 3.28 Составление опорного плана методом аппроксимации (шаг 4)

			0	4
3	8 х	7 х	6 200	9 х	200 0
	4 х	10 х	8 х	3 180
1	2 100	3 50	6 х	5 70	70 0
	5 х	4 100	8 х	9 х
			200 0	70 0	700 700

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

Таблица 3.29 Опорный план

8	7	6 200	9
4	10	8	3 180
2 100	3 50	6	5 70
5	4 100	8	9

3.5.3 Нахождение оптимального плана методом потенциалов

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

V_j - потенциалы столбцов;

U_i - потенциалы строк,

С_ij - стоимость перевозки единицы груза от каждого поставщика каждому потребителю;

Х_ij - количество груза, которое будет перевезено от i-го поставщика к j-му потребителю, где i = 1, …, m (m - число строк), а j = 1, …, n (n - число столбцов).

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

Для заполненных клеток (Х_ij 0):

V_j - U_i = С_ij.

Для пустых клеток (Х_ij = 0):

V_j - U_i С_ij,

для всех i = 1, …, m и j = 1, …, n.

Опорный план, представленный в табл. 3.29, прежде всего, проверим на вырожденность:

· число заполненных клеток в опорном плане (табл. 3.29) равно 6;

· m + n - 1 = 4 + 4 - 1 = 7.

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

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

V1 - U3 = 2,	V1 = 0 + 2,	V1 = 2,
V2 - U3 = 3,	V2 = 0 +3,	V2 = 3,
V3 - U3 = 6,	V3 = 0 + 6,	V3 = 6,
V4 - U3 = 5,	V4 = 0 + 5,	V4 = 5,
V3 - U1= 6,	6 - U1 = 6,	U1 = 0,
V4 - U2 = 3,	5 - U2 = 3,	U2 = 2,
V2 - U4 = 4,	3 - U4 = 4,	U4 = -1.

Заполняем потенциалы строк и столбцов (табл. 3.30)

Таблица 3.30 Оптимальный план

	V1 = 2	V2 = 3	V3 = 6	V4 =5
U1 = 0	8	7	6 200	9
U2 = 2	4	10	8	3 180
U3 = 0	2 100	3 50	6 0	5 70
U4 = -1	5	4 100	8	9

Проверяем второе условие оптимальности (для пустых клеток):

Д11 = V1 - U1 = 2 - 0 = 2 8, Д12 = V2 - U1 = 3 - 0 = 3 7, Д14 = V4 - U1 = 5 - 0 = 5 9, Д21 = V1 - U2 = 2 - 2 = 0 4, Д22 = V2 - U2 = 3 - 2 = 1 10,	Д23 = V3 - U2 = 6 - 2 = 4 8, Д41 = V1 - U4 = 2 - (-1) = 3 5, Д43 = V3 - U4 = 6 - (-1) = 7 8, Д44 = V4 - U4 = 5 - (-1) = 6 9.

Второе условие выполнено для всех пустых клеток, следовательно, в табл. 3.30 получено оптимальное решение. Запишем его:

_min = 200 · 6 + 180 · 3 + 100 · 2 + 50 · 3 + 0 · 6 + 70 · 5 + 100 · 4 = 2840.

Рассмотрим еще один пример. Задан некоторый опорный план (табл. 3.31).

Таблица 3.31 Первый опорный план

3	5 120	7 10	11
1 30	4	6 70	2
5 120	9	12	7 50

Число заполненных клеток в опорном плане (табл. 3.31) равно 6. По формуле считаем число отличных от нуля неизвестных:

m + n - 1 = 4 + 3 - 1 = 6. Следовательно, план (табл. 3.31) является невырожденным.

Используя первое условие оптимальности, находим потенциалы строк и столбцов, придавая нулевое значение потенциалу первой строки (U₁ = 0).

V2 - U1 = 5,	V2 = 0 + 5,	V2 = 5,
V3 - U1 = 7,	V3 = 0 + 7,	V3 = 7,
V3 - U2 = 6,	7 - U2 = 6,	U2 = 1,
V1 - U2 = 1,	V1 - 1 = 1,	V1 = 2,
V1 - U3 = 5,	2 - U3 = 5,	U3 = -3,
V4 - U3 = 7,	V4 - (-3) = 1,	V4 = 4.

Полученные значения потенциалов строк и столбцов записываем соответственно слева от таблицы и сверху (табл. 3.32).

Таблица 3.32 Второй опорный план

	V1 = 2	V2 = 5	V3 = 7	V4 = 4
U1 = 0	3	5 120	7 10	11
U2 = 1	1 30	4	6 70	2
U3 = -3	5 120	9	12	7 50

Проверяем второе условие оптимальности (для пустых клеток).

Д11 = V1 - U1 = 2 - 0 = 2 3, Д14 = V4 - U1 = 4 - 0 = 4 11, Д22 = V2 - U2 = 5 - 1 = 4 = 4,	Д24 = V4 - U2 = 4 - 1 = 3 2, Д32 = V2 - U3 = 5 - (-3) = 8 9, Д33 = V3 - U3 = 7 - (-3) = 10 12.

Для всех пустых клеток, где нарушено второе условие оптимальности, находим характеристику по формуле (3.2):

_ij= v_j - u_i - c_ij. (3.2)

Из характеристик выбираем наибольшую (в данном случае единственная: ₂₄ = 4 - 1 - 2 = 1) и начиная с клетки с данной характеристикой строим цепь (цикл) - ломаную линию, вершины которой расположены в занятых клетках таблицы, кроме первой. Повороты цепи делают под прямым углом. В строке или столбце, где проходит цепь, содержатся только две клетки цепи. Цепь должна быть замкнута. Клетки цепи отмечаем чередующимися знаками (+) и (-), начиная со знака (+) в первой клетке цепи (табл. 3.33).

Таблица 3.33 Третий опорный план

	V1 = 2	V2 = 5	V3 = 7	V4 = 4
U1 = 0	3	5 120	7 10	11
U2 = 1	- 1 30	4	6 70	+ 2
U3 = -3	5 120 +	9	12	7 50 -

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

Q = min(30, 50) = 30.

Пересчитанные грузы записать в табл. 3.34 и пересчитать потенциалы.

Потенциалы исправить, начиная с потенциала столбца той клетки, с которой начиналась цепь в предыдущей таблице, т. е. V₄ = 4 - 1 = 3. Уменьшить его на величину характеристики этой клетки ₂₄ = 1. В столбце, где исправлен потенциал, есть еще заполненные клетки в третьей строке, следовательно, исправить потенциал третьей строки (U₃ = -3 - 1 = -4). Затем «пройти» по этой строке и для заполненных клеток исправить потенциал столбцов (V₁ = 2 - 1 = 1).

Таблица 3.34 Оптимальный план

	V1 = 1	V2 = 5	V3 = 7	V4 = 4 3
U1 = 0	3	5 120	7 10	11
U2 = 1	1	4	6 70	2 30
U3 = -3 - 4	5 150	9	12	7 20

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

· для заполненных клеток первое условие верно;

· для пустых клеток:

Д11 = V1 - U1 = 1- 0 = 1 3, Д14 = V4 - U1 = 3 - 0 = 3 11, Д21 = V1 - U2 = 1 - 1 = 0 4,	Д22 = V2 - U2 = 5 - 1 = 4 = 4, Д32 = V2 - U3 = 5 -(-4) = 9 = 9, Д33 = V3 - U3 = 7 - (-4) = 11 12.

Все условия выполняются. Следовательно, в табл. 3.34 получено оптимальное решение:

Z_min = 120 · 5 + 10 · 7 + 70 · 6 + 30 · 2 + 150 · 5 + 20 · 7 = 2040.

Контрольные вопросы

1. Что понимают под методами линейного программирования?

2. Какие разделы включает линейное программирование?

3. Что называют оптимальным вариантом плана?

4. Какие методы линейного программирования вы знаете?

5. Опишите общую схему расчетов симплексным методом.

6. Сформулируйте ключевую теорему симплексного метода.

7. Какие переменные задачи являются базисными, а какие - свободными?

8. Когда задача имеет альтернативное решение?

9. Какое решение задачи называется вырожденным?

10. Когда задача линейного программирования не имеет решения и по какой причине?

11. При решении каких задач применяется метод искусственного базиса?

12. Назовите теорему, устанавливающую связь между оптимальными решениями М- и Z-задач.

13. Сформулируйте основную теорему двойственности.

14. В чем заключается правило построения двойственной задачи?

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

16. Какая модель транспортной задачи является открытой, а какая закрытой?

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

18. Когда опорный план транспортной задачи является оптимальным?

Глава 4. Моделирование экономических систем и процессов при решении задач методами линейного программирования

4.1 Понятие модели и моделирования. Требования к модели

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

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