Задача линейного программирования в общем виде.

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

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

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

(34.1)

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

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

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

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

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

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

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

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

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

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

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

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

(34.2)

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

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

(34.3)

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

Таблица 34.1

базис	св. члены			…
Z				…
				…
				…
…	…	…	…	…	…
				…

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

Шаг 1.

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

(35.1)

Шаг 2:

Строим вспомогательную задачу ЛП

(35.2)

.

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

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

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

(35.3)

Шаг 3:

Решаем вспомогательную задачу ЛП симплекс-методом.

Шаг 4:

Если , то допустимого решения в исходной задаче не существует. Задача не разрешима и процесс решения исходной задачи завершается.

Шаг 5:

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

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

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

Итак, у нас получилась вспомогательная задача ЛП:

Исходная симплекс-таблица примет тогда вид:

базис	св. члены
	35	3	3	8
	10	1	2	1
	15	1	2	3
	20	2	1	5

Дальнейшие итерации приводятся без особых пояснений.

Первая итерация

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

базис	св. члены
	35	3	3	8
	10	1	2	1
	15	1	2	3
	20	2	1	5

базис	св. члены
	3	-1/5	7/5	-8/5
	6	3/5	9/5	-1/5
	3	-1/5	7/5	-3/5
	4	2/5	1/5	1/5

Вторая итерация

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

базис	св. члены
	3	-1/5	7/5
	6	3/5	9/5
	3	-1/5	7/5
	4	2/5	1/5

 

базис	св. члены
	0	0	-1
	15/7	6/7	-9/7
	15/7	-1/7	5/7
	25/7	15/7	-1/7

Третья итерация

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

базис	св. члены
	-90/7	-30/7
	15/7	6/7
	15/7	-1/7
	25/7	15/7

Строка целевой функции не содержит положительных значений.

Значит, задача решена и оптимальный план имеет вид: (0, 15/7, 25/7, 15/7)

Двойственность задач линейного программирования. Таблица соответствий.

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

Таблица 36.1

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

 

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

Рассмотрим пару задач ЛП вида:

Таблица 36.2

Прямая задача (I)	Двойственная ей задача (II)
……………………… ……… - любое …….. - любое	……… - любое …….. - любое ……………………………..

 

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

Грубо говоря, двойственная задача - это на 90⁰ повернутая исходная прямая задача. В этой связи полезно усвоить следующую схему соответствия.

Задача 36.1: построить двойственную задачу к следующей задаче ЛП:

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

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

 

Таблица 36.3

Прямая задача (I)	Двойственная ей задача (II)
- любое - любое	- любое

Итак, задача слева - исходная прямая задача, задача справа - двойственная к исходной задаче.

 

 

Теоремы двойственности.

Рассмотрим стандартную задачу ЛП и двойственную к ней:

Таблица 37.1

Прямая задача (I)	Двойственная ей задача (II)
……………………… ………	……… ……………………………..

Пара двойственных задач (I) и (II) называется парой симметрических двойственных задач.

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

Рассмотрим пару симметрических двойственных задач в матричной форме записи.

Таблица 37.2.

Прямая задача (I)	Двойственная ей задача (II)

Здесь , , , ,

- матрица из строк и столбцов, - транспонированная матрица. Введем обозначения для допустимых областей задачи (I) и (II).

,

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

Следствие (достаточное условие оптимальности): если для некоторых допустимых решений и выполняется равенство значений целевых функций , то , - оптимальные решения задачи (I) и (II) соответственно.

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

, (37.1)

где , оптимальные планы задач (I) и (II) соответственно.

Вторая теорема двойственности: чтобы допустимые решения , пары двойственных задач (I) и (II) были оптимальными необходимо и достаточно, чтобы выполнялись условия:

1) , (37.2)

2) . (37.3)

 

Критерии оптимальности.

Первый критерий оптимальности: Решение оптимально тогда и только тогда, когда существует решение такое, что

. (38.1)

Второй критерий оптимальности: чтобы допустимые решения , - пары двойственных задач (I) и (II) были оптимальны, необходимо и достаточно, чтобы выполнялись соотношения:

1) если , то ; (38.2)

2) если , то ; (38.3)

3) если , то ; (38.4)

4) если , то . (38.5)

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

, (38.6)

, , .

Пусть решение задачи найдено одним из стандартных методов: , .

Построим двойственную задачу:

, (38.7)

, , .

По первой теореме двойственности задача разрешима, причем

.

Найдем оптимальный план задачи , используя вторую теорему двойственности. Подставим координаты вектора в ограничения задачи (38.6).

Получим

Следовательно, неравенство должно выполняться как равенство, то есть .

Далее, так как , , то

, .

Получаем систему линейных уравнений:

, ,

Планы и , в силу второй теоремы двойственности, являются оптимальными в задачах (38.6) и (38.7) соответственно.

Рис. 41.1

OABC — область допустимых решений (ОДР). Оптимальное решение задача имеет в точке B (9/5,41/15) при этом максимальное значение целевой функции составляет 218/15 ед. Полученное оптимальное решение не целочисленное. Условию целочисленности переменных удовлетворяют координаты 12 точек, принадлежащих ОДР. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник OABC многоугольником OKEMNF, содержащим все допустимые точки с целочисленными координатами.

Строим вектор . Линию уровня перемещаем по направлению ,

получим в точке E (1, 3) максимальное значение целевой функции

(ед.)

Ответ: Фирме следует приобрести один комплект оборудования 1-го вида и три комплекта оборудования 2-го вида, что обеспечит ей при имеющихся ограничениях на производственные площади и денежные средства максимальное увеличение выпуска продукции, равное 14 ед. в смену.

Метод ветвей и границ.

 

Пусть (43.1)

, , (43.2)

, - целые, . (43.3)

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

Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи.

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

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

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

1. либо меньше или равно ближайшему меньшему целому числу ;

2. либо больше или равно ближайшему большему целому числу .

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

(43.4)

, , (43.5)

(43.6)

, - целые, . (43.7)

и

(43.8)

, , (43.9)

(43.10)

, - целые, . (43.11)

Возможны четыре случая при решении этой пары задач:

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

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

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

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

Алгоритм метода ветвей и границ:

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

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

3. Находим решение двух задач с ограничениями на компоненту.

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

 

Задача линейного программирования в общем виде.

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

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

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