Понятие о симплексном методе

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

Рассмотрим линейнуюоптимизационную модель с системой ограничений в канонической форме записи:

(2.1)

, i = , (2.2)

, j = . (2.3)

Из теоремы: «Линейная функция, определенная на выпуклом n‑мерном многограннике, достигает наибольшего значения в вершине этого многогранника. Если линейная функция достигает наибольшего значения более чем в одной вершине, то она достигает такого же значения в любой точке, являющейся выпуклой линейной комбинацией этих вершин» следует, что оптимальный план задачи (2.1)-(2.3) является одним из опорных решений системы (2.2). Это опорное решение, применяя симплекс-метод, мы и ищем, переходя от одного опорного решения к другому, при условии, что значение функции (2.1) возрастает (не убывает).

Суть метода: предположим, что в системе (2.2) m < n и все m уравнений линейно независимы: r = m < n. Тогда система (2.2) имеет бесконечное множество решений. Разрешаем систему (2.2) относительно базисных неизвестных (m < n):

, j = , (2.4)

и подставляя значения (2.4) в целевую функцию (2.1), получим:

, (2.5)

, (2.6)

. (2.7)

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

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

Опорный план соответствует базису . Если значение не оптимальное, то преобразовывают базис Б в новый базис Б , удаляя из Б одну переменную и вводя вместо нее другую из свободных неизвестных, так чтобы , где – опорный план в новом базисе Б . Преобразовывая один базис в другой, переходят от одного опорного плана к другому, и так как число опорных планов не более , то через конечное число шагов, либо приходят к базису , в котором достигает оптимума и тогда – оптимальный, либо устанавливают, что задача (2.1) - (2.3) неразрешима.

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

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

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

1) ограничения заданы в виде равенств;

2) правые части (системы ограничений) (2.2) неотрицательны, т. е. ;

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

Например, в системе ограничений:

,

,

.

первое и второе ограничения имеют предпочтительный вид, третье – нет.

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

Как же приводится система ограничений к предпочтительному виду?

1) Если система ограничений имеет вид:

, , ,

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

,

имеет предпочтительный вид. Начальный опорный план имеет вид:

= .

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

2) Если система ограничений имеет вид:

, , ,

то вычитая из левых частей неотрицательные дополнительные переменные , , получим расширенную задачу, эквивалентную данной. Полученная система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть с коэффициентами «–1». План недопустим. Поэтому вводят искусственный базис. К левым частям системы ограничений - равенств, не имеющих предпочтительного вида, добавляют искусственные переменные . В целевую функцию вводят с коэффициентом, равным (+М) в случае решения задачи на минимум, и с коэффициентом равным (–М) на максимум, где М – большое положительное число. Полученная задача называется М-задачей, она имеет предпочтительный вид и стратегически эквивалентна исходной.

3) Если исходная линейнаяоптимизационная модели имеет вид:

(2.8)

, , ; (2.9)

, j = ,

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

; (2.10)

, ; (2.11)

, j = , , ; (2.12)

где знак «–» в (2.10) относится к модели на максимум. Начальный опорный план М‑задачи, которая имеет предпочтительный вид, запишется:

.

Если в оптимальном плане М ‑ модели: все искусственные переменные равны нулю, то план

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

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

; (2.13)

, , ; (2.14)

, j = . (2.15)

Разрешая систему (2.14) относительно базисных переменных , подставляем в (2.13), получим (2.5). Из (2.5)-(2.7) можно выяснить признак оптимальности опорного плана. Из (2.14) находим начальный опорный план , а из (2.13) значение целевой функции:

, где .

Так как , j = , то при целевая функция достигает минимального значения в точке . Если же , то в целевая функция достигает max: . Это видно из равенства .

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

Таблица 2.1

БП		СП
… …
		… …
…	…	. . .
		… …
…	…	. . .
		… …
=		… …

, , , ;

или

, , .

Признак оптимальности опорного плана

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

, , ;

, j = .

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

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

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

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

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

Затем -тое уравнение разрешаем относительно :

(2.16)

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

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

(2.17)

Обозначив , i = 0, 1, 2, …, m, i ≠ k; j = 0, 1, …, n – m, j ≠ s,

получим следующую систему равенств:

. (2.18)

Приведение системы

, , ,

к новому базису называется симплексным преобразованием. В результате получим симплексную таблицу 2.2:

Таблица 2.2

БП		СП
… …
		… …
…	…	. . .
		… …
…	…	. . .
		… …
=		… …

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

, .

Сформулируем правила перехода к новому опорному плану:

1) выбираем разрешающий элемент , стоящий на пересечении разрешающей строки и разрешающего столбца;

2) разрешающий элемент заменяем обратной величиной ;

3) остальные элементы разрешающей строки делим на разрешающий элемент : , ;

4) остальные элементы разрешающего столбца делим на разрешающий элемент и меняем знаки;

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

.

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

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

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

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

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

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

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

Пример 2.1. Предприятие может изготовлять четыре вида продукции П , П₂, П , П . Сбыт любого ее объема обеспечен. Предприятие располагает в течение квартала трудовыми ресурсами в 100 чел, полуфабрикатами массой 260кг, станочным оборудованием в 370 станко-смен. Нормы ресурсов и прибыль от единицы каждого вида продукции представлены в таблице 2.3:

Таблица 2.3

Ресурсы	Продукция	Объем ресурсов
П	П	П	П
Трудовые ресурсы, чел.	2,5	2,5		1,5
Полуфабрикаты, кг
Станочное оборудование, станко-смен
Прибыль от единицы продукции, руб.					max

Необходимо:

1) определить план выпуска продукции, максимизирующий прибыль;

2) решить задачу с требованием комплектации, чтобы количество единиц третьей продукции было в 3 раза больше количества единиц первой;

3) выяснить оптимальный ассортимент при дополнительных ограничениях: первого продукта выпускать не менее 25 единиц, третьего – не более 30, второго и четвертого – в отношении 1 : 3.

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

.

План удовлетворяет ограничениям:

а) на трудовые ресурсы:

;

на полуфабрикаты:

;

на станочное оборудование:

;

условия неотрицательности:

, j = ;

б) дополнительное условие комплектации:

;

в) дополнительные условия:

.

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

В расширенной задаче система ограничений

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

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

Таблица 2.4

БП	А	СП
		2,5	2,5		1,5
Функция		-40	-50	-100	-80

Рассчитаем элементы индексной строки:

– произведение вектора коэффициентов целевой функции, стоящих у базисных переменных = (0, 0, 0) и вектора свободных членов у системы ограничений в предпочтительном виде А = (100, 260, 370).

Так как - строка содержит 4 отрицательных элемента, то в базис будем вводить переменную , которая соответствует наименьшему значению , : = - 100. Разрешающим столбцом будет третий столбец.

Для определения переменной, подлежащей исключению из базиса, составляем отношения свободных членов к положительным элементам разрешающего столбца. В разрешающем столбце все элементы положительные: 100/2 =50; 260/4 = 65; 370/4 = 92,5. Выбираем наименьшее, которое определяет первую строку в качестве разрешающей.

Таким образом, разрешающим элементом будет «2». Строим новую симплексную таблицу 2.5:

Таблица 2.5

БП		СП
		1,25	1,25	1/2	0,75
		-1		-2
				-2
-строка					-5

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

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

500/0,75 = 66; 60/3 = 20; 170/70 = 24.

Так как отношение 60/3 = 20 – наименьшее, то третья строка разрешающая. Разрешающий элемент «3». Строим новую симплексную таблицу 2.6:

Таблица 2.6

Б. П.	А	СП
-строка		250/3	250/3	140/3	5/3

Так как в - строке нет отрицательных элементов, то план

Х* = (0, 0, 35, 20, 0, 0, 30)

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

(Х*) = 5100,

так как в - строке нет нулевых элементов.

Лекция 3 Экономико-математические методы и модели оптимального планирования в промышленности, АПК (продолжение)

Вопросы, изучаемые на лекции:

3.1. Понятие двойственности. Построение двойственных моделей оптимального планирования в промышленности, АПК

3.2. Соответствие между переменными пары взаимно двойственных линейных оптимизационных моделей

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

Понятие двойственности. Построение двойственных моделей оптимального планирования в промышленности, АПК

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

Рассмотрим линейную оптимизационную модель в канонической форме записи: найти план , при котором целевая функция

, (3.1)

и который удовлетворяет ограничениям:

, (3.2)

.

Двойственная модель формулируется следующим образом: найти план , при котором целевая функция

, (3.3)

и который удовлетворяет ограничениям:

. (3.4)

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

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

, (3.5)

и который удовлетворяет ограничениям:

, (3.6)

.

Двойственная задача формулируется следующим образом: найти план , при котором целевая функция

, (3.7)

и который удовлетворяет ограничениям:

, (3.8)

.

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

Установим связи между двойственными моделями:

1) упорядочим запись исходной модели: в задаче на максимум ограничения-неравенства должны иметь смысл ≤, в задаче на минимум − ≥.

2) если в прямой модели определяется максимум целевой функции, то в двойственной – минимум, и наоборот;

3) свободные члены ограничений прямой модели служат коэффициентами целевой функции двойственной модели, а коэффициенты целевой функции прямой модели служат свободными членами ограничений двойственной модели;

4) матрицей коэффициентов ограничений двойственной модели служит матрица, полученная транспонированием матрицы коэффициентов ограничений исходной модели;

5) каждому ограничению-неравенству прямой модели соответствует неотрицательная переменная двойственной модели, а каждому ограничению-равенству – переменная произвольного знака.

6) каждой неотрицательной переменной прямой модели соответствует ограничение-неравенство двойственной, а каждой произвольной переменной – ограничение-равенство.

Пример 3.1. Пусть предприятие выпускает n видов продукции и использует при этом m различных видов ресурсов, объем которых ограничен величинами , ,…, . Пусть известны нормы расхода i-го ресурса при производстве единицы j-го вида продукции – . Известна также выручка от реализации единицы j-го вида продукции – . Требуется найти план , при котором выручка была бы максимальной.

Тогда двойственная задача формулируется следующим образом:

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