Формирование и решение линейных задач

6x₁+2x₂ Ј 27

x₁ і 0, x₂ і??

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

x₁/14+x₂/7/2 Ј 1

x₁/6+x₂/9/2 Ј 1

x₁/9/2+x₂/27/2 Ј1

x₁ і0, x₂ і_.

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

F=x₁+x₂ ® max (5.13)

Эту зависимость представим в виде x₂= F-x₁. Из графика данного уравнения (Рис. 5.1) следует, что tg?= ?1, при этом ? =135^о, а величина F равна отрезку, отсекаемому прямой функции цели на оси координат. Если прямую перемещать параллельно самой себе в направлении, указанном стрелками, то эта величина будет возрастать. Очевидно, что оптимальным решением будут координаты точки С (x^?₁; x^?₂). При этом F=F^?.

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

Метод решения задачи линейного программирования:

Найти вершины ОДР, как точки пересечения ограничений.

Определить последовательно значения целевой функции в вершинах.

Вершина, в которой целевая функция приобретает оптимальное значение, является оптимальной вершиной.

Координаты оптимальной вершины являются оптимальными значениями искомых переменных.

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

Тот факт, что оптимальное решение находится на вершине ОДР, дает еще два очень важных вывода:

если оптимальным решением являются координаты вершин ОДР, значит, сколько вершин имеет ОДР, столько оптимальных решений может иметь задача.

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

Как видно на Рис. 5.1, вершина, координаты которой являются оптимальным решением, определяется углом наклона прямой, описывающей целевую функцию. Значит, каждая вершина будет соответствовать оптимальному решению для некоторой целевой функции. Поясним это на рассмотренном ранее примере. Раньше мы находили оптимальное решение по максимизации суммарного выпуска F₁=x₁+x₂ ? max. Найдем оптимальные решения еще для четырех целевых функций:

F₂=x₂ ® max (максимизация выпуска продукции П₂)

F₃=x₁ ® max (максимизация выпуска продукции П₁)

F₄=4x₁+8,5x₂ ® max (максимизация прибыли)

F₅=(1+3+6) x₁ + (4+4+2) x₂ = 10х₁+10х₂ ® max (минимизация используемых ресурсов).

Для каждой целевой функции, так же как и для F₁, можно построить линию целевой функции и определить вершину, в которой целевая функция будет иметь оптимальное значение. Результаты решения задачи по пяти целевым функциям сведем в таблицу 4.2, из анализа которой можно сделать вывод: координаты каждой вершины могут быть оптимальным решением в некотором смысле.

Таблица 4.2

Целевая функция	Вершина	x1	x2	x1+x2	Прибыль	Используемый ресурс
F1=x1+x2 ? max	C	4	1,5	5,5	28,75	55
F2=x2 ? max	A	0	3,5	3,5	29,75	35
F3=x1 ? max	D	4,5	0	4,5	18	45
F4=4x1+8,5x2 ? max	B	2	3	5	33,5	50
F5= 10х1+10х2	0	0	0	0	0	0

4.4 Симплексный метод

Симплексный метод или метод последовательного улучшения плана является одним из основных методов решения задач ЛП. название симплексный метод берет от слова «симплекс», которым создатель метода Р. Данциг обозначил наложенное на переменные x₁, x₂… x_n ограничение x₁+x₂+… +x_n=1.

В математике симплексом в k-мерном пространстве называется совокупность k+1 вершин.

Так для плоскости при k=2 симплексом будет треугольник; в пространстве при k=3 симплексом будет тетраэдр, имеющий 4 вершины.

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

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

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

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

4x₁+9x₂ Ј 56

5x₁+3x₂ Ј 37

x₁+2x₂ Ј2

обращающее в максимум линейную форму:

¦=3x₁+4x₂ (5.15)

Вначале перейдем от системы неравенств (5.14) к системе уравнений, добавив к левым частям неравенств неотрицательные переменные x₃, x₄, x₅. Мы получим:

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

5x₁+3x₂+0. x₃+x₄+0. x₅=37

оx₁+2x₂+0. x₃+0. x₄+ x₅=2

¦=3x₁+4x₂+0. x₃+0. x₄+0. x₅ (5.17)

перепишем теперь систему (5.16) в виде системы 0-уравнений:

0=56 - (4x₁+9x₂+1. x₃+0. x₄+0. x₅)

0=37 - (5x₁+3x₂+0. x₃+1. x₄+0. x₅)

0=2 - (-x₁+2x₂+0. x₃+0. x₄+1. x₅?

¦=0 - (-3x₁-4x₂-0. x₃-0. x₄-0. x₅) (5.19)

заметим, что система (5.18) может быть записана в виде одного векторного равенства:

0=B - (A₁x₁+A₂x₂+A₃x₃+A₄x₄+A₅x₅),

где вектор-столбец В имеет своими компонентами свободные члены, а векторы A₁, A₂,…, A₅ - коэффициенты при соответствующих переменных x₁, x₂, x₃, x₄, x₅.

Линейная форма имеет вид: ¦=3x₁+4x₂+0. x₃+0. x₄+0. x₅.

Векторы A₃, A₄, A₅ образуют базис. Это означает, что, присвоив х₁=0, х₂=0, получаем из (5.16) первое базисное решение: x₁=0; x₂=0; x₃=56; x₄=37; x₅=2.

При этом значение линейной формы ?=0. На основании (5.18) строим первую симплексную таблицу.

Симплексная таблица строится следующим образом:

В заглавной строке пишем последовательно векторы B, A₁, A₂, A₃, A_4, A₅. Слева добавляем колонку «Базисные векторы», рядом с ней колонку «С», в которой поставлены коэффициенты при базисных переменных в линейной форме, в данном случае величины С₃, С₄, С₅. В последней строке, называемой индексной, и обозначаемой через ? j-С_j, проставляются числа, равные значению линейной формы, в соответствием с уравнением (j=1, 2, 3, 4, 5). В итоге мы имеем таблицу 4.1.

Таблица 4.1.

Базисные	Коэффициенты	Вектор свободных	3	4	0	0	0
векторы	линейной формы С	членов В	A1	A2	A3	A4	A5
A3	0	56	4	9	1	0	0
A4	0	37	5	3	0	1	0
A5	0	2	-1	2	0	0	1
Индексная строка ? j-Сj	0	-3	-4	0	0	0

Это первая симплексная таблица, соответствующая первому базисному решению: x₁=0; x₂=0; x₃=56; x₄=37; x₅=2. Значение линейной формы, равное нулю, мы записываем в первой клетке индексной строки.

Т.к. мы решаем задачу на максимум, то из выражения линейной формы видно, что имеет смысл увеличить x₁ или x₂. Действительно, коэффициенты при этих переменных в скобках отрицательны (а по существу положительны), и если мы положим x₁?0 или x₂?0, то значение ? увеличится. Но эти же коэффициенты с их знаками стоят в индексной строке.

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

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

Таким образом, ведущей строкой будет строка A₅. На пересечении ведущего столбца и ведущей строки стоит разрешающий элемент. В нашем случае - это число 2.

Теперь мы приступаем к составлению второй таблицы или второго плана. Вместо единичного вектора A₅ мы в базис вводим вектор A₂. Переход к новому базису, как это известно, эквивалентен элементарному преобразованию матрицы, элементами которой служат числа табл. 4.1. А именно: в новой таблице элемент строки, соответствующий элементу ведущей строки прежней таблицы, равен этому элементу ведущей строки, разделенному на разрешающий элемент. чтобы получить любой другой элемент новой симплексной таблицы, нужно от соответствующего элемента прежней таблицы отнять произведение элемента ведущей строки на элемент ведущего столбца, разделенное на разрешающий элемент. Например, элементу 4 (табл. 4.1) будет соответствовать элемент табл. 4.2:

Таким образом, мы переходим ко второй таблице (таблица 4.2). Указанные выше преобразования относятся к столбцам B, A₁, A₂, A₃, A_4, A₅.

Таблица 4.2.

Базисные	Коэффициенты	Вектор свободных	3	4	0	0	0
векторы	линейной формы С	членов В	A1	A2	A3	A4	A5
A3	0	47	17/2	0	1	0	-9/2
A4	0	34	13/2	0	0	1	-3/2
A5	4	1	-1/2	1	0	0	1/2
Индексная строка ? j-Сj	4	-5	0	0	0	2

Из табл. 4.2 видно, что значение линейной формы возросло и теперь равно 4. Однако наличие в индексной строке отрицательных чисел свидетельствует о том, что это значение еще можно увеличить. Переходим к следующей симплексной таблице. число «5» определяет ведущий столбец. Находим ведущую строку. Для этого определяем:

Итак, разрешающим элементом будет 13/2. Вектор A₄ выводим из базиса и вводим вместо него вектор A₁. Пересчет коэффициентов осуществляем по указанным выше правилам и получаем таблицу 4.3.

Таблица 5.3

Базисные	Коэффициенты	Вектор свободных	3	4	0	0	0
векторы	линейной формы С	членов В	A1	A2	A3	A4	A5
A3	0	33/13	0	0	1	-17/13	-33/13
A1	3	68/13	1	0	0	2/13	-3/13
A2	4	47/13	0	1	0	1/13	5/13
Индексная строка ? j-Сj	392/13	0	0	0	10/13	11/13

В индексной строке нет отрицательных элементов. Следовательно, мы получим оптимальную программу. Оптимальное решение:

x₁=68/13; x₂=47/13; x₃=33/13; x₄ = x₅ = 0.

4.5 Анализ симплекс-таблиц

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

При оперативном управлении решается достаточно широкий и важный круг вопросов, которые возникают при ежедневном обеспечении производственного процесса. Мы рассмотрим лишь те вопросы оперативного управления, которые могут быть решены с помощью моделей, уже составленных при планировании. «Что будет, если пять человек из числа трудовых ресурсов отвлекут на другие работы? Что будет, если сырья поставят на 20% меньше? Какую продукцию следует выпускать, если изменились цены?» Рассмотрим, как находить ответы на эти вопросы на конкретном примере.

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

Таблица 4.1

Элемент	Вид продукции	Располагаемый
модели	П1	П2	П3	П4	ресурс
Ресурсы:
трудовые	1	1	1	1	16
сырье	6	5	4	3	110
оборудование	4	6	10	13	100
Прибыль с единицы продукта	60	70	120	130	-
План	х1	х2	х3	х4	-

x₁ + x₂ + x₃+ x₄ Ј 16

6x₁ + 5x₂ + 4x₃+ 3x₄ Ј 110

4x₁ + 6x₂ + 10x₃+ 13x₄ Ј100

x_j і 0, j і??4?

F = 60x₁ + 70x₂ + 120x₃ + 130x₄ ® max

От системы неравенств (5.20) перейдем к системе уравнений. Для этого, в каждое неравенство добавим по одной дополнительной переменной: y_i 0, i m. Тогда получим систему уравнений:

x₁ + x₂ + x₃+ x₄ + y₁ =16

6x₁ + 5x₂ + 4x₃+ 3x₄ + y₂ =110

4x₁ + 6x₂ + 10x₃+ 13x₄ + y₃ =100

x_j і 0, j =??4; y_i і 0, i = 1,3.

F = 60x₁ + 70x₂ + 120x₃ + 130x₄ ? max

Затем перепишем систему (5.21) в следующем виде:

y₁ =16 - ?x₁ + x₂ + x₃+ x₄)

y₂ =110 - ?6x₁ + 5x₂ + 4x₃+ 3x₄)

y₃ =100 - ?4x₁ + 6x₂ + 10x₃+ 13x₄)

F = 0 - (-60x₁ - 70x₂ - 120x₃ - 130x₄)

Систему (5.22) можно представить в виде Таблицы 5В, которую составляют следующим образом: свободные переменные, заключенные в скобки, выносят в верхнюю строку таблицы. В остальные столбцы записывают свободные члены и коэффициенты перед свободными переменными. Эта, так называемая симплекс таблица, служит основой для решения задач линейного программирования. В этой таблице переменные, являющиеся свободными, в данном случае x₁, x₂, x₃, x₄ по условию равны 0. Поскольку свободные переменные равны 0, то из системы (5.22) видно, что базисные переменные y₁, y₂, y₃, а также целевая функция F, которую записывают снизу, равны свободным членам. Значит y₁=16, y₂=110, y₃=100, F=0.

Таблица 4.2

Величина	Свободный	Свободные переменные
	член	х1	х2	х3	х4
Базисные переменные:
y1	16	1	1	1	1
y2	110	6	5	4	3
y3	100	4	6	10	13
Индексная строка (F)	0	- 60	- 70	- 120	- 130

Напомним, что в системе общее число переменных N=n+m, где n - число основных переменных, m - число дополнительных переменных. Все переменные можно подразделить с одной стороны на основные и дополнительные, а с другой - на базисные и свободные.

Свободными переменными будем называть такие, которые равны 0.

Из теории известно, что n переменных в допустимом решении должны быть равны 0, т.е. столько же переменных, сколько и основных. Однако, из этого ни в коей мере не следует, что нулю равны все основные переменные. Если из общего числа переменных N=n+m будут свободными n переменных, то очевидно, что m переменных будут базисными, т.е. не равны нулю. С учетом введенных терминов можно сказать, что целью решения задачи ЛП является нахождение базисных и свободных переменных.

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

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

Действительно, если x₁= x₂= x₃= x₄ = 0 мы никакой продукции не выпускаем и при этом прибыль F=0. Дополнительные переменные y₁, y₂, y₃, показывающие объем неиспользованных ресурсов, равны, соответственно: 16, 110,100, т.е. тому ресурсу, который имеется в наличии. В самом деле, мы ничего не выпускаем, но не тратим ресурсы. Следовательно, данные в Табл. 5В соответствуют такой вершине ОДР, в которой целевая функция принимает минимальное значение.

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

Поскольку Табл. 4.2 не удовлетворяет данному признаку, то необходимо перейти к другой вершине ОДР. Переход от одной вершины к другой, производится по определенному алгоритму симплекс-метода, который заключается в обмене переменных.

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

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

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

Таким образом, ведущим столбцом будет столбец х₃, а ведущей строкой будет строка y₃. На пересечении ведущего столбца и ведущей строки будет разрешающий элемент. В нашем случае это число 10. Таким образом, ведущей строкой будет строка y₃, обозначим ее через A_r. Ведущим столбцом будет столбец х₄, обозначим его через A_k, и, следовательно, разрешающий элемент A_rk = 10.

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

Элементы любой другой строки j находят из соотношения:

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

После этих преобразований новая симплексная таблица после первой итерации примет вид Таблицы 4.3.

Таблица 4.3

Величина	Свободный	Свободные переменные
	член	х1	х2	х3	х4
Базисные переменные:
?y1	6	0,6	0,4	0	- 0,3
y2	70	4,4	2,6	0	- 2,2
?y3	10	0,4	0,6	1	1,3
Индексная строка (F)	1200	- 12	2	0	26

В Табл. 4.3 в индексной строке только один отрицательный элемент, следовательно, ведущим столбцом будет х₁, а ведущую строку определяем по наименьшему отношению:

Т. о. Ведущей строкой будет y₁, а разрешающим элементом число 0,6.

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

Таблица 4.4

Величина	Свободный	Свободные переменные
	член	х1	х2	х3	х4
Базисные переменные:
х1	10	5/3	2/3	- 1/6	- 1/2
y2	26	-22/3	- 1/3	1/3	0
х3	6	- 2/3	1/3	1/6	3/2
Индексная строка (F)	1320	20	10	10	20

Из этой таблицы видно, что в столбце свободных членов все элементы положительные. Значит решение является допустимым. В строке целевой функции все элементы тоже положительные. Следовательно, это решение оптимальное и максимизирует целевую функцию. При этом оптимальным планом будут следующие величины: х₁^*=10, х₃^*=6 (значит, они - базисные) и х₂^*=х₄^*=0 (т.к. они свободные). При этом целевая функция F=1320.

Вот результат решения задачи. Однако, с помощью симплекс-таблицы можно узнать еще много полезных сведений. Так их этой же таблицы видим, что свободные переменные y₁=y₃=0, а базисная переменная y₂=26. А это значит, что в оптимальном плане резервы трудовых ресурсов и оборудования равны нулю. Иными словами, эти ресурсы используются полностью. Вместе с тем резерв ресурсов сырья y₂=26, что свидетельствует о том, что имеются излишки сырья. Вот какие полезные сведения можно получить из окончательной симплекс-таблицы.

4.6 Решение транспортных задач

В качестве примера приведем решение транспортной задачи ЛП с помощью таблицы. Транспортная таблица состоит из m строк и n столбцов. В правом верхнем углу каждой клетки будем ставить стоимость С_ij перевозки единицы груза из A_i в B_j, а в центр клетки поместим перевозку X_ij.

Таблица 4.1

	ПН	В1	В2	В3	В4	В5	Запасы аi
ПО
A1	13	7	14	7	5	30
A2	11	8	12	6	8	48
A3	6	10	10	8	11	20
A4	14	8	10	10	15	30
Заявки bj	18	27	42	26	15	128

Таблица 4.2

	ПН	В1	В2	В3	В4	В5	Запасы аi
ПО
A1	18 13	12 7	14	7	5	30
A2	11	15 8	33 12	6	8	48
A3	6	10	9 10	11 8	11	20
A4	14	8	10	15 10	15 15	30
Заявки bj	18	27	42	26	15	128

Составим опорный план. Можно применить метод «северо-западного угля». Пусть пункт В₁ подал заявки на 18 единиц груза. Удовлетворим ее из запасов А₁. После этого в нем остается еще 30-18=12 единиц груза. Отдадим их пункту В₂. Но заявка этого пункта еще не удовлетворена. Выделим остаток 27-12 из запасов А₂ и т.д. рассуждая аналогичным образом, составим таблицу 4.3. Полученный план перевозок является опорным, но вряд ли он является оптимальным в смысле стоимости перевозок.

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

Таким образом, задача ЛП на геометрическом языке может быть сформулирована так: среди прямых уровня функции цели ? найти опорную по отношению к ОДР и притом так, чтобы вся область лежала со стороны больших значений ?. Наш план - не оптимальный. Сразу видно, что его можно улучшить, если произвести в нем «циклическую перестановку», уменьшив перевозки в «дорогой» клетке (2.3) со стоимостью 12. но зато, увеличив перевозки в «дешевой» клетке (2.4) со стоимостью 6. чтобы план оставался опорным, мы должны при этом сделать одну из свободных клеток базисной, а одну из базисных - свободной.

Сколько единиц груза можем мы перенести по циклу следующему циклу: (2.4)?(3.4)?(3.3)?(2.3), увеличивая перевозки в нечетных вершинах цикла и уменьшая в четных? Очевидно, не больше 11 единиц (иначе перевозки в клетке (3.4) стали бы отрицательными). Также очевидно, что в результате циклического переноса допустимый план остается допустимым - баланс заявок и запасов не нарушается. Произведем перенос и запишем улучшенный план в таблицу 4.3.

Таблица 4.3

	ПН	В1	В2	В3	В4	В5	Запасы аi
ПО
A1	18 13	12 7	14	7	5	30
A2	11	15 8	33 12	11 6	8	48
A3	6	10	20 10	8	11	20
A4	14	8	10	15 10	15 15	30
Заявки bj	18	27	42	26	15	128

Таблица 4.4

	ПН	В1	В2	В3	В4	В5	Запасы аi
ПО
A1	- 3 13	12 7	14	7	+15 5	30
A2	11	15 8	22 12	11 6	8	48
A3	6	10	20 10	8	11	20
A4	+15 14	8	10	15 10	- 15	30
Заявки bj	18	27	42	26	15	128

Посмотрим, что мы сэкономили. Общая стоимость плана в табл. 4.2 равна:

‡₁=18ґ13+12ґ7+15ґ8+33ґ12+9ґ10+11ґ8+15ґ10+15ґ15=1287.

Общая стоимость плана табл. 4.1 равна:

‡₂=18ґ13+12ґ7+15ґ8+22ґ12+11ґ6+20ґ10+15ґ10+15ґ15=1243.

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

Действительно алгебраическая сумма стоимостей, стоящих в вершинах цикла со знаком «+», если перевозки в этой вершине увеличиваются, и со знаком «-», если уменьшаются (так называемая «цена цикла»). в данном случае равна 6-8+10-12=-4. Значит, при переносе одной величины груза по этому циклу стоимость уменьшается на 4. А мы перенесем 11 единиц. Следовательно, цена цикла 4. 11=44.

Попробуем еще раз улучшить план табл. 4.3 с помощью цикла (табл. 4.4) с ценой: 5-15+14-13=9. Перебрасывая 15 единиц груза, сокращаем стоимость на: 9. 15=135.

5. Практическая робота

5.1 Графическое решение задачи распределения ресурсов

Ресурсы	Продукция	Наличие
	П1	П2
трудовые	1	2	12
материальные	2	3	17
финансовые	3	4	20
выпуск	1	1	-
прибыль	2	3	-
план	x1	x2	-
Целевая функция	а) x1+ x2 max б) прибыль max

Найдем наибольшее значение линейной функции графическим методом.

L = 2 x₁+ 3 x₂

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

x₁+ 2 x₂ 12

2 x₁+ 3 x₂17

3 x₁+ 4 x₂20

Решение:

В первую очередь, найдем область допустимых значений, т.е. точки x₁ и x₂, которые удовлетворяют системе ограничений. По условию задачи x₁  0, x₂  0, т.е. мы рассматриваем только те точки, которые принадлежат первой четверти.

Шаг 1

Рассмотрим неравенство 1 системы ограничений.

x₁ + 2 x₂ ? 12

1) Построим прямую.

Заменим знак неравенства на знак равенства.

x₁ + 2 x₂ = 12

Преобразуем уравнение следующим образом.

x₁+x₂= 12

11/2

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

На оси X₁ рисуем точку с координатой 12. 

На оси X₂ рисуем точку с координатой 6.

Соединяем полученные точки и получаем необходимую прямую.

2) Какие точки нас интересуют?

x₁+ 2 x₂ 12

2 x₂- x₁+ 12

x₂-1/2 x₁+ 6

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

3) Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа.

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

Точки принадлежащие области допустимых значений:

А (0, 0)

В (12, 0)

С (0, 6)

Шаг 2

Рассмотрим неравенство 2 системы ограничений.

2 x₁ + 3 x₂ ? 17

1) Построим прямую.

Заменим знак неравенства на знак равенства.

2 x₁ + 3 x₂ = 17

Преобразуем уравнение следующим образом.

x₁+x₂= 17

1/2 1/3

Каждый член уравнения разделим на 17.

x₁+x₂= 1

17/2 17/3

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

На оси X₁ рисуем точку с координатой 17/2. 

На оси X₂ рисуем точку с координатой 17/3.

Соединяем полученные точки и получаем необходимую прямую.

2) Какие точки нас интересуют?

2x₁+ 3 x₂17

3 x₂-2 x₁+ 17

x₂-2/3 x₁+ 17/3

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

3) Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа.

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

Точки принадлежащие области допустимых значений:

А (0, 0)

В (17/2, 0)

С (0, 17/3)



Шаг 3

Рассмотрим неравенство 3 системы ограничений.

3 x₁ + 4 x₂ ? 20

1) Построим прямую.

Заменим знак неравенства на знак равенства.

3 x₁ + 4 x₂ = 20

Преобразуем уравнение следующим образом.

x₁+x₂= 20

1/3 1/4

Каждый член уравнения разделим на 20.

x₁+x₂= 1

20/35

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

На оси X₁ рисуем точку с координатой 20/3. 

На оси X₂ рисуем точку с координатой 5.

Соединяем полученные точки и получаем необходимую прямую.

2) Какие точки нас интересуют?

3 x₁+ 4 x₂ 20

4 x₂-3 x₁+ 20

x₂-3/4 x₁+ 5

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

3) Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа.

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

Точки принадлежащие области допустимых значений:

А (0, 0)

В (20/3, 0)

С (0, 5)

Шаг 4

Вернемся к нашей исходной функции L.

L = 2 x₁+ 3 x₂

Допустим значение функции L равно 1 (абсолютно произвольно выбранное число), тогда

1 = 2 x₁+ 3 x₂

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

Диапазон перемещения прямой НЕ от точки O до точки N, а именно, в направлении от точки O к точке N.

Будем перемещать прямую, перпендикулярную вектору ON, до тех пор, пока она полностью не пройдет область допустимых решений.

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

Ответ:

Наибольшее значение функции достигает при:

Х1 = 0

Х2 = 5

Значение функции: L = 15

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

Поставщик	Потребитель	Запасы А
	B 1	B 2	B 3	B 4	B 5
A 1	- 10	- 7	- 14	- 8	- 10	40
A 2	- 12	- 8	- 10	- 8	- 10	38
A 3	- 8	- 10	- 10	- 12	- 14	42
A 4	- 16	- 10	- 8	- 12	- 16	30
Заявки В	28	22	25	35	40	150

1) Метод северо-западного угла.

Рассмотрим маршрут доставки от поставщика A₄ к потребителю B₅ (ячейка A₄B₅).

Запасы поставщика A₄ составляют 30 единиц продукции. Потребность потребителя B₅ составляет 30 единиц продукции. (см. таблицу).

От поставщика A₄ к потребителю B₅ будем доставлять 30 единиц продукции.

Разместим в ячейку A₄B₅ значение равное 30.

Мы полностью израсходoвали запасы поставщика A₄. Вычеркиваем строку 4 таблицы, т.е. исключаем ее из дальнейшего рассмотрения.



Поставщик	Потребитель	Запасы А
	B 1	B 2	B 3	B 4	B 5
A 1	28 10	12 7	- 14	- 8	- 10	40
A 2	- 12	10 8	25 10	3 8	- 10	38
A 3	- 8	- 10	- 10	32 12	10 14	42
A 4	- 16	- 10	- 8	- 12	30 16	30
Запасы В	28	22	25	35	40	150

Заполненные нами ячейки будем называть базисными, остальные - свободными.

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

Количество базисных ячеек (задействованных маршрутов) равно 8, что и требовалось.

Мы нашли начальное решение, т.е. израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S₀ = 10 * 28 + 7 * 12 + 8 * 10 + 10 * 25 + 8 * 3 + 12 * 32 + 14 * 10 + 16 * 30 = 1722 ден. ед.

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

2) Метод наименьших стоимостей.

Минимальный элемент матрицы тарифов находится в ячейке A₄B₅ и равен 16, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₄ к потребителю B₅ наиболее рентабельный.

Запасы поставщика A₄ составляют 5 единиц продукции. Потребность потребителя B₅ составляет 5 единиц продукции. (см. таблицу).

От поставщика A₄ к потребителю B₅ будем доставлять 5 единиц продукции.

Разместим в ячейку A₄B₅ значение равное 5

Мы полностью израсходoвали запасы поставщика A₄. Вычеркиваем строку 4 таблицы, т.е. исключаем ее из дальнейшего рассмотрения.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4	B 5
A 1	- 10	22 7	- 14	18 8	- 10	40
A 2	- 12	- 8	- 10	17 8	21 10	38
A 3	28 8	- 10	- 10	- 12	14 14	42
A 4	- 16	- 10	25 8	- 12	5 16	30
Потребность	28	22	25	35	40	150

Заполненные нами ячейки будем называть базисными, остальные - свободными.

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

Количество базисных ячеек (задействованных маршрутов) равно 8, что и требовалось.

Мы нашли начальное решение, т.е. израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S₀ = 7 * 22 + 8 * 18 + 8 * 17 + 10 * 21 + 8 * 28 + 14 * 14 + 8 * 25 + 16 * 5 = 1344 ден. ед.

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

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

1. Мину М. Математическое программирование. Теория и алгоритмы. М. 2004

Орехов Н.А., Левин А.Г., Горбунов Е.А. «Математические методы и модели в экономике». Учебное пособие для вузов / Под ред. проф. Н.А. Орехова - М.: ЮНИТИ-ДАНА, 200

2. Самаров К.Л., Шапкин А.С. «Задачи с решениями по высшей математике и математическим методам в экономике»: Учебное пособие - М.: Издательско-торговая корпорация «Дашков и Ко», 2007

3. Мацнев А.П., Якушин А.А. «Экономико-математические методы и модели». Учебное пособие для студентов. - М: Новый Центр, 2006.

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