Симплекс-метод линейного программирования

Размещено на http://www.allbest.ru/

Симплекс-метод линейного программирования

Размещено на http://www.allbest.ru/

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

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

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

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X₁, X₂, ..., X_r. Тогда наша система уравнений может быть записана как

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

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X₁, X₂, ..., X_r, то решение {b₁, b₂,..., b_r, 0, ..., 0}будет опорным при условии, что b₁, b₂,..., b_r ? 0.

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

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

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

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

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

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

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

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

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

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



Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X₁, X₂, ..., X_r и что при этом b₁, b₂,..., b_r ? 0 (соответствующее базисное решение является опорным).

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

Далее эта система оформляется в виде симплекс-таблиц:



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

Порядок работы с симплекс таблицей

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

Алгоритм перехода к следующей таблице такой:

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

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

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

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

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

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

· в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.

· столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

· строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.

· в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

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

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

Пример 2.4.1

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

(2.16)

Этому способу разбиения переменных на основные и неосновные соответствует базисное решение (k₁ , k₂, ... , k_m , 0, 0, ... , 0). Рассмотрим общий случай, когда это решение является недопустимым. От полученного базисного решения следует сначала перейти к какому-нибудь допустимому базисному решению. Причем не обязательно, чтобы этот переход осуществлялся сразу, за один шаг.

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

Для перехода к новому базисному решению необходимо: выбрать переменную, которую следует перевести из неосновных в основные; установить, какая основная переменная при этом перейдет в число неосновных переменных. При переводе неосновной переменной в основные ее значение, как правило, возрастает: вместо нуля в исходном базисном решении оно будет положительно в новом базисном решении (исключая случай вырождения). Вернемся к i-му уравнению системы (2.16), содержащему отрицательный свободный член k₁. Оно показывает, что значение переменной xi растет при возрастании значений тех неосновных переменных, которые в этом уравнении имеют положительные коэффициенты. Отсюда следует, что в основные можно переводить те неосновные переменные, которые в уравнении системы (2.16) с отрицательным свободным членом имеют положительные коэффициенты.

Здесь может быть три исхода:

1. в i-м уравнении системы (2.16) нет основных переменных с положительными коэффициентами, т. е. все коэффициенты b_{i, m+j} (как и свободный член k_i) отрицательны. В этом случае система ограничений несовместна, она не имеет ни одного допустимого решения, а следовательно, и оптимального;

2. в i-м уравнения имеется одна переменная x_m+j , коэффициент b при которой положителен. В этом случае именно эта переменная переводится в основные;

3. в i-м уравнении имеется несколько переменных с положительными коэффициентами b_{i, m+j} . В этом случае в основные можно перевести любую из них.

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

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

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

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

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

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

Задача

Для изготовления различных изделий A и B используется 2 вида сырья. На производство единицы изделия A его требуется затратить: 1-го вида -15кг, 2-го вида - 11кг, 3-го вида - 9кг. На производство единицы изделия B требуется затратить сырья 1-го вида - 4кг, 2-го вида - 5кг, 3-го вида - 10кг.

Производство обеспечено сырьем 1-го вида в количестве 1095кг, 2-го вида - 865кг, 3-го вида -1080кг.

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

Решение. Составим задачу линейного программирования

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

Приведем к канонической форме

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

Первоначальный опорный план принимает вид X₀ = ( 0, 0, 1095, 865, 1080 )

Для получения оптимального плана составим таблицу

№ итерации	базисные переменные	Сб	С1= ? 3	С2= ? 2	С3= 0	С4= 0	С5= 0	A0	У	ai0/aik
			x1	x2	x3	x4	x5
0	x3	0	15	4	1	0	0	1095	1115	73*
	x4	0	11	5	0	1	0	865	882	78
	x5	0	9	10	0	0	1	1080	1100	120
Дj = Zj -Cj	3**	2	0	0	0
I	x1	? 3	1	0,26	0,06	0	0	73	74,33	27,75
	x4	0	0	2,06	?0,73	1	0	62	64,3	30*
	x5	0	0	7,6	?0,6	0	1	423	431	55
Дj = Zj -Cj	0	0,24**	?0,2	0	0	? 219	? 218
II	x1	? 3	1	0	0,16	? 0,13	0	65	660,32
	x2	? 2	0	1	? 0,35	0,48	0	30	31,13
	x5	0	0	0	2,1	? 3,68	1	195	194,4	*
Дj = Zj -Cj	0	0	0,22**	? 0,58	0	? 255	? 255,35
III	x1	? 3	1	0	0	0,15	? 0,08	50	51,7
	x2	? 2	0	1	0	? 0,14	0,17	63	64,03
	x3	0	0	0	1	? 1,75	0,48	93	92,72
Дj = Zj -Cj	0	0	0	? 0,18	? 0,1	? 276	? 276,29

* разрешающая строка ;** разрешающий столбец

Опорные планы X₁ = ( 73, 0, 0, 62, 423 ), X₂ = ( 65, 30, 0, 0, 195 ) ? не оптимальные.

Опорный план X₃ = (50, 63, 93 ) оптимальный.

при X₀ = ( 0, 0, 1095, 865, 1080 ), Z(X₀) = 0

при X₁ = ( 73, 0, 0, 62, 423 ), Z(X₁) = ? 219

при X₂ = ( 65, 30, 0, 0, 195 ), Z(X₂) = ? 255

при X₃ = (50, 63, 93) , Z(X₃) =Z(X_min) =Z(X^*) = ? 276

Боьшое число экономических задач сводится к линейным математическим моделям. Традиционно оптимизационные линейные математические модели называются моделями линейного програм-мирования. Этот термин появился в конце 30-х годов, когда про-граммирование на компьютере еще не было развито, и соответствует не очень удачному переводу английского "programmation". Под линейным программированием понимается линейное планиде, т. е. получение оптимального плана--решения в задачах с линейной структурой. В данной книге встречаются также термины «нелинейное программирование» и «динамическое программирование», которые аналогичным образом подразумевают получение оптимального решения задач с соответствующей структурой.

Постановка задачи линейного программирования (ЛП)

В общем виде задача линейного программирования ставится следующим образом.

Максимизировать (минимизировать) функцию

(3.1)

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

где x_j, -управляющие переменные или решения задачи
(3.1)-(3.4); b_j, a_ij, - параметры, f - целевая функция или критерий эффективности задачи.

Функция (3.1) - линейная, ограничения (3.2)-(3.4) - линейные. Задача содержит п переменных и т ограничений.

Решить задачу линейного программирования - это значит найти значения управляющих переменных x_j, удовлетворяющих ограничениям (3.2)-(3.4), при которых целевая функция (3.1) принимает минимальное или максимальное значение.

В зависимости от вида целевой функции (3.1) и ограничений
(3.2)-(3.4) можно выделить несколько типов задач линейного программирования или линейных моделей: общая линейная задача, транспортная задача, задача о назначениях.

В этой главе рассматривается общая линейная задача.

Приведем пример экономической задачи, сводящейся к линейной модели.



Задача

Предприятие производит изделия трех видов, поставляет их заказчикам и реализует на рынке. Заказчикам требуется 1000 изделий первого вида. 2000 изделий второго вида и 2500 изделий третьего вида.

Условия спроса на рынке ограничивают число изделий первого вида 2000 единицами, второго - 3000 и третьего - 5000 единицами.

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

Таблица 3.1

Тип ресурсов	Вид изделий	Всего ресурсов
	1	2	3
1 2 3 4	500 1000 150 100	300 200 300 200	1000 100 200 400	25000000 30000000 20000000 40000000
Прибыль	20	40	50

Как организовать производство, чтобы:

1) обеспечить заказчиков;

2) не допустить затоваривания;

3) получить максимальную прибыль?

Построение математической модели 3.1.

Выполним последовательно этапы построения математической модели, сформулированные в пункте 3.

1) Цель - получение максимальной прибыли.

2) Параметрами являются все числовые данные, приведенные в условии задачи.

3) Управляющие переменные:

x₁ - число изделий первого вида;

x₂ - число изделий второго вида;

x₃ - число изделий третьего вида;

4) Ограничения: обеспечить заказчиков, не превысить, запас ресурсов, не допустить затоваривания рынка.

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

(3.5)

Первые три неравенства в системе (3.5) соответствуют спросу заказчиков. Неравенства с четвертого по шестое формализуют спрос на рынке. Последние четыре неравенства соответствуют ограничениям по ресурсам.

5) Целевая функция или критерий эффективности задачи имеет вид

Р = 20х₁ + 40 х₂ + 50 х₃ max. (3.6)

В формуле буквой Р обозначена прибыль. Ее надо максимизировать. Каждое слагаемое определяет прибыль от производства изделий каждого вида соответственно в количествах х₁, х₂, х₃ .

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

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

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

Математическую модель строим по этапам, сформулированным в пункте 1.3.

1) Целью является максимизация прибыли.

2) Задача решается в общем виде, поэтому для определения параметров введем условные обозначения:

n - число различных видов изделий;

m - число различных типов ресурсов;

b_i - запас ресурса i-го типа, ;

a_ij - количество ресурсов i-го типа для изготовления одного изделия j-го вида,

Pj - прибыль от реализации одного изделия j-гo вида.

3) Управляющие переменные x_j, - число изделий j-го вида.

4) Ограничения задачи - это ограничения по ресурсам и условия неотрицательности управляющих переменных.

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

(3.7)

(3.8)

(3.7), (3.8) - линейная математическая модель поставленной задачи. В результате ее расчета определяют оптимальный план производства, т. е. количество изделий каждого вида, которые надо изготовить так, чтобы при этом была максимальна прибыль (3..7) и не был превышен запас ресурсов (3.8)

Формирование минимальной потребительской продовольственной корзины

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

1) Целью является минимизация стоимости потребительской корзины.

2) Параметры задачи:

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

m - число различных питательных веществ, необходимых человеку;

a_ij - содержание i-го питательного вещества в j-м продукте,

b_t - количество i-го питательного вещества, необходимое человеку,

c_j - стоимость единицы j-го продукта,

3) Управляющие переменные x_j, - это количество j-го продукта, входящего в потребительскую корзину,

4) Область допустимых решений определяется следующей системой неравенств, содержащей условия по необходимому уровню потребления каждого питательного вещества во всех продуктах и условия неотрицательности управляющих переменных:

(3.9)

5) Критерий оптимальности С имеет вид

(3.10)

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

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

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

1) Целью является минимизация себестоимости.

2) Параметры:

т - номенклатура, т. е. число различных видов продукции в производственном заказе;

b_i - число единиц продукции i-го вида, ;

п - число единиц оборудования;

T_j - фонд времени работы оборудования j-го типа,

a_ij - производительность оборудования j -го типа по производству изделий i-го вида, ;

c_ij - себестоимость изготовления единицы продукции i-го вида на оборудовании j-го типа,

3) Управляющие переменные x_ij, - это время, в течение которого оборудование j-го типа занято изготовлением продукции i-го вида.

4) Область допустимых решений определяется ограничениями к (3.10) по фонду времени, ограничениями (3.11) по номенклатуре и условиями неотрицательности x_ij

(3.11)

(3.12)

5) Критерий оптимальности задается функцией

(3.13)

где С - суммарная себестоимость.

Система (3.11)-(3.13) - линейная математическая модель задачи. Она содержит m*m неизвестных (управляющих переменных) и т+п ограничений, не считая условий (3.11). После расчета модели определяется оптимальная загрузка оборудования, т. е. время в течение которого оборудование каждого типа занято изготовлением продукции каждого вида.

Раскрой материала

На раскрой (распил) поступает материал нескольких видов в определенном количестве. Из этого материала необходимо изготовить различные изделия. Материал может быть раскроен разными способами

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

Составление математической модели.

1) Цель - минимизация себестоимости раскроя.

2) Параметры:

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

d_j - количество материала j-го вида,

m - число различных видов изделий, которые надо изготовить;

b_j - число изделий i-го вида,

l - число различных способов раскроя;

a_ijk - число изделий i-го вида, которое можно получить из единицы материала j-го вида при k-м способе раскроя;

c_jk - себестоимость раскроя единицы материала j-го вида k-м способом;

3) Управляющие переменные x_jk - количество единиц материала j-го вида, раскраиваемых k-м способом;

4) Область допустимых решений определяется ограничениями по количеству исходного материала (3.13), ограничениями по выпуску (3.14) и условиями неотрицательности управляющих переменных.

(3.14)

5) Критерий оптимальности задается функцией

(3.15)

(3.14)-(3.15) - линейная математическая модель поставленной задачи. Она содержит ml неизвестных (управляющих переменных) и п+т ограничений, не считая условий неотрицательности переменных X_jk. После расчета модели определяется количество материала каждого вида, раскраиваемого различными способами.

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

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

1. В чем заключаются особенность задач ЛП?

2. Что такое ограничения?

3. Какого вида бывают целевая функция?

4. Что такое область допустимых решений?

5. Может ли у задачи ЛП не быть решения?

Графический метод решения задачи линейного программирования

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

Пример 3.1

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

Прибыль от реализации одной единицы товара первого вида составляет 2 усл. ед., второго вида - 3 усл. ед.

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

Таблица 3.2

Ресурсы	Норма затрат ресурсов на товары	Общее количество ресурсов
	1 -го вида	2-го вида
1 2 3 4	2 1 4 0	2 2 0 4	12 8 16 12



Решение

Это задача составления плана реализации товара при n=2, m=4.

Математическая модель имеет вид

(3.16)

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

Графическое решение.

Построим в плоскости X₁OX₂ область допустимых решений. Каждое неравенство системы (3.3.2) определяет в плоскости X₁OX₂ полуплоскость, лежащую выше или ниже прямой, определяемой соответствующим уравнением. Построим прямые (см. рис. 3.1)

Рассмотрим точку с координатами х₁ =0; х₂ =0. Подставив их в первое неравенство, получаем 0 ? 12 - верно, следовательно, искомая полуплоскость лежит ниже прямой 2x₁ +2x₂ = 12; остальные полуплоскости находятся аналогичным образом.

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

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

Построим две линии уровня (рис. 3.1):

2x₁ + 3x₂ = 6;

2x₁ +3х₂=13.

Функция Р возрастает в направлении вектора-нормали = (2,3) следовательно, минимум находится в точке (0.0). Максимум определяем, передвигая нашу линию уровня в направлении вектора параллельно самой себе до тех пор, пока хотя бы одна ее точка будет принадлежать области допустимых решений.

В данном случае это точка: х₁ = 4, х₂ = 2;

при этом P=2*4+3*2=14.

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

Рис. 3.1. Графический метод решения задачи ЛП

Изложенный выше графический метод применим для решения задач линейного программирования следующего вида:

(3.17)

(3.18)



Алгоритм решения ЗЛП графическим методом.

1) Записывают уравнения прямых, соответствующих ограничениям (3.3.4), и строят их на плоскости x₁ox_3.

2) Определяют области, в которых выполняются ограничения задачи. Для этого выбирают произвольную точку на плоскости х₁ох₂ и подставляют ее координаты в первую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны от прямой, что и точка; в противном случае искомая полуплоскость лежит с противоположной стороны от прямой. Эти действия последовательно выполняются для всех неравенств (3.3.4).

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

4) Определяют направление возрастания (убывания) целевой функции f. Это можно сделать двумя способами. Можно построить вектор-нормаль , его направление показывает направление возрастания функции f, и противоположном направлении функция убывает. Можно просто построить две линии уровня функции f = K₁; f = K₂; (K₁, K₂ - произвольные константы, K₁ K₂), и по их расположению определить направление возрастания (убывания) функции.

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

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

Возможны следующие варианты областей допустимых решений (рис. 3.2):



Рис. 3.2. Варианты областей. а - область допустимых решений
- замкнутое множество (многоугольник); б - область допустимых решений - открытое множество; в - область допустимых решений - пустое множество (система ограничений (3.18) несовместна);
г - область допустимых решений состоит из единственной точки А

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

3.3. Основная задача линейного программирования (ОЗЛП)

В произвольной форме линейная математическая модель или задача линейного программирования имеет вид (3.1)-(3.4).

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

Для применения симплекс-метода задачу следует записать в канонической форме:

(3.19)

(3.20)

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

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

1) Если требуется найти минимум f, то заменяя f на -f переходят к задаче максимизации, так как min(f)= -max(-f).

2) Если ограничение содержит неравенство со знаком , то от него переходят к равенству, добавляя в левую часть ограничения дополнительную неотрицательную переменную.

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

4) Если в задаче какая-либо из переменных произвольна, то от нее избавляются, заменяя ее разностью двух других неотрицательных переменных. Например, для произвольной переменной x_k, x_k = x'_k-x”_k, где x'_kx”_k ? 0, x”_k ? 0.

Пример 3.2

Записать в канонической форме задачу

Решение.

f₁= - f= - 5x₁ - 2x₂ +3x₃

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

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

Произвольную переменную x₃ заменяем разностью двух неотрицательных переменных x₃ = x₆ - x₇

Окончательно получаем каноническую форму записи

Задача (3.19)-(3.20) называется основной задачей линейного программирования (ОЗЛП).

ОЗЛП не всегда имеет решение.

Во-первых, уравнения (3.20) могут оказаться несовместными.

Во-вторых, уравнения (3.20) могут оказаться совместными не в области неотрицательных решений.

В третьих, допустимые решения (3.10), (3.20) существуют, но среди них нет оптимального: функция f не ограничена в области допустимых решений.

Предположим, что все уравнения (3.20) линейно независимы, т. е. выражают независимые друг от друга условия задачи. Если это не так, то лишние уравнения надо просто исключить. Задачу (3.19)-(3.20) имеет смысл решать, когда число уравнений в системе ограничений (3.20) меньше числа входящих в них неизвестных: т < п. В противном случае, если т = п,то система (3.4.2) имеет единственное решение, и задача максимизации функции (3.19) не имеет смысла; если т > п, то система (3.20) переопределена и в общем случае не имеет решений.

Если т < п, то система (3.4.2) имеет бесконечное множество решений и среди них можно выбрать оптимальное, доставляющее максимум функции (3.19).

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

1. В чем особенность задачи ОЗЛП?

2. Как привести задачу ЛП к каноническому виду?

3. Может ли в области допустимых решений быть одна точка?

Симплекс-метод

Симплекс-метод является методом направленного перебора решений системы (3.20). Каждое следующее решение улучшает значение целевой функции. Симплекс-метод включает два этапа:

1) Определение начального решения, удовлетворяющего ограничениям (3.20).

2) Последовательное улучшение начального решения и получение оптимального решения задачи (3.19)-(3.20).

Любое решение задачи линейного программирования называется опорным планом задачи.

Система (3.20) содержит т линейно независимых уравнений, и их число меньше числа неизвестных, входящих в систему, следовательно, систему (3.20) можно разрешить относительно т неизвестных, например x₁,x₂,…x_m, выразив их через остальные неизвестные

Коэффициенты a_ij,b_i, , в полученной системе, естественно, отличны от коэффициентов системы (3.20), но для простоты обозначены той же буквой.

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

После указанных преобразований задача (3.19)-(3.20) записывается в следующем виде:

(3.21)

(3.22)

Алгоритм решения системы (3.21)-(3.22) симплекс-методом

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

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

Остальные п - т переменных называют свободными.

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

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

Х_о ={x₁= b₁,х₂=b₂,...,х_т = b_m,x_m+l = 0,...,х_n = 0}.

Если все b_i 0, то начальное решение является допустимым. Переходят к шагу 3. В противном случае используют алгоритм нахождения начального решения.

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



Значения коэффициентов c_j, , естественно, отличны от значений коэффициентов в формуле (3.21), но для простоты обозначены той же буквой.)

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

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

Составляется симплекс-таблица (табл. 3.3). В левой колонке симплекс-таблицы находятся базисные переменные, в колонке свободных членов - правые части соответствующих ограничений. В i-й строке,
j-м столбце стоит коэффициент при j-й переменной в i-м ограничении (3.22), , . В последней строке (f - строке) стоит коэффициент с противоположным знаком при j-ой переменной в целевой функции f.
В последнем столбце стоят значения свободных членов, входящего в ограничения.

Таблица 3.3

Базисные переменные	Коэффициенты при переменных	Свободные члены
	x1	x2	…	xm	…	xp	…	xn
x1 x2 … xq … xm	a11 a21 … aq1 … am1	a11 a22 … aq2 … am2	…… ... … … … …	a1m a2m … aqm … aAmn	…… ... … … … …	a1p a2p … aqp … amp	…… ... … … … …	a1n a2n … aqn … amn	b1 b2 … bq … bm
-f	-c1	-c2		-cm		-cp		-cn	0

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

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

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

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

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

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

...