F = 2x₁ - 3x₂ + 1 > min

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

х₁ + х₂ ? 4,

2х₁ - х₂ ? 1,

х₁ - 2х₂ ? 1,

х₁ ? 0, х₂ ? 0.

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

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: х₁, х₂, х₅,

неосновные: х₃, х₄.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

х₁ = ,

х₂ = ,

х₅ = 4 + х₃ - х₄.

Положив неосновные переменные равными нулю, получим новое базисное решение: Х = (5/3; 7/3; 0; 0; 4), которое является допустимым.

Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении:

F = 2x₁ - 3x₂ + 1 = 2 () - 3 () + 1 = .

F = F(X) = - 1/3.

Шаг 3. Проверка оптимальности решения.

Т.к. в выражении для F присутствуют отрицательные коэффициенты при неосновных переменных, то данное решение не оптимальное, т.е. F не минимальное.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

Отрицательный коэффициент в F перед х₃, т.е. х₃ вводим в новый состав основных переменных. Определим допустимое значение х₃.

х₁ = ? 0, х₄=0 х₁ = ? 0 х₃ ? ?

х₂ = ? 0, х₂ = ? 0 х₃ ? ?

х₅ = 4 + х₃ - х₄ ? 0 х₅ = 4 + х₃ ? 0 х₃ ? ?

2. Определим выводимую переменную.

х₃ = min {?; ?; ?} = ?.

Уравнения не ограничивают рост переменной х₃, поэтому и значение функции F неограниченно и отрицательно, т.е. F_min = - ?.

Вывод. Если на каком-либо шаге получаем, что во всех уравнениях системы бесконечные оценочные отношения той переменной, которая переводится в основные, то задача не имеет конечного оптимума (F_max = ?, если задача на отыскание максимума, и F_min = - ?, если задача на отыскание минимума).

1.7 Алгоритм табличного симплекс-метода

Пусть система приведена к каноническому виду.

f = c₁x₁ + c₂x₂ + … + c_nx_n > max

x₁ + a_1m+1x_m+1 + … + a_1nx_n = b₁,

x₂ + a_2m+1x_m+1 + … + a_2nx_n = b₂,

…

x_m + a_mm+1x_m+1 + … + a_mnx_n = b_m.

x_j ? 0, j =

Запишем расширенную систему.

x₁ + a_1m+1x_m+1 + … + a_1nx_n = b₁,

x₂ + a_2m+1x_m+1 + … + a_2nx_n = b₂,

…

x_m + a_mm+1x_m+1 + … + a_mnx_n = b_m,

f - c₁x₁ - c₂x₂ - … - c_nx_n = 0.

Шаг 1. Получение начального решения.

Выбираются m переменных, называемых базисными и обладающих следующим свойством: они входят с коэффициентом 1 только в одно уравнение и коэффициентом 0 в остальные уравнения системы.

Остальные n - m переменных называют свободными. Все свободные переменные полагаются равными 0, а базисные переменные - равные правым частям соответствующих ограничений системы.

Пусть m базисных переменных - это переменные x₁, x₂, …, x_m. Тогда начальное решение имеет X₀ имеет следующий вид:

X₀ = {x₁=b₁, x₂=b₂, …, x_m=b_m, x_m+1=0, …, x_n=0}

Если все b_i ? 0, , то начальное решение является допустимым. Переход к шагу 2. В противном случае используют алгоритмы нахождения начального решения (Алгоритмы нахождения начального решения будут описаны в подпунктах 1.8.1. и 1.8.2.).

Шаг 2. Выражение функции f только через свободные переменные.

f = .

Переход к шагу 3.

Шаг 3. Проверка решения на оптимальность.

Составляется симплекс-таблица.

Основные (базисные) переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	X1	X2	…	Xm	…	Xp	…	Xn
X1	a11	a12	…	a1m	…	a1p	…	a1n	b1
X2	a21	a22	…	a2m	…	a2p	…	a2n	b2
…	…	…	…	…	…	…	…	…	…	…
Xq	aq1	aq2	…	aqm	…	aqp	…	aqn	bq
…	…	…	…	…	…	…	…	…	…	…
Xm	am1	am2	…	amm	…	amp	…	amn	bm
F	-c1	-c2	…	-cm	…	-cp	…	-cn	0

В левой колонке симплекс-таблицы находятся базисные переменные, в колонке свободных членов - правые части соответствующих ограничений. В i-ой строке, j-м столбце стоит коэффициент при j-ой переменной в i-ом ограничении, i = 1,…, m, j = 1,…, n. В последней строке (f-строке) стоит коэффициент при j-ой переменной в целевой функции из расширенной системы. В предпоследнем столбце стоит значение свободного члена, входящего в целевую функцию.

Для проверки решения на оптимальность просматривается последняя f-строка:

· если коэффициенты, стоящие при свободных переменных неотрицательны, то полученное решение оптимально;

· полученное решение единственно, если все эти коэффициенты положительны;

· если среди неотрицательных коэффициентов встречается хотя бы один нулевой, то задача имеет бесконечное множество решений;

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

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

Переход к шагу 4.

Шаг 4. Получение нового решения.

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

2. Выбор переменной, выводимой из списка базисных переменных. Находят отношение элементов столбца свободных членов к элементам разрешающего столбца. При делении на противоположный по знаку элемент и на 0 результат полагают равным +?. Эти значения записываются в последний столбец симплекс-таблицы. Среди этих отношений находят минимальное. Строка, соответствующая минимальному отношению, называется разрешающей. Пусть, например, это q-я строка. Базисная переменная x_q, стоящая в этой строке, выводится из списка базисных переменных. Элемент симплекс-таблицы a_qp, стоящий на пересечении разрешающего столбца, называется разрешающим элементом.

3. Выполнение симплекс-преобразования и переход к новой симплекс-таблице. Элемент a_ij новой симплекс-таблицы вычисляется с помощью следующего симплекс-преобразования (в алгебре это преобразование известно как прямой ход метода Гаусса для решения систем линейных алгебраических уравнений):

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

.

Новое решение имеет следующий вид: все свободные переменные в нем полагаются равными 0, а все базисные переменные - свободным членам, стоящим в одной строке с ними.

После построения новой симплекс-таблицы следует перейти к шагу 3.

Определение первоначального допустимого базисного решения

Изложенные выше вычисления проводились для случая, когда, начальное решение является допустимым. Если в начальном решении существуют b_i < 0, то допустимое начальное решение можно найти по следующему алгоритму.

Шаг 1. Выражение функции через свободные переменные,

Шаг 2. Составление симплекс-таблицы.

Шаг 3. Выбор переменной, вводимой в список базисных переменных.

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

Шаг 4. Выбор переменной, выводимой из списка базисных переменных.

Находят отношения элементов столбца свободных членов к элементам разрешающего столбца. Рассматривают отношения, в которых числитель и знаменатель отрицательные, и среди них выбирают минимальное. Строка, соответствующая выбранному отношению, например q-я, является разрешающей, и переменная, стоящая в этой строке, выводится из списка базисных переменных. Элемент а_qp, стоящий на пересечении разрешающей строки и разрешающего столбца, является разрешающие элементом.

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

Понятие об М-методе (методе искусственного базиса)

М-метод или метод искусственного базиса используется для определения первоначального базисного решения, когда оно не является допустимым, т.е. в начальном решении существуют b_i < 0.

При расчете с помощью симплексных таблиц удобнее пользоваться М-методом. Он заключается в следующем.

В каждое уравнение, дающее отрицательную компоненту в базисном решении, вводим свою новую неотрицательную искусственную переменную y₁, y₂, …, y_k, которая имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице включаем в число основных все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты базисного решения. Составляем новую линейную функцию T = F - M(y₁ + y₂ + … + y_k), где М - произвольно большое число, и ищем ее максимум (Т-задача). Выражение M(y₁ + y₂ + … + y_k) назовем М-функцией. Справедлива теорема:

1. Если в оптимальном решении Т-задачи искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходное задачи (т.е. T_max = F_max, если y₁ = y₂ = … = y_k = 0, т.е. минимум М-функции равен 0).

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

3. Если Т_max= ?, то исходная система также неразрешим, причем либо F_max= ?, либо условия задачи противоречивы.

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

Рассмотрим работу М-метода, используя симплексные таблицы, на примере.

Найти максимум целевой функции:

F(x) = x₁ + 2x₂ > max

при наложенных ограничениях:

x₁ - x₂ ? - 1,

x₁ - x₂ ? - 3,

x₁ ? 3.

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

Имеем F(x) = x₁ + 2x₂ > max

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

x₁ - x₂ + x₃ = - 1,

x₁ - x₂ - x₄ = - 3,

x₁ + x₅ = 3.

X₁ = (0; 0; -1; 3; 5) - недопустимое базисное решение с одной отрицательной компонентой, поэтому в первое уравнение введем искусственную переменную y₁ с тем же знаком, что и свободный член:

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

x₁ - x₂ - x₄ = - 3,

x₁ + x₅ = 3

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

- x₁ + x₂ + x₄ = 3,

x₁ + x₅ = 3.

T = x₁ + 2x₂ - My₁ > max.

Составляем первую симплексную таблицу.

Основные переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	х1	x2	x3	х4	x5	у1
у1	-1	1	-1	0	0	1	1	1
х4	-1	1	0	1	0	0	3	3
х5	1	0	0	0	1	0	3	?
F	-1	-2	0	0	0	0	0
Mф	М	-М	М	0	0	М	М

Последняя строка - это (-М) - функция, т.е. (-М_ф) у₁. Заполняем ее, умножая строку у₁ на коэффициент (-М). Проверяя выполнение критерия оптимальности при отыскании максимума (-М) - функции, определяем, что в последней строке имеется отрицательный элемент во втором столбце; значит он является разрешающим, переменная x₂ переходит в основные. Минимальное оценочное отношение в первой строке, она является разрешающей. Переменная у₁ переходит в состав неосновных переменных, обращается в нуль на следующем базисном решении и далее исключается из рассмотрения.

В соответствии с общим алгоритмом получаем таблицу:

Основные переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	х1	x2	x3	х4	х5
x2	-1	1	-1	0	0	1
х4	0	0	1	1	0	2
х5	1	0	0	0	1	3
F	-3	0	-2	0	0	2
Mф	0	0	0	0	0	0

Последняя строка показывает, что критерий оптимальности выполнен; max (-M_ф) = 0, значит min M_ф = 0, далее эту строку можно не рассматривать. Получено допустимое базисное решение (0; 1; 0; 2; 3), начиная с которого решаем исходную задачу в соответствии с обычным алгоритмом.

Замечание. При решении задачи на отыскание минимума линейной целевой функции рекомендуется вместо Z_min находить (-Z)_max.

1.8 Алгоритм матричного симплекс-метода

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

Алгоритм решения следующий:

1) определить ведущий столбец;

2) определить ведущий элемент;

3) определить ведущую строку;

4) составить уравнения пересчета матрицы;

5) выполнить пересчет матрицы;

6) проверить результаты пересчета матрицы на оптимальность;

7) если найденное решение оптимально, то вычисления прекратить и сформулировать ответ. Если найденное решение не оптимально, то перейти к п. 1.

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

Вся матрица в канонической задаче ЛП называется правильной, если она содержит m правильных столбцов (где m равно числу строк в матрице).

Все правильные столбцы должны содержать единицы в разных строках матрицы.

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

Ведущим столбцом может быть назначен любой столбец t матрицы, удовлетворяющий одному из условий:

· первый элемент, содержащий положительный элемент (кроме нуля) в строке (векторе) решений;

· столбец, содержащий наибольший положительный элемент в строке (векторе) решений;

· если столбец t удовлетворяет условию:

при решении задач на max;

при решении задач на min,

причем - коэффициент целевой функции в столбце j и - коэффициент в столбце j выбранной строки i матрицы А.

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

Критерием останова алгоритма поиска решений будет:

· для поиска max целевой функции - все коэффициенты вектора решений или равны нулю, или отрицательны;

· для поиска min целевой функции - все коэффициенты вектора решений или равны нулю, или положительны.

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

Рассмотрим работу симплексного метода на примере.

Найти максимум целевой функции:

F = x₁ + 2x₂ + x₃ + 2x₄ > max

при наложенных ограничениях:

x₁ + x₂ + 3x₄ ? 8;

2x₁ + 3x₂ + x₃ ? 14;

x₂ + 2x₃ + 4x₄ = 9.

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

x₁ + x₂ + 0x₂ + 3x₄ + x₅ 0x₆ = 8;

2x₁ + 3x₂ + x₃ + 0x₄ + 0x₅ - x₆ = 14;

0x₁ + x₂ + 2x₃ + 4x₄ + 0x₅ + 0x₆ = 9.

F(x) = x₁ + 2x₂ + x₃ + 2x₄ + 0x₅ + 0x₆ > max.

Оставим коэффициенты и получим условия задачи в матричном виде:

Таким образом, каноническая задача ЛП определена матрицей А, вектором свободных членов b = {8; 14; 9} и вектором решений c = {1; 2; 1; 2; 0; 0}.

Воспользуемся для расчета третьим способом. Четырем столбцам матрицы А соответствуют коэффициенты вектора решения больше нуля. Любой столбец может быть назначен ведущим.

По третьему правилу определим минимальные элементы в каждом столбце.

Для первого столбца: 8/1 14/2 > 1 • 14/2 = 7.

Для второго столбца: 8/1 14/3 9/1 > 2 • 14/3 = 28/3.

Для третьего столбца: 14/1 9/2 > 1 • 9/2 = 9/2.

Для четвертого столбца: 8/3 9/4 > 2 • 9/4 = 18/4.

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

Таким образом, ведущим элементом будет элемент a₂₂, ведущий столбец - второй, ведущая строка - вторая.

Во втором столбце будем исключать вторую переменную. Для этого надо, чтобы в ведущей строке коэффициент при второй переменной был равен 1.

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

,

где - новое значение элемента ведущей строки;

- текущее значение элемента ведущей строки;

- значение ведущего элемента

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

где - новое значение элемента первой строки;

- новое значение элемента второй (ведущей) строки.

Такое преобразование строк матрицы носит название преобразования Жордана-Гаусса.

Для третьей строки:

Для четвертой строки (строки вектора решений):



Значение целевой функции f определим по формуле:

где - коэффициент целевой функции.

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

Для третьего столбца: 14 13/5 > 1/3 • 13/5 = 13/15.

Для четвертого столбца: 10/9 13/12 > 2 • 13/12 = 13/6.

Для шестого столбца: 10 13 > 2/3 • 10 = 20/3.

Ведущим элементом будет a₁₆.

Определим формулы для пересчета строк матрицы.

Для ведущей (первой) строки:

Для второй, третьей и четвертой строк соответственно:

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

Для ведущей (третьей) строки:

Для первой, второй и четвертой строк соответственно:

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

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

Ответ: X {0; 8; 1/2; 0}.

Т.к. пятая и шестая переменные - фиктивные, то в решении они не учитываются. Максимальное значение, равное 33/2, целевая функция принимает при следующих значениях аргументов: x₁ = 0; x₂ = 8; x₃ = 1/2; x₄ = 0.

Проверка:

F(x) = x₁ + 2x₂ + x₃ + 2x₄ = 1 • 0 + 2 • 8 + 1 • 1/2 + 2 • 0 = 0 + 16 + 0,5 + 0 = 16,5;

x₁ + x₂ + 3x₄ ? 8; 1 • 0 + 1 • 8 + 0 • 0,5 + 3 • 0 ? 8; 0 + 8 + 0 + 0 ? 8; 8 ? 8;

2x₁ + 3x₂ + x₃ ? 14; 2 • 0 + 3 • 8 + 1 • 0,5 + 0 • 0 ? 14; 24,5 ? 14;

x₂ + 2x₃ + 4x₄ = 9; 0 • 0 + 1 • 8 + 2 • 0,5 + 4 • 0 = 9; 0 + 8 + 1 + 0 = 9; 9 = 9.

Общие случаи решения задач ЛП матричным симплекс-методом

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

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

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

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

Рассмотрим пример, решив его вторым подходом.

Найти максимум целевой функции F(x) = - 2x₁ + 3x₂ > max

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

2x₁ - x₂ ? 6;

- x₁ + 3x₂ ? 6;

x₁ + 2x₂ ? 8;

x_j ? 0,

Выполнив необходимые преобразования, получим матричную модель

Первый элемент последней строки - отрицательный. Выполнив преобразование Жордана - Гаусса относительно элемента а₃₁, т.к. он имеет коэффициент, равный единице. Формула для пересчета последней строки:



Теперь для определения максимума целевой функции переходим к алгоритму, описанному в пункте 2.5.

Ведущим элементом будет а₂₂. Пересчитаем коэффициенты торой строки

Формула для пересчета первой строки: .

Формула для пересчета третьей строки: .

Формула для пересчета четвертой строки: .

Ведущий элемент - а₃₅. Формула для пересчета четвертой строки:

.



Все коэффициенты последней строки отрицательные. Целевая функция достигает своего максимума, равного 6, в точке Х (0; 2).

Проверка:

F(x) = - 2 • 0 + 3 • 2 = 6.

Первое ограничение: 2 • 0 - 1 • 2 ? 6, - 2 ? 6.

Второе ограничение: - 1 • 0 + 3 • 2 ? 6, 6 ? 6.

Третье ограничение: 1 • 0 + 2 • 2 ? 8, 4 ? 8.

2. Решение задач симплекс-методом

Предприятию требуется составить план выпуска двух видов изделий четырьмя цехами так, чтобы от продаж изготовленной продукции предприятие получило наибольшую прибыль. Оба вида изделий последовательно обрабатываются в этих четырех цехах (таблица 1). В плане должно быть предусмотрено, что I цех может обрабатывать эту продукцию в течении 15 ч, II цех - 8 ч, III цех - 16 ч, IV цех - 12 ч.

Таблица 1. Обработка изделий в цехах

Изделия	Цех
	1	2	3	4
I	2	1	4	0
II	3	2	0	4

Предприятие от продажи изделия первого вида получило 2 руб. прибыли, от второго вида - 3 руб. прибыли.

2.1 Решение задачи с помощью симплекс-таблиц

Обозначим первый вид изделия за х₁, а второй - х₂.

Составим математическую модель этой задачи:

F = 2x₁ + 3x₂ > max

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

2х₁ + 3х₂ ? 15,

х₁ + 2х₂ ? 8,

4х₁ ? 16,

4х₂ ? 12,

х₁ ? 0, х₂ ? 0.

Приведем систему ограничений к каноническому виду, введя дополнительные неотрицательные переменные со знаком «+», т.к. неравенства имеют вид «?».

2х₁ + 3х₂ + х₃ = 15,

х₁ + 2х₂ + х₄ = 8,

4х₁ + х₅ = 16,

4х₂ + х₆ = 12.

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

2х₁ + 3х₂ + х₃ = 15,

х₁ + 2х₂ + х₄ = 8,

4х₁ + х₅ = 16,

4х₂ + х₆ = 12,

F - 2x₁ - 3x₂ = 0.

Шаг 1.

1. Определим основные и неосновные переменные:

основные: х₃, х₄, х₅, х₆;

неосновные: х₁, х₂.

2. Выразим основные переменные через неосновные:

х₃ = 15 - 2х₁ - 3х₂,

х₄ = 8 - х₁ - 2х₂,

х₅ = 16 - 4х₁,

х₆ = 12 - 4х₂.

3. Запишем первое базисное решение, положив неосновные переменные равными нулю: Х₁ = (0; 0; 15; 8; 16; 12).

Шаг 2.

Выразим F через неосновные переменные и вычислим ее значение:

F = 2x₁ + 3x₂.

F₁ = F(X₁) = 2 • 0 + 3 • 0 = 0.

Шаг 3. Заполним симплекс-таблицу.

Основные переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	х1	х2	х3	х4	х5	х6
х3	2	3	1	0	0	0	15	5
х4	1	2	0	1	0	0	8	4
х5	4	0	0	0	1	0	16	?
х6	0	4	0	0	0	1	12	3
F	-2	-3	0	0	0	0	0

Т.к. существует отрицательный коэффициент в последней (оценочной) строке, то решение не оптимально.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

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

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

Шаг 3. Выполним симплекс-преобразования и перейдем к новой симплекс-таблице.



Основные переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	х1	х2	х3	х4	х5	х6
х3	2	0	1	0	0	-3/4	6	3
х4	1	0	0	1	0	-1/2	2	2
х5	4	0	0	0	1	0	16	4
х2	0	1	0	0	0	1/4	3	?
F	-2	0	0	0	0	3/4	9

Т.к. существует отрицательный коэффициент в оценочной строке, то решение не оптимально.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

Отрицательный коэффициент а₅₁ = -2. Первый столбец - разрешающий. Переменная х₁ вводится в состав основных.

2. Определим выводимую переменную.

Найдем оценочное отношение. Минимальное оценочное отношение равно 2. Вторая строка является разрешающей. Переменная х₄ выводится из состава основных переменных.

Шаг 3. Выполним симплекс-преобразования и перейдем к новой симплекс-таблице.

Основные переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	х1	х2	х3	х4	х5	х6
х3	0	0	1	-2	0	1/4	2	8
х1	1	0	0	1	0	-1/2	2	?
х5	0	0	0	-4	1	2	8	4
х2	0	1	0	0	0	1/4	3	12
F	0	0	0	2	0	-1/4	13

Т.к. существует отрицательный коэффициент в оценочной строке, то решение не оптимально.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

Отрицательный коэффициент а₅₆ = -1/4. Шестой столбец - разрешающий. Переменная х₆ вводится в состав основных.

2. Определим выводимую переменную.

Найдем оценочное отношение. Минимальное оценочное отношение равно 4. Третья строка является разрешающей. Переменная х₅ выводится из состава основных переменных.

Шаг 3. Выполним симплекс-преобразования и перейдем к новой симплекс-таблице.

Основные переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	х1	х2	х3	х4	х5	х6
х3	0	0	1	3/2	-1/8	0	1
х1	1	0	0	0	1/4	0	4
х6	0	0	0	-2	1/2	1	4
х2	0	1	0	1/2	-1/8	0	2
F	0	0	0	3/2	1/8	0	14

Критерий оптимальности выполнен, т.к. в последней строке нет отрицательных значений. F_max = 14, оптимальное базисное решение: Х = (4; 2; 1; 0; 0; 4).

В результате решения получаем ответ:

Для того чтобы предприятие получило максимальную прибыль, необходимо выпустить 4 изделия первого вида и 2 изделия второго вида, учитывая последовательную обработку в четырех цехах. В результате этого максимальная прибыль составит 14 руб.

2.2 Решение задачи матричным симплекс-методом

Составим математическую модель данной задачи:

F = 2x₁ + 3x₂ > max

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

2х₁ + 3х₂ ? 15,

х₁ + 2х₂ ? 8,

4х₁ ? 16,

4х₂ ? 12,

х₁ ? 0, х₂ ? 0.

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

2х₁ + 3х₂ + х₃ + 0х₄ + 0х₅ + 0х₆ = 15,

х₁ + 2х₂ + 0х₃ + х₄ + 0х₅ + 0х₆ = 8,

4х₁ + 0х₂ + 0х₃ + 0х₄ + х₅ + 0х₆ = 16,

0х₁ + 4х₂ + 0х₃ + 0х₄ + 0х₅ + х₆ = 12.

F(x) = 2x₁ + 3x₂ + 0х₃ + 0х₄ + 0x₅ + 0x₆ > max.

Оставим коэффициенты и получим условия задачи в матричном виде:

Воспользуемся для расчета третьим способом. Двум столбцам матрицы А соответствуют коэффициенты вектора решения больше нуля. Любой столбец может быть назначен ведущим.

Определим минимальные элементы в каждом столбце.

Для первого столбца: 15/2 8/1 16/4 > 2 • 4 = 8.

Для второго столбца: 15/3 8/2 12/4 > 3 • 3 = 9.

Из двух величин выберем максимальное. В данном случае это 9.

Таким образом, ведущим элементом будет элемент a₄₂, ведущий столбец - второй, ведущая строка - четвертая.

Во втором столбце будем исключать четвертую переменную. Для этого надо, чтобы в ведущей строке коэффициент при второй переменной был равен 1.

Пересчитаем элементы ведущей строки по формуле и получим матрицу в виде:

В остальных строках матрицы коэффициент при второй переменной должен быть равен 0. В итоге получим:

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

Для первого столбца: 3 2 4 > 2 • 2 = 4.

Ведущим элементом будет a₂₁.

Пересчитаем строки матрицы.

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

Для шестого столбца: 8 4 12 > 1/4 • 4 = 1.

Ведущий элемент - а₃₆.

Пересчитаем строки матрицы.

Т.к. вектор решения содержит нулевые и отрицательные значения, то найдено оптимальное решение. F_max = 14, оптимальное базисное решение: X {4; 2; 1; 0; 0; 4}.

В результате решения получаем ответ:

Для того чтобы предприятие получило максимальную прибыль, необходимо выпустить 4 изделия первого вида и 2 изделия второго вида, учитывая последовательную обработку в четырех цехах. В результате этого максимальная прибыль составит 14 руб.

Сравнение матричного симплекс-метода с табличным.

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

1) в последней (оценочной) строке против всех основных переменных ставим нуль;

2) предыдущая разрешающая строка пересчитывается делением на разрешающий элемент;

3) расставляем нули и единицы в столбцах соответствующим основным переменным:

· 1 - против «своей основной переменой»,

· 0 - против «чужой переменной»;

4) для заполнения других коэффициентов пользоваться формулой:

где p - номер разрешающего столбца,

q - номер разрешающей строки.

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

2.3 Решение задачи М-методом (методом искусственного базиса)

Найти максимум целевой функции:

F(x) = x₁ + 2x₂ > max

при наложенных ограничениях:

x₁ - x₂ ? - 1,

x₁ - x₂ ? - 3,

x₁ ? 3.

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

Имеем: F(x) = x₁ + 2x₂ > max

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

x₁ - x₂ + x₃ = - 1,

x₁ - x₂ - x₄ = - 3,

x₁ + x₅ = 3.

Выразим основные переменные через неосновные.

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

х₄ = - 3 - х₁ + х₂,

х₅ = 3 - х₁.

Положив неосновные переменные равными нулю, получим базисное решение: X₁ = (0; 0; -1; 3; 5), которое является недопустимым, т.к. базисное решение имеет одну отрицательную компоненту. Поэтому в первое уравнение введем искусственную переменную y₁ с тем же знаком, что и свободный член:

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

x₁ - x₂ - x₄ = - 3,

x₁ + x₅ = 3

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

- x₁ + x₂ + x₄ = 3,

x₁ + x₅ = 3.

T = x₁ + 2x₂ - My₁ > max.

Составляем первую симплексную таблицу.



Основные переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	х1	x2	x3	х4	x5	у1
у1	-1	1	-1	0	0	1	1	1
х4	-1	1	0	1	0	0	3	3
х5	1	0	0	0	1	0	3	?
F	-1	-2	0	0	0	0	0
Mф	М	-М	М	0	0	М	М

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

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

В соответствии с общим алгоритмом получаем таблицу:

Основные переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	х1	x2	x3	х4	х5
x2	-1	1	-1	0	0	1	?
х4	0	0	1	1	0	2	?
х5	1	0	0	0	1	3	3
F	-3	0	-2	0	0	2
Mф	0	0	0	0	0	0

Последняя строка показывает, что критерий оптимальности выполнен; max (-M_ф) = 0, значит min M_ф = 0, далее эту строку можно не рассматривать. Получено допустимое базисное решение: Х₁ = (0; 1; 0; 2; 3), начиная с которого решаем исходную задачу в соответствии с обычным алгоритмом.

Т.к. существует отрицательный коэффициент в оценочной строке, то решение не оптимально.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

Максимальный отрицательный коэффициент а₄₁ = -3. Первый столбец - разрешающий. Переменная х₁ вводится в состав основных.

2. Определим выводимую переменную.

Найдем оценочное отношение. Минимальное оценочное отношение равно 3. Третья строка является разрешающей. Переменная х₅ выводится из состава основных переменных.

3. Выполним симплекс-преобразования и перейдем к новой симплекс-таблице.

Основные переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	х1	x2	x3	х4	х5
x2	0	1	-1	0	1	4	?
х4	0	0	1	1	0	2	2
х1	1	0	0	0	1	3	?
F	0	0	-2	0	3	11

Т.к. существует отрицательный коэффициент в оценочной строке, то решение не оптимально.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

Отрицательный коэффициент а₄₃ = -2. Третий столбец - разрешающий. Переменная х₃ вводится в состав основных.

2. Определим выводимую переменную.

Найдем оценочное отношение. Минимальное оценочное отношение равно 2. Вторая строка является разрешающей. Переменная х₄ выводится из состава основных переменных.

3. Выполним симплекс-преобразования и перейдем к новой симплекс-таблице.



Основные переменные	Коэффициенты при переменных	Свободные члены	Оценочное отношение
	х1	x2	x3	х4	х5
x2	0	1	0	1	1	6
х3	0	0	1	1	0	2
х1	1	0	0	0	1	3
F	0	0	0	2	3	15

Критерий оптимальности выполнен, т.к. в последней строке нет отрицательных значений. F_max = 15, оптимальное базисное решение: Х = (3; 6; 2; 0; 0).

Заключение

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

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

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

1. Роль симплексного метода достаточно велика, т.к. симплекс-метод находит применение для решения широкого круга задач линейного программирования в экономической сфере, сфере планирования и других сферах, связанных с производством, и до настоящего времени является одним из основных методов.

2. Матричный симплекс-метод более трудоемкий, чем табличный, т.к. для решения задачи матричным симплекс-методом для каждой строки составляется соответствующая формула пересчета.

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

4. Симплексный метод и его разновидности в настоящее время достаточно востребованы во всех сферах производства.

Список литературы

1. Введение в исследование операций. 6-е издание.: Пер. с англ. - М.: Издательский дом «Вильямс», 2001. - 912 с.: ил. - Парал. тит. англ.

2. Исследование операций в экономике: Учебное пособие для вузов/ Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2001. - 407 с.

3. Линейное программирование. Ашманов С.А. - М.: Наука. Главная редакция физико-математической литературы, 1981. - 340 с.

4. Малеко Е.М. Математические методы и модели исследования операций: Учеб. пособие. - Магнитогорск: МаГУ, 2003. - 100 с.

5. Математические методы в программировании: Учебник. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. - 224 с.: ил. - (Профессиональное образование). - (Учимся программировать).

6. Математическое программирование: Учебное пособие. - 2-е издание, переработанное и дополненное / Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. - М.: Высшая школа, 1980. - 300 с.

7. Справочник по математике для инженеров и учащихся втузов. Бронштейн И.Н., Семендяев К.А. - М.: Наука. Главная редакция физико-математической литературы, 1981.

Приложение

Dim KolBazPer, KolPer, nomerMinus, numStroki, numStolbca As Integer

Dim flag As Boolean

Sub delay(zaderjka)

PauseTime = zaderjka ' Установка задержки

Start = Timer 'Старт таймера

Do While Timer < Start + PauseTime

DoEvents ' Позволяет выполнять действия в процессе задержки

Loop

End Sub

Private Sub Clear_Click()

'Гасим кнопку вычисление

Vichislenie. Enabled = False

'Форматирование

Range («A:Z»).Clear

Range («A:Z»).Select

Selection. ColumnWidth = 8.63

Range («A1»).Select

End Sub

Sub ПоискРазрешающейСтроки()

For i = 3 To KolBazPer + 2

If Worksheets («Лист1»).Cells (i, nomerMinus).Value * Worksheets («Лист1»).Cells (i, KolPer + 2).Value > 0 Then

OcOtn = Cells (i, KolPer + 2).Value / Cells (i, nomerMinus).Value

Cells (i, KolPer + 3) = OcOtn

End If

If (Worksheets («Лист1»).Cells (i, nomerMinus).Value * Worksheets («Лист1»).Cells (i, KolPer + 2).Value < 0) _

Or (Worksheets («Лист1»).Cells (i, nomerMinus).Value = 0) _

Or ((Worksheets («Лист1»).Cells (i, KolPer + 2).Value = 0) _

And (Worksheets («Лист1»).Cells (i, nomerMinus).Value > 0)) Then

OcOtn = «Бесконечность»

Cells (i, KolPer + 3) = OcOtn

End If

If ((Worksheets («Лист1»).Cells (i, KolPer + 2).Value = 0) _

And (Worksheets («Лист1»).Cells (i, nomerMinus).Value < 0)) Then

OcOtn = 0

Cells (i, KolPer + 3) = OcOtn

End If

Next i

If Worksheets («Лист1»).Cells (3, KolPer + 3) = «Бесконечность» Then

min = 10000

Else

min = Worksheets («Лист1»).Cells (3, KolPer + 3) 'минимальный элемент - первый

End If

nomerMinus = 3 'строка минимального элемента третья

For i = 3 To KolBazPer + 2

'проверка следующего элемента на минимальность

If (Worksheets («Лист1»).Cells (i, KolPer + 3) < min) And _

(Worksheets («Лист1»).Cells (i, KolPer + 3) <> «Бесконечность») Then

min = Worksheets («Лист1»).Cells (i, KolPer + 3)

nomerMinus = i

End If

Next i

numStroki = nomerMinus

Range (Cells(nomerMinus, 1), Cells (nomerMinus, KolPer + 3)).Select

Selection. Interior. Color = vbGreen

End Sub

Sub ПоискРазрешающегоСтолбца()

Dim s, i, j, min As Integer

s = 0

For j = 2 To KolPer + 1

If Worksheets («Лист1»).Cells (KolBazPer + 3, j) < 0 Then 'Проверка строки на отрицательный элемент

s = s + 1 'сумма отрицательных элементов

If s = 1 Then 'если отриц. элемент =1, запомнить номер столбца

nomerMinus = j

End If

End If

Next j

If s = 1 Then 'если отриц. элемент =1, окрасить столбец в зеленый

numStolbca = nomerMinus

Range (Cells(2, nomerMinus), Cells (KolBazPer + 3, nomerMinus)).Select

Selection. Interior. Color = vbGreen

ElseIf s = 0 Then

MsgBox «Найдено оптимальное решение. F =» & Worksheets («Лист1»).Cells (KolBazPer + 3, KolPer + 2), vbOK, «Ответ»

flag = True

Else

'Нахождение максимального отрицательного элемента, если в индексной строке их несколько

min = Worksheets («Лист1»).Cells (KolBazPer + 3, 2) 'минимальный элемент - первый

nomerMinus = 2 'столбец минимального элемента второй

For i = 2 To KolPer + 1

'проверка следующего элемента на минимальность

If Worksheets («Лист1»).Cells (KolBazPer + 3, i) < min Then

min = Worksheets («Лист1»).Cells (KolBazPer + 3, i)

nomerMinus = i

End If

Next i

numStolbca = nomerMinus

Range (Cells(2, nomerMinus), Cells (KolBazPer + 3, nomerMinus)).Select

Selection. Interior. Color = vbGreen

End If

End Sub

Sub НоваяСТ()

Dim RazRelem

For i = 3 To KolBazPer + 3

For j = 2 To KolPer + 2

Worksheets («Лист2»).Cells (i, j).Value = Worksheets («Лист1»).Cells (i, j).Value

Next j

Next i

RazRelem = Cells (numStroki, numStolbca).Value

For i = 3 To KolBazPer + 3

For j = 2 To KolPer + 2

With Worksheets («Лист2»)

If numStroki = i Then

Cells (i, j).Value =.Cells (i, j).Value / RazRelem 'вычисление разрешающей строки

Else

Cells (i, j).Value =.Cells (i, j).Value - ((.Cells (i, numStolbca).Value *.Cells (numStroki, j).Value) / RazRelem) 'пересчет таблицы

End If

End With

Next j

Next i

End Sub

Sub НахождениеМаксимума()

Do

'Снятие окраски

Range (Cells(1, 1), Cells (KolBazPer + 3, KolPer + 3)).Select

Selection. Interior. Color = vbWhite

ПоискРазрешающегоСтолбца

delay (1)

If Not flag Then ПоискРазрешающейСтроки

delay (1)

If Not flag Then НоваяСТ

delay (1)

Loop While flag = False

End Sub

Private Sub Vichislenie_Click()

НахождениеМаксимума

'Гасим кнопку вычисление

Vichislenie. Enabled = False

End Sub

Private Sub VvodParam_Click()

flag = False

'Зажигаем кнопку вычисление

Vichislenie. Enabled = True

' Ввод параметров таблицы

KolBazPer = CInt (InputBox(«Введите количество базисных переменных:», «Ввод параметров»))

KolPer = CInt (InputBox(«Введите количество переменных:», «Ввод параметров»))

'Оформление шапки

Range («A1:A2»).Select

ActiveCell. FormulaR1C1 = «»

With Selection

HorizontalAlignment = xlCenter

VerticalAlignment = xlCenter

WrapText = True

MergeCells = True

End With

Columns («A:A»).ColumnWidth = 14

Range (Cells(1, 2), Cells (1, KolPer + 1)).Select

Selection. Merge

Range («B1»).Value = «Коэффициенты при переменных»

With Selection

HorizontalAlignment = xlCenter

VerticalAlignment = xlCenter

WrapText = True

MergeCells = True

End With

Range (Cells(1, KolPer + 2), Cells (2, KolPer + 2)).Select

ActiveCell. FormulaR1C1 = «Свободные члены»

With Selection

HorizontalAlignment = xlCenter

VerticalAlignment = xlCenter

WrapText = True

MergeCells = True

End With

Columns (KolPer + 2).ColumnWidth = 14

Range (Cells(1, KolPer + 3), Cells (2, KolPer + 3)).Select

ActiveCell. FormulaR1C1 = «Оценочное отношение»

With Selection

HorizontalAlignment = xlCenter

VerticalAlignment = xlCenter

WrapText = True

MergeCells = True

End With

Columns (KolPer + 3).ColumnWidth = 14

Range (Cells(KolBazPer + 3, 1), Cells (KolBazPer + 3, 1)).Select

Selection. Value = «F»

With Selection

HorizontalAlignment = xlCenter

VerticalAlignment = xlCenter

MergeCells = True

End With

Dim j As Integer

For j = 2 To KolPer + 1

Cells (2, j) = «Х» & j - 1

Next j

'Начертание границ таблицы

Range (Cells(1, 1), Cells (KolBazPer + 3, KolPer + 3)).Select

Selection. Borders(xlDiagonalDown).LineStyle = xlNone

Selection. Borders(xlDiagonalUp).LineStyle = xlNone

With Selection. Borders(xlEdgeLeft)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

With Selection. Borders(xlEdgeTop)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

With Selection. Borders(xlEdgeBottom)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

With Selection. Borders(xlEdgeRight)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

With Selection. Borders(xlInsideVertical)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

With Selection. Borders(xlInsideHorizontal)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

Range («A1»).Select

End Sub

Размещено на Allbest.ru