Задачи для самостоятельного решения

х

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

1)			2)
3)			4)
5)			6)
7)			8)
9)			10)
11)			12)
13)			14)
15)			16)
17)			18)
19)			20)
21)			22)
23)			24)

IV Основные свойства злп

Рассмотрим каноническую ЗЛП (1.4) в векторной форме (1.6).

• План Х=(х₁, х₂, …х₃)называется опорным планом ЗЛП, если система векторов ,входящих в разложение с неотрицательными коэффициентамиx_j, линейно независима, т.к. векторы являютсяm-мерными, то число положительных компонент не может быть больше, чемm.

• Опорный план называется невырожденным, если он содержит ровноmположительных компонент, в противном случае он называетсявырожденным.

• Отрезком в n-мерном пространстве евклидовом пространствеRⁿ, соединяющем точкиХ⁽¹⁾ иХ⁽²⁾называется множество точек, удовлетворяющих равенствуХ=Х⁽¹⁾ + Х⁽²⁾, где, 0, +=1.

• Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и все точки отрезка, соединяющего эти точки.

• Точка Хвыпуклого множества называется угловой, если она не может быть представлена в видеХ=Х⁽¹⁾ + Х⁽²⁾,гдеХ⁽¹⁾ иХ⁽²⁾принадлежат данному множеству.

Теорема 1. Множество планов ЗЛП является выпуклым, если оно не пусто.

• непустое множество планов ЗЛП называется многогранником решений,а всякая угловая точка многогранника решений –вершиной.

Теорема 2.Если ЗЛП имеет оптимальный план, то максимальное значение целевая функция задачи принимает в одной из вершин многогранника решений. Если максимальное значение целевая функция принимает его во всякой точке отрезка, соединяющего эти вершины.

Теорема 3.Если система векторов(kn) в разложениилинейно независима и такова, что

,

где все x_j, то точкаХ=(х₁, х₂, …, x_k, 0, …,0)является вершиной многогранника решений.

Теорема 4.ЕслиХ=(х₁, х₂, …, x_n ) – вершина многогранника решений, то векторы , соответствующие положительнымx_jлинейно независимы.

V Симплекс-метод решения злп

Рассмотрим стандартную ЗЛП

Вводя дополнительные переменные х_n+1, х_n+2, …, x_n+m приводим задачу к каноническому виду:

(1.9)

Симлекс-метод основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает. Система (1.9) содержит mуравнений и n+mнеизвестных. Выбранныеmнеизвестных называютсябазисными, а остальные – свободными (равными нулю). Систему (1.9) запишем в векторной форме:

(1.11)

где

; …;;…,

В качестве опорного выбирается план Х=(0, …, 0, b₁, b₂, …, b_m), определяемый системой единичных векторов, которые образуют базисm-мерного пространства.

Переход от одного опорного плана к другому осуществляется с помощью оценки вектора.

Оценкой вектора называется величина

(1.12)

где c_i– коэффициенты целевой функции при базисных переменных.

Теорема 5. (о возможности улучшения опорного плана).

Если для данного опорного плана (решения), есть такая отрицательная оценка _S, что среди координат вектора в данном базисе (то есть среди чисела_ks k=1, 2, …, m) есть положительные, то базис, которому соответствует лучшее опорное решение, получим, заменив вектором тот векторисходного базиса, для которогоа_rs>0,причем для всех а_is>0, (ir) .

Теорема 6. (критерий оптимальности опорного решения).

Если для данного опорного решения все оценки неотрицательны, то это решение оптимально.

Теорема 7.(признак неограниченности целевой функции).

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

Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести, составив симплексную таблицу 1.1.

Таблица 1.1

i

Базис

Сб

Ао

С1

С2

…

Сr

…

Сn

Cn+1

…

Се

…

C n+m

А1

А2

…

Аr

…

Аn

Аn+1

…

Ае

…

А n+m

1

Аn+1

Cn+1

b1

a11

a12

…

a1r

…

a1n

1

…

0

…

0

2

Аn+2

Cn+2

b2

a21

a22

…

a2r

…

a1n

0

…

0

…

0

r

Аn+r

Cn+r

br

ar1

ar2

…

arr

…

arn

0

…

1

…

0

m

Аn+m

Cn+m

bm

am1

am2

…

amr

…

amn

0

…

0

…

1

m+1

F0

∆1

∆2

∆r

∆n

∆n+1

…

∆e

…

∆n+m

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

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

Первые mстрок определяются исходными данными задачи, а показатели(т+1)-й строки вычисляют.

f₀ -значение целевой функции, которое она принимает при данном опорном плане.

(1.13)

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

1. Если все неотрицательные, то и найденный опорный план оптимален.

2. <0для некоторогоj,и все соответствующие этому индексу

величины a_ij (i=).В этом случае целевая функция не ограничена сверху на множестве планов, поэтому задача неразрешима.

3. <0для некоторых индексов j, и для каждого такого по крайней мере одно из чисела_ijположительно. В этом случае можно перейти от исходного плана к опорному плану, при котором значение целевой функции увеличивается.

Переход от одного опорного плана к другому осуществляется выводом из исходного базиса какого-нибудь из векторов и введением в него нового вектора. В качестве вектора, вводимого в базис, можно взять любой из векторов А_j, для которого <0.

Для определенности выбираем Р_jс наибольшим по абсолютной величине отрицательным числом. Пусть это будет приj=s. Тогда в базис вводится вектор.

Для определения вектора подлежащего исключению из базиса, находят min(b_i/a_is)для всехa_is >0.Пусть этот минимум достигается приi=r.Тогда из базиса исключают векторA_n+г числоа_rsназываютразрешающим элементом.

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

b'_i =(1.14)

и коэффициенты a'_ij = (1.15)

После этого составляют новую симплексную таблицу и вычисляют элементы (m+1)-й строкиF'₀и Δj´ по формулам (1.13), в которых все элементы берутся из новой таблицы. Полученный новый опорный план проверяется на оптимальность по знакамΔj. Процесс составления новых планов продолжается до получения оптимального плана или до выяснения неразрешимости задачи.

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

Таблица 1.2.

Вид сырья	Нормы затрат сырья, кг			Общее кол-во сырья, кг
	А	В	С
I	18	15	12	360
II	6	4	8	192
III	5	3	3	180
Цена одного изд.	9	10	16

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

Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной.

Решение.Обозначим искомый выпуск изделий А черезх₁,изделий В черезх₂,изделий С черезх₃.

Переменные х₁, х₂, х₃должны удовлетворять следующей системе неравенств (ввиду ограничений на выделяемый фонд сырья):

(1.16)

Общая стоимость произведенной предприятием продукции:

F=9x₁ +10x₂+16x₃(1.17)

По своему экономическому содержанию переменные х₁, х₂, х₃могут принимать только лишь неотрицательные значения:

(1.18)

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

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

18х₁ +15x₂+12х₃ + x₄ = 360,

6х₁+ 4х₂+8x₃ +x₅ = 192,

5x₁+3х₂+3х_з + x₆= 180.

Преобразованную систему уравнений запишем в векторной форме:

x₁A₁+x₂A₂ + x₃A₃ + x₄A₄ + x₅A₅ + x₆A₆ =A₀,

где

Трехмерные единичные векторы A_4, A₅, A₆образуют базис трехмерного векторного пространства.

Опорным является план X = (0; 0; 360; 192; 180).

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

Таблица 1.3

i	базис	Сб	A0	9	10	16	0	0	0
				A1	A2	A3	A4	A5	A6
1	A4	0	360	18	15	12	1	0	0
2	A5	0	192	6	4	8 8 8	0	1	0
3	A6	0	180	5	3	3	0	0	1
4				-9	10	-16	0	0	0

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

Как видно из таблицы 1.3, значения всех основных переменных х₁, х₂, х₃ равны нулю, а дополнительные переменные принимают свои значения в соответствии с ограничениями задачи. Эти значения переменных отвечают такому "плану", при котором ничего не производится и значение целевой функции равно нулю.

Так как максимальное по абсолютной величине число Δjстоит в 4-й строке столбца вектора, то в новый базис введем вектор. С экономической точки зрения мы включаем в план производства изделия С.

Определим вектор, подлежащий исключению из базиса. Для этого находим

min () для a_i3> 0, т.е.

min () == 24

т.е. ограничивающим фактором для производства изделий С является имеющийся объем сырья 2-го вида (табл. 1.4). С учетом его наличия предприятие может изготовить 24 изделия С. Следовательно, вектор , подлежит исключению из базиса. Элемент 8, стоящий на пересечении 2-й строки и столбца вектора является разрешающим. Таким образом, r = 2, S = 3.

Таблица 1.4.

i	базис	Сб	Р0	9	10	16	0	0	0
				Р1	Р2	Р3	Р4	Р5	Р6
1	Р4	0	72	9	9	0	1	-3/2	0
2	Р3	16	24	3/4	1/2	1	0	1/8	0
3	Р6	0	108	11/4	3/2	0	0	-3/8	1
4			384	3	-2	0	0	2	0

Сначала заполняем строку вектора, вновь введенного в базис, т.е. строку, номер которой совпадает с номером направляющей (2-й) строки. Элементы этой строки получаются из соответствующих элементов предыдущей таблицы делением их на разрешающий элемент. При этом в столбце C_бзаписываем коэффициентС_з =16, стоящий в столбце вводимого в базис вектора_. Затем заполняем элементы столбцов для векторов, входящих в новый базис. В этих столбцах на пересечении строк и столбцов одноименных векторов проставляем единицы, а все остальные элементы полагаем равными нулю.

Остальные элементы таблицы 1.4 вычисляют по формулам (1.14), (1.15).

По окончании всех расчетов элементов таблицы 1.4 в ней получен новый опорный план: X=(0; 0; 24; 72; 0; 108), который тоже не является оптимальным, поскольку в столбце вектораэтой строки стоит отрицательное число -2. Значит, в базис следует ввести векторA₂,т.е. в новом плане предусмотреть выпуск изделий В.

Для нахождения вектора подлежащего исключению, определяем

min () дляa'_ir> 0, т.е.

min == 8

Следовательно, исключению из базиса подлежит вектор . Столбец вектора и 1-я строка являются направляющими, а число 9 - разрешающий элемент. Отсюда следует, чтоr = 1, S=2.

Составляем таблицу для III итерации (таблица 1.5).

Таблица 1.5

i	базис	Сб	A0	9	10	16	0	0	0
				A1	A2	A3	A4	A5	A6
1		10	8	1	1	0	1/9	-1/6	0
2		16	20	1/4	0	1	-1/18	5/24	0
3		0	96	5/4	0	0	-1/6	-1/8	1
4			400	5	0	0	2/9	5/3	0

В таблице 1.5 сначала заполняем элементы 1-й строки, которая представляет собой строку вновь вводимого в базис вектора Р₂. Элементы этой строки получаем из элементов 1-й строки таблицы 1.4 делением последних на разрешающий элемент (т.е. на 9). При этом в столбцеС_бданной строки записываемС₂=10.

Затем заполняем элементы столбцов вектора базиса и по формулам (1.14), (1.15) вычисляем элементы остальных столбцов. В результате получаем новый план X = (0; 8; 20; 0; 0; 96) и соответствующие значенияΔ"jиF₀" .Среди чиселΔ"j нет отрицательных. Это означает, что найденный опорный план является оптимальным иF_max =400.

Следовательно оптимальный план включает в себя изготовление 8 изделий В, 20 изделий С и не предусматривает изготовление изделий вида А. При данном плане полностью используется сырье 1 и 2-го видов и остается неиспользованным 96 кг. сырья 3-го вида. Стоимость произведенной продукции равна 400 руб.

Симплекс–метод решения ЗЛП (алгоритм)