4.4. Варианты заданий

Найти решение следующих задач линейного целочисленного программирования.

1)	F=3x1-2x2→max		2)	F=x1+2x2→max
3)	F=7x1-2x2→max		4)	F=2x1 -x2→max
5)	F=7x1-2x2→max		6)	F=x1-x2→max
7)	F=7x1 + x2→max		8)	F=7x1 - x2→min
9)	F=x1+3x2→max		10)	F=-3x1+6x2→min
11)	F=x1+x2→max		12)	F=-2x1+x2→min
13)	F=2x1-x2→max		14)	F=3x1+x2→min
15)	F=3x1+3x2→min		16)	F=8x1+2x2→max
17)	F=x1+2x2→max		18)	F=2x1+3x2→min
19)	F=6x1+4x2→min		20)	F=-2x1-x2→min
21)	F=7x1-2x2→max		22)	F=x1+2x2→max
23)	F=-2x1+x2→min		24)	F=x1-2x2→max
25)	F=8x1+2x2→max		26)	F=7x1-2x2→max
27)	F=6x1+4x2→min		28)	F=x1+x2→max
29)	F=x1+x2→max		30)	F=x1-3x2→min

Тема 5. Транспортная задача

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

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

Приведем простейшую формулировку транспортной задачи. Пусть имеется тпунктов производства однородного продукта с объемами производстваa_i (i=1, 2,…, m)иппунктов потребления с объемами потребленияb_j (j=1, 2 ,..., n), причем предполагается, что

(5.1)

Пусть х_ij -количество груза перевозимого изi-го пункта производства вj-и пункт потребления, ис_ij -стоимость транспортировки одного изделия (единицы груза) из пункта производстваi в пункт потребленияj.

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

(5.2)

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

(5.3)

х_ij0; i=1, 2 ,..., n, j=1, 2 ,..., n (5.4)

Условия (5.3), (5.4) образуют систему ограничений: первая группа ограничений (5.3) указывает, что суммарный объем перевозок из некоторого исходного пункта равен произведенному количеству этой продукции. Вторая группа ограничений (5.3) требует, чтобы суммарные перевозки продукции в некоторый пункт потребления полностью удовлетворили спрос на эту продукцию. Условия баланса (5.1) означают, что суммарный объем производства равен суммарному спросу. В реальных задачах это выполняется не всегда. Однако транспортную задачу всегда можно сбалансировать, введя фиктивный пункт-производитель или фиктивный пункт потребления (склад).

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

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

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

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

Шаг 1. Найти начальное допустимое решение.

Шаг 2. Выделить из числа небазисных переменных вводимую в базис. Если все небазисные переменные удовлетворяют условию оптимальности (С_pq0), закончить вычисления; в противном случае перейти к шагу 3.

Шаг 3. Выбрать выводимую из базиса переменную (используя условие допустимости) из числа переменных текущего базиса; затем найти новое базисное решение. Вернуться к шагу 2.

Рассмотрим алгоритм подробнее. Для пояснения воспользуемся задачей, приведенной в таблице 2.1.

Таблица 2.1.

Поставщик	Потребитель				Запасы
	1	2	3	4
1	10 x11	0 x12	20 x13	11 x11	15
2	12 x21	7 x22	9 x23	2 x24	25
3	0 x31	14 x32	16 x33	18 x34	5
Спрос	5	15	15	10

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

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

x₁₁=тin(а_i,b_i),

после этого «закрывают» соответствующий столбец или строку. Если а₁>b₁, то «закрывается» первый столбец, т.е. все остальные элементы этого столбца полагаются равными нулю:х_i1=0, i=1, 2 ,..., m, еслиа₁<b₁, то закрывается первая строках_1j=0, j=1, 2 ,..., n;. Еслиa₁=b₁, то сами выбираем, что закрывать - строку или столбец. После того как спрос и объем производства во всех незакрытых строках и столбцах приведены в соответствие с установленным значением переменной, переходим к заполнению следующей клетки таблицы(х₁₂илих₂₁).Этот процесс продолжается до тех пор, пока не исчерпан груз у производителей или не удовлетворен спрос потребителей. Последняя заполненная клеткат, покажется лежащей в последнемn-м столбце и в последнейm-й строке.

Применим описанную процедуру к примеру, задаваемому таблицей 2.1.

1. х₁₁=5, столбец 1 закрывается, т.е. все остальные элементы первого столбца полагаются равными нулю и в первом столбце больше нельзя производить никаких операций. На первую строку теперь приходится 10 единиц.

2. х₁₂=10,строка 1 закрывается, а на долю столбца 2 остается 5 единиц.

3. х₂₂=5,столбец 2 закрывается, а в строке 2 остается 20 единиц.

4. х₂₃=15,столбец 3 закрывается, а в строке 2 остается 5 единиц.

5. х₂₄=5,строка 2 закрывается, а в столбце 4 остается 5 единиц.

6. х₃₄=5,закрывается строка 3 или столбец 4. Поскольку остается только один столбец или одна строка, процесс заканчивается. Полученное базисное решение приведено в таблице 2.2.

Базисные переменные принимают значения:

х₁₁=5, х₁₂=10, х₂₂=5, х₂₃=15, х₂₄=5, х₃₄=5.

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

	1	2	3	4
1	10 5	0 10	20	11	15
2	12	7 5	9 15	20 5	25
3	0	14	16	18 5	5
	5	15	15	10

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

В методе потенциалов строки iи столбцуjтранспортной таблицы ставятся в соответствие числаU_i,иV_j,. Для каждой базисной переменной текущего решения потенциалыU_i,иV_jдолжны удовлетворять уравнению:

U_i,+V_j= С_ij(5.5)

Так как базисных переменных т + п - 1, то мы получим систему изm + п -1уравнений вида (5.5) относительнот + пнеизвестных. Значения потенциалов можно найти из этой системы, придав одному из них произвольное значение (обычноU₁полагается равным нулю), и затем, решая систему относительноm+n-1, остальных потенциалов. Как только решение получено, оценки для небазисных переменных определяются следующим образом:

(5.6)

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

Применим описанную процедуру к таблице 5.2. Уравнения (5.5) для базисных переменных будут иметь вид:

х₁₂:

х₂₂:

х₂₃:

х₂₄:

х₃₄:

Полагая u₁=0,получим значения потенциаловv₁=10, v₂=0, u₂=7, v₃=2, v₄=13, u₃=5

Оценки для небазисных переменных (5.6) определяются следующим образом:

х₁₃:

х₁₄:

х₂₁:

х₃₁:

х₃₂:

х₃₃:

Поскольку переменная x₃₁ имеет максимальную положительную оценку, то она вводится в базис.

Следующий шаг алгоритма - нахождение переменной, выводимой из базиса. Для этого построим замкнутый цикл, соответствующий вводимой переменной (на данном шаге в нашем примере это). Цикл начинается и заканчивается выбранной небазисной переменной. Он состоит из связной последовательности горизонтальных и вертикальных отрезков, концами которых должны быть базисные переменные (за исключением тех концов, которые относятся к вводимой в базис переменной), т.е. каждая ячейка, стоящая на изломе цикла, должна содержать базисную переменную. В таблице 5.3 показан цикл соответствующий вводимой переменной, для базисного решения из таблицы 5.2. Этот цикл можно выразить при помощи базисных переменных следующим образом:

х₃₁х₁₁х₁₂х₂₂х₂₄х₃₄х₃

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

Из таблицы 5.3 видно, что если значение вводимой в базис переменнойх₁₃ увеличено на единицу, то для сохранения допустимости решения значения базисных переменных, стоящих на изломах цикла, необходимо спроектировать следующим образом: уменьшитьх₁₁на единицу, увеличитьх₁₂на единицу, уменьшитьх₂₂на единицу, увеличитьх₂₄на единицу и уменьшитьх₃₄на единицу. Этот процесс обозначен знакамии в соответствующих ячейках таблицы 5.3. Введенные изменения не нарушают ограничений, накладываемых на объем производства и спрос.

Таблица 5.3

	1		2		3		4
1		10		0		20		11
	5		10
2		12		7		9		20
			5		15		5
3		0		14		16		18
	Х31						5

Переменная, выводимая из базиса, выбирается из тех, находящихся на изломах цикла, переменных, значения которых уменьшаются при увеличениих₃₁. Они располагаются в таблице 5.3 в ячейках, отмеченных знаком . Для таблицы 5.3 это переменные х₁₁, х₂₂, х₃₄..Выводимой из базиса переменной становится та, которая имеет наименьшее значение, поскольку именно она раньше всех достигнет нуля. В рассматриваемом примере все три

-переменныех₁₁, х₂₂, х₃₄ имеют одно и тоже значение (V = 5). В этом случае любую из них можно исключить из базиса. Пусть выбрана перемеднаях₃₄.Тогда значениех₃₁становится равным 5, а переменные, находящиеся на изломах цикла (базисные), соответствующим образом корректируются, т.е. каждая из них увеличивается или уменьшается на 5 единиц в зависимости от знакаили . Новое решение приведено в таблице 5.4. Соответствующая стоимость перевозок

f= 0^.10+15 ^. 0+0 ^.7+15 ^. 9+10 ^.20+5 ^.0=335

Полученная стоимость отличается от стоимости, соответствующей начальному решению на 410 - 355 = 75, т.е. на величину, приписанную переменнойх₃₁=5и умноженную на.

Таблица 5.4.

	1		2		3		4
1		10		0		20		11
	0		15						15
2		12		7		9		20
			0		15		10		25
3		0		14		16		18
	5								5
	δ^5		15		15		10

Базисное решение в таблице 5.4 вырожденное, поскольку базисные переменные х₁₁их₂₂равны нулю. Однако вырожденность не требует никаких дополнительных мер предосторожности. С нулевыми базисными переменными оперируют точно так же, как с переменными имеющими положительные значения.

Оптимальность нового базисного решения (таблица 5.4) проверяется вычислением новых потенциалов (таблица 5.5). Величины С_pqуказываются в юго-западном углу небазисного элемента.

Таблица 5.5

	V1=10			V2=0			V3=2			V4=13
U1=0			10			0			20			11
		0			15								15
							-18			+2
U2=7			12						9			20
		X21			0			15			10		25
	+5
U1=0			0			14			16			18
		5											5
				-24			-24			-15
	5			15			15			10

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

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

Таблица 5.6

	V1=5			V2=0			V3=2			V4=13
U1=0			10			0			20			11
					5						10		15
	-5						-18
U2=7			12			7			9			20
		0			10			15					25
										-2
U3=-5			0			14			16			18
		5											5
				-19			-19			-12

Значения u_i,v_i,вычисляются заново. В таблице 5.6 в базис вводится переменнаях₁₄, а исключается из базиса переменнаяx₂₄..

Пересчитав заново потенциалы, получим новое решение, приведенное в таблице 5.7.

Таблицa 5.7.

	V1=5			V2=0			V3=2			V4=11
U1=0			10			0			20			11
					15						10		15
	-5						-18			+2
U2=7			12			7			9			20
					0			15			10		25
U3=-5			0			14			16			18
													5
				-19			-19			-10
	5			15			15			10

Так как все в таблице 5.7неположительные,то полученное решение оптимальное. Оптимальное решение формулируется следующим образом. Перевезти 5 единиц из пункта производства 1 в пункт потребления 2, заплатив 5^.0=0 руб., 10 единиц из 1 в 4 за 10^.11=110 руб., 10 единиц из 2 в 2 за 10^.7=70 руб., 15 единиц из 2 пункта производства в 3 пункт потребления, заплатив 15^.9=135 руб. и 5 единиц из 3 в 1 за 5^.0=0 руб. Суммарные транспортные расходы составляют 315 руб.