Симплекс-метод решения ЗЛП

Краткая теория
Примеры решения задач

Краткая теория

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

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

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

- умение находить начальный опорный план;

- наличие признака оптимальности опорного плана;

- умение переходить к нехудшему опорному плану.

Построение начального опорного плана

Рассмотрим три случая.

1-й случай. Пусть в системе ограничений имеется единичный неотрицательный базис. Например, она имеет вид:

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

2-й случай. Пусть система ограничений имеет вид:

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

Получим систему ограничений

эквивалентную исходной и имеющую предпочтительный вид. Отсюда получаем начальный опорный план:

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю:

3-й случай. Пусть система ограничений имеет вид:

Перейдем к каноническому виду путем введения дополнительных переменных :

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

где в целевой функции знак "-" относится к задаче максимизации. Если некоторые из уравнений исходной системы ограничений имеют предпочтительный вид, то в них не вводят искусственные переменные. Начальный опорный план M-задачи имеет вид:

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

Симплексные таблицы

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

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

Заносим условия задачи в симплексную таблицу:

БП									Симплексные отношения
БП			18	20	32	0	0	0	Симплексные отношения
	0	720	18	15	12	1	0	0	720/12=60
	0	384	6	4	8	0	1	0	384/8=48
	0	360	5	3	3	0	0	1	360/3=120
		0	-18	-20	-32	0	0	0

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

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

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

Признак оптимальности опорного плана задачи максимизации.

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

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

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

Столбец называют разрешающим (ключевым) . Если задача решается на минимум, то разрешающий столбец выбирается из условия:

Ключевая строка определяется по минимуму соотношений свободных членов и членов ключевого столбца (симплексных отношений):

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент

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

Для контроля вычислений элементов индексной строки применяются формулы:

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

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

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

Смежные темы решебника:

Заказать решение задач, узнать цену help100task@yandex.ru, или шлите свои условия сюда: - на 100task.ru делать работы удобнее, надежнее, аккуратнее, быстрее, безопаснее и дешевле чем в агенствах и на биржах.
Или подписаться на телеграм-канал, чтобы не потерять контакты:

Примеры решения задач

Пример 1

Скачать пример 1 в формате pdf

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

Решение

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

Заполняем симплексную таблицу 0-й итерации.

БП									Симплексные отношения
БП			18	20	32	0	0	0	Симплексные отношения
	0	720	18	15	12	1	0	0	60
	0	384	6	4	8	0	1	0	48
	0	360	5	3	3	0	0	1	120
		0	-18	-20	-32	0	0	0

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

Переход к следующей итерации осуществляем следующим образом:

Ключевой столбец соответствует .

Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 8

Теперь приступаем к составлению 1-й итерации. Вместо единичного вектора вводим вектор .

Переходим к таблице 1-й итерации.

БП									Симплексные отношения
БП			18	20	32	0	0	0	Симплексные отношения
	0	144	9	9	0	1	-3/2	0	16
	32	48	3/4	1/2	1	0	1/8	0	96
	0	216	11/4	3/2	0	0	-3/8	1	144
		1536	6	-4	0	0	4	0

Ключевой столбец соответствует .

Находим ключевую строку, для этого определяем:

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 9

Вектор выводим из базиса и вводим вектор .

Переходим к таблице 2-й итерации.

БП									Симплексные отношения
БП			18	20	32	0	0	0	Симплексные отношения
	20	16	1	1	0	1/9	-1/6	0
	32	40	1/4	0	1	-1/18	5/24	0
	0	192	5/4	0	0	-1/6	-1/8	1
		1600	10	0	0	4/9	10/3	0

В индексной строке все члены неотрицательные.

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

; ; ; ; ; ;

Ответ:

Пример 2

Скачать пример 2 в формате pdf

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве , , , единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве единиц, ресурса второго вида в количестве единиц, ресурса третьего вида в количестве единиц. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве , единиц, ресурсов второго вида в количестве , единиц, ресурсов третьего вида в количестве , единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно , , тыс. руб.

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

Решение

Через обозначим товарооборот 1-го, 2-го и третьего вида товаров соответственно.

Тогда целевая функция, выражающая получаемую прибыль:

Ограничения по материально-денежным ресурсам:

Кроме того, по смыслу задачи

Получаем следующую задачу линейного программирования:

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

Заполняем симплексную таблицу 0-й итерации.

БП									Симплексные отношения
БП			8	6	4	0	0	0	Симплексные отношения
	0	520	16	18	9	1	0	0	65/2
	0	140	7	7	2	0	1	0	20
	0	810	9	2	1	0	0	1	90
		0	-8	-6	-4	0	0	0

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

Переход к следующей итерации осуществляем следующим образом:

Ведущий столбец соответствует .

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е.7.

Теперь приступаем к составлению 1-й итерации. Вместо единичного вектора вводим вектор .

Получаем таблицу 1-й итерации:

БП									Симплексные отношения
БП			8	6	4	0	0	0	Симплексные отношения
	0	200	0	2	31/7	1	-16/7	0	1400/31
	8	20	1	1	2/7	0	1/7	0	70
	0	630	0	-7	-11/7	0	-9/7	1	—
		160	0	2	-12/7	0	8/7	0

Ключевой столбец для 1-й итерации соответствует .

Находим ключевую строку, для этого определяем:

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 31/7.

Вектор выводим из базиса и вводим вектор .

Получаем таблицу 2-й итерации:

БП									Симплексные отношения
БП			8	6	4	0	0	0	Симплексные отношения
	4	1400/31	0	14/31	1	7/31	-16/31	0
	8	220/31	1	27/31	0	-2/31	9/31	0
	0	21730/31	0	-195/31	0	11/31	-65/31	1
		7360/31	0	86/31	0	12/31	8/31	0

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

Таким образом, необходимо продавать 7,1 тыс.р. товара 1-го вида и 45,2 тыс.р. товара 3-го вида. Товар 2-го вида продавать невыгодно. При этом прибыль будет максимальна и составит 237,4 тыс.р. При реализации оптимального плана остаток ресурса 3-го вида составит 701 ед.

Запишем модель двойственной задачи.

Транспонируем матрицу исходной задачи:

Получаем:

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

Соответствие между переменными исходной и двойственной задачи:


\|	\|	\|	\|	\|	\|

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

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

Пример 3

Скачать пример 3 в формате pdf

В опытном хозяйстве установлено, что откорм КРС выгоден только тогда, когда каждое животное получает в суточном рационе не менее 20 кг. к. ед., не менее 2000 г белка и не менее 100 г кальция. Для кормления животных используется сено, силос и концентраты. Содержание указанных питательных веществ в 1 кг корма каждого вида, а также себестоимость 1 кг корма приведены в таблице. Возможности хозяйства позволяют включать в суточный рацион не более 20 кг сена. Составить кормовой рацион минимальной стоимости, учитывающий минимальные суточные нормы потребления питательных веществ и возможности хозяйства по ресурсам.

Виды кормов	Содержание в 1 кг			Себестоимость 1 кг, ден.ед.
Виды кормов	Кормовых единиц	Белка, г	Кальция, г	Себестоимость 1 кг, ден.ед.
Сено	0,5	40	5	2
Силос	0,2	10	4	1
Концентраты	1,0	200	3	4

Решение

Через , и обозначим количество кормов – сена, силоса и концентратов соответственно.

Тогда ограничения на содержание веществ:

Кроме того, по смыслу задачи , ,

Целевая функция, выражающая себестоимость кормов:

Получаем следующую задачу линейного программирования:

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

Ограничение имеет предпочтительный вид, если при неотрицательности правой части левая часть имеет переменную, входящую с коэффициентом, равным единице, а остальные ограничения-равенства - с коэффициентом, равным нулю. В нашем случае 1-e, 2-e, 3-e ограничения не имеют предпочтительного вида, поэтому вводим для них искусственные переменные , , . В целевую функцию искусственные переменные введем с коэффициентом М, где М - большое положительное число. Получили М-задачу, которая всегда имеет предпочтительный вид.

Заполняем симплексную таблицу 0-й итерации.

БП												Симплексные отношения
БП			2	1	4	0	0	0	M	M	M	Симплексные отношения
	M	20	0,5	0,2	1	-1	0	0	1	0	0	20
	M	2000	40	10	200	0	-1	0	0	1	0	10
	M	100	5	4	3	0	0	-1	0	0	1	33,333
		0	-2	-1	-4	0	0	0	0	0	0
		2120M	45,5M	14,2M	204M	-M	-M	-M	0	0	0

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

Переход к следующей итерации осуществляем следующим образом:

Ключевой столбец соответствует .

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 200

Теперь приступаем к составлению 1-й итерации. Вместо единичного вектора вводим вектор .

Переходим к таблице 1-й итерации.

БП												Симплексные отношения
БП			2	1	4	0	0	0	M	M	M	Симплексные отношения
	M	10	0,3	0,15	0	-1	0,005	0	1	-	0	33,333
	4	10	0,2	0,05	1	0	-0,005	0	0	-	0	50
	M	70	4,4	3,85	0	0	0,015	-1	0	-	1	15,909
		40	-1,2	-0,8	0	0	-0,02	0	0	-	0
		80M	4,7M	4M	0	-M	0,02M	-M	0	-	0

Ключевой столбец соответствует .

Находим ключевую строку, для этого определяем:

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 4,4

Вектор выводим из базиса и вводим вектор .

Переходим к таблице 2-й итерации.

БП												Симплексные отношения
БП			2	1	4	0	0	0	M	M	M	Симплексные отношения
	M	5,227	0	-0,113	0	-1	0,004	0,068	1	-	-	76,868
	4	6,818	0	-0,125	1	0	-0,006	0,045	0	-	-	151,511
	2	15,909	1	0,875	0	0	0,003	-0,227	0	-	-	-
		59,091	0	0,25	0	0	-0,016	-0,273	0	-	-
		5,227M	0	-0,113M	0	-M	0,004M	0,068M	0	-	-

Ключевой столбец соответствует .

Находим ключевую строку, для этого определяем:

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 0,068

Вектор выводим из базиса и вводим вектор .

Переходим к таблице 3-й итерации.

БП												Симплексные отношения
БП			2	1	4	0	0	0	M	M	M	Симплексные отношения
	0	76,868	0	-1,662	0	-14,706	0,059	1	-	-	-
	4	3,359	0	-0,05	1	0,662	-0,009	0	-	-	-
	2	33,358	1	0,498	0	-3,338	0,016	0	-	-	-
		80,076	0	-0,204	0	-4,015	0,0	0	-	-	-

В индексной строке все члены неположительные.

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

; ; ; ; ; ;

Таким образом, для кормления необходимо 33,3 кг сена и 3,3 кг концентратов. При этом себестоимость корма будет минимальна и составит 80 ден.ед.

Краткая теория
Примеры решения задач