Симплекс-метод решения злп. Симплекс-метод, примеры решения задач

Шаг 0. Подготовительный этап.

Приводим задачу ЛП к специальной форме (15).

Шаг 1. Составляем симплекс-таблицу , соответствующую специальной форме:

Заметим, что этой таблице соответствует допустимое базисное решение
задачи (15). Значение целевой функции на этом решении

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

Если среди элементов индексной строки симплекс – таблицы
нет ни одного положительного элемента то
, оптимальное решение задачи ЛП найдено:. Алгоритм завершает работу.

Шаг 3. Проверка на неразрешимость

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

Шаг 4. Выбор ведущего столбца q

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

Шаг 5. Выбор ведущей строки p

Среди положительных элементов столбца
находим элемент
, для которого выполняется равенство

.

Строку p объявляем ведущей (разрешающей). Элемент
объявляем ведущим (разрешающим).

Шаг 6. Преобразование симплексной таблицы

Составляем новую симплекс-таблицу, в которой:

а) вместо базисной переменной записываем, вместо небазисной пере меннойзаписываем;

б) ведущий элемент заменяем обратной величиной
;

в) все элементы ведущего столбца (кроме
) умножаем на
;

г) все элементы ведущей строки (кроме
) умножаем на;

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

Из элемента вычитается произведение трех сомножителей:

первый – соответствующий элемент ведущего столбца;

второй – соответствующий элемент ведущей строки;

третий – обратная величина ведущего элемента
.

Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».

Шаг 7. Переход к следующей итерации осуществляется возвратом к шагу 2.

2.3. Алгоритм симплекс-метода для задачи на максимум

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

На шаге 2:
:

На шаге 3
. Целевая функция является неограниченной сверху на допустимом множестве.

На шаге 4 :
.

2.4. Пример решения задачи симплекс-методом

Решить задачу, записанную в виде (15).

Составим симплексную таблицу:

Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение не является оптимальным. Значение целевой функции для этого базисаL=0.

Выбираем ведущий столбец – это столбец, соответствующий переменной .

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

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

Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальная. Базисное решение, соответствующее таблице, имеет вид . Значение целевой функции на этом базисеL= -2 .

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

Еще одна итерация завершена. Переходим к новой итерации.

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

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

Для решения ЗЛП симплекс-методом ее приводят к каноническому виду, т.е. из ограничений – неравенств надо сделать ограничения – равенства. Для этого в каждое ограничение вводится дополнительная неотрицательная балансовая переменная со знаком «+», если знак неравенства «£», и со знаком «–», ели знак неравенства «³».

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

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

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

1. Составляем первый опорный план

Задача остается прежней. Приведем стандартную форму системы неравенств (1) в каноническую форму системы уравнений путем введения дополнительных балансовых переменных x 3 , x 4 , x 5 , x 6 .

или

В экономическом смысле значения дополнительных переменных x 3 , x 4 , x 5 определяют остатки сырья после реализации продукции.

Матрица полученной системы уравнений имеет вид:

Видно, что в матрице A базисным минором 4-го порядка является определитель, составленный из единичных коэффициентов при дополнительных переменных x 3 , x 4 , x 5 , x 6 , так как он отличен от нуля и равен 1. Это означает, что векторы-столбцы при этих переменных является линейно независимыми, т.е. образуют базис , а соответствующие им переменные x 3 , x 4 , x 5 , x 6 являются базисными (основными). Переменные x 1 , x 2 будут называться свободными (неосновными).

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

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

Количество базисных решений и соответствующее ему число групп базисных переменных может быть не более, чем , где n –общее число переменных, r – число базисных переменных, r ≤ m ≤ n .

Для нашей задачи r = 4; n = 6. Тогда , т.е. возможны 15 групп из 4-х базисных переменных (или 15 базисных решений).

Разрешим систему уравнений относительно базисных переменных x 3 , x 4 , x 5 , x 6:

Полагая, что свободные переменные x 1 = 0, x 2 = 0, получим значения базисных переменных: x 3 = 312; x 4 = 15; x 5 = 24; x 6 = –10, т.е. базисное решение будет = (0; 0; 312; 15; 24; –10).

Данное базисное решение является недопустимым , т.к. x 6 = –10 ≤ 0, а по условию ограничений x 6 ≥ 0. Поэтому вместо переменной x 6 в качестве базисной надо взять другую переменную из числа свободных x 1 или x 2 .

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

Таблица 1

F –строка называется индексной . Она заполняется коэффициентами целевой функции, взятыми с противоположными знаками, так как уравнение функции можно представить в виде F = 0 – (– 4x 1 – 3x 2).

В столбце свободных членов b i есть отрицательный элемент b 4 = –10, т.е. решение системы является недопустимым. Чтобы получить допустимое решение (опорный план), элемент b 4 надо сделать неотрицательным.

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

Делим свободные члены b i на соответствующие элементы a is разрешающего столбца, получаем оценочные отношения Θ i = = {24, 15, 12, 10}. Из них выбираем наименьшее положительное (minΘ i =10), которое будет соответствовать разрешающей строке . Разрешающая строка определяет переменную x j , которая на следующем шаге выступает из базиса и станет свободной. Поэтому x 6 -строка является разрешающей строкой, а элемент «–1» – разрешающим элементом . Обводим его кружком. Переменные x 1 и x 6 меняются местами.

Оценочные отношения Θ i в каждой строке определяются по правилам:

1) Θ i = , если b i и a is имеют разные знаки;

2) Θ i = ∞, если b i = 0 и a is < 0;

3) Θ i = ∞, если a is = 0;

4) Θ i = 0, если b i = 0 и a is > 0;

5) Θ i = , если b i и a is имеют одинаковые знаки.

Совершаем шаг модифицированного жорданова исключения (ШМЖИ) с разрешающим элементом и составляем новую таблицу (табл. 2) по следующему правилу:

1) на месте разрешающего элемента (РЭ) устанавливается величина, ему обратная, т.е. ;

2) элементы разрешающей строки делятся на РЭ;

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

4) остальные элементы находятся по правилу прямоугольника:

Из табл. 2 видно, что свободные члены в b i -столбце являются неотрицательными, следовательно, получено первоначальное допустимое решение – первый опорный план = (10; 0; 182; 5; 4; 0). При этом значение функции F () = 40. Геометрически это соответствует вершине F (10; 0) многоугольника решений (рис. 1).

Таблица 2

2. Проверяем план на оптимальность. Опорный план не оптимальный, так как в F -строке имеется отрицательный коэффициент «–4». Улучшаем план.

3. Нахождение нового опорного плана

Выбираем разрешающий элемент по правилу:

Выбираем наименьший отрицательный коэффициент в F -строке «–4», который и определяет разрешающий столбец – x 6 ; переменную x 6 переводим в базисные;

Находим отношения Θ i , среди них выбираем наименьшее положительное, которое соответствует разрешающей строке:

min Θ i = min {14, 5, 2, ∞} = 2, следовательно, x 5 -строка – разрешающая, переменную x 5 переводим в свободные (переменные x 5 и x 6 меняются местами).

На пересечении разрешающих строки и столбца стоит разрешающий элемент «2»;

Выполняем шаг ШМЖИ, строим табл. 3 по вышеприведенному правилу и получаем новый опорный план = (12; 0; 156; 3; 0; 2).

Таблица 3

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

Опорный план также не является оптимальным, так как в F -строке имеется отрицательный коэффициент «–1». Значение функции F () = 48, что геометрически соответствует вершине E (12; 0) многоугольника решений (рис. 1). Улучшаем план.

5. Нахождение нового опорного плана

x 2 -столбец – разрешающий, так как в F -строке наименьший отрицательный коэффициент «–1» находится в x 2 -столбце (Δ 2 = –1). Находим наименьшее Θ i : min Θ i = min {≈ 9, 6, ∞, 24} = 6, следовательно, x 4 -строка – разрешающая. Разрешающий элемент «1/2». Меняем местами переменные x 2 и x 4 . Выполняем шаг ШМЖИ, строим табл. 4, получаем новый опорный план = (9; 6; 51; 0; 0; 5).

6. Проверка опорного плана на оптимальность

В F -строке все коэффициенты неотрицательны, следовательно, опорный план является оптимальным. Геометрически соответствует точке D (9;6) (см. рис. 1). Оптимальный план дает максимальное значение целевой функции у.е.

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

Назначение сервиса . Сервис предназначен для онлайн решения задач линейного программирования (ЗЛП) симплекс-методом в следующих формах записи:

• в виде симплексной таблицы (метод жордановых преобразований); базовой форме записи;
• модифицированным симплекс-методом ; в столбцовой форме; в строчечной форме.

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel .

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 1 2 3 4 5 6 7 8 9 10

При этом ограничения типа x i ≥ 0 не учитывайте. Если в задании для некоторых x i отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом . При решении автоматически определяется использование М-метода (симплекс-метод с искусственным базисом) и двухэтапного симплекс-метода .

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП
Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных
Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях)	Доход G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Алгоритм симплекс-метода включает следующие этапы:

1. Составление первого опорного плана . Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
2. Проверка плана на оптимальность . Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
3. Определение ведущих столбца и строки . Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.
4. Построение нового опорного плана . Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса .

Если необходимо найти экстремум целевой функции, то речь идет о поиске минимального значения (F(x) → min , см. пример решения минимизации функции) и максимального значения ((F(x) → max , см. пример решения максимизации функции)

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

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

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

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

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

Замечание 2. Пусть в некоторой крайней точке все симплексные разности неотрицательные D k ³ 0 (k = 1..n+m),т.е. получено оптимальное решение и существует такой А k - небазисный вектор, у которого D k = 0. Тогда максимум достигается по крайней мере в двух точках, т.е. имеет место альтернативный оптимум. Если ввести в базис эту переменную x k , значение целевой функции не изменится.

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

Замечание 4. При решении задачи минимизации в базис вводится вектор с наибольшей положительной симплексной разностью. Далее применяется тот же алгоритм, что и для задачи максимизации.

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

Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑a ji b j , умножив обе части неравенства на -1. Введем m дополнительных переменных x n+j ≥0(j =1,m ) и преобразуем ограничения к виду равенств

(2)

Предположим, что все исходные переменные задачи x 1 , x 2 ,..., x n – небазисные. Тогда дополнительные переменные будут базисными, и частное решение системы ограничений имеет вид

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)

Так как при этом значение функции цели F 0 = 0 , можно представить F(x) следующим образом:

F(x)=∑c i x i +F 0 =0 (4)

Начальная симплекс-таблица (симплекс-табл. 1) составляется на основании уравнений (2) и (4). Если перед дополнительными переменными x n+j стоит знак «+», как в (2), то все коэффициенты перед переменными x i и свободный член b j заносятся в симплекс-таблицу без изменения. Коэффициенты функции цели при ее максимизации заносятся в нижнюю строку симплекс-таблицы с противоположными знаками. Свободные члены в симплекс-таблице определяют решение задачи.

Алгоритм решения задачи следующий:

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

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

Таблица 1.

x n

базисные переменные	Свободные члены в ограничениях	Небазисные переменные
		x 1	x 2	...	x l	...
x n+1	b 1	a 11	a 12	...	a 1l	...	a 1n
x n+2	b 2	a 21	a 22	...	a 2l	...	a 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+r	b2	a r1	a r2	...	a rl	...	a rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+m	b m	a m1	a m2	...	a ml	...	a mn
F(x) max	F 0	-c 1	-c 2	...	-c 1	...	-c n

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

Одновременно из БП исключается та переменная, которая первой изменит знак при увеличении выбранной НП x l . Это будет x n+r , индекс r которой определяется из условия

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

Строка, соответствующая переменной x n+r , называется ведущей, или разрешающей. Элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим, или разрешающим элементом. Нахождением ведущего элемента заканчивается работа с каждой очередной симплекс-таблицей.

3-й шаг. Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов симплекс-таблицы предыдущего шага и помечаются штрихом, т.е. b" j , a" ji , c" i , F" 0 . Пересчет элементов производится по следующим формулам:

Сначала в новой симплекс-таблице заполнятся строка и столбец, которые в предыдущей симплекс-таблице были ведущими. Выражение (5) означает, что элемент a" rl на месте ведущего равен обратной величине элемента предыдущей симплекс-таблицы. Элементы строки a ri делятся на ведущий элемент, а элементы столбца a jl также делятся на ведущий элемент, но берутся с противоположным знаком. Элементы b" r и c" l рассчитываются по тому же принципу.

Остальные формулы легко записать с помощью .

Прямоугольник строится по старой симплекс-таблице таким образом, что одну из его диагоналей образует пересчитываемый (a ji) и ведущий (a rl) элементы (рис. 1). Вторая диагональ определяется однозначно. Для нахождения нового элемента a" ji из элемента a ji вычитается (на это указывает знак « – » у клетки) произведение элементов противоположной диагонали, деленное на ведущий элемент. Аналогично пересчитываются элементы b" j , (j≠r) и c" i , (i≠l).

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

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

Рис. 1. Правило прямоугольника

Если среди коэффициентов F-строки имеются отрицательные (за исключением свободного члена), то нужно переходить к другому базисному решению. При максимизации функции цели в базис включается та из небазисных переменных (например x l), столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента c l в нижней строке симплекс-таблицы. Это позволяет выбрать ту переменную, увеличение которой приводит к улучшению функции цели. Столбец, соответствующий переменной x l , называется ведущим. Одновременно из базиса исключается та переменная x n+r , индекс r которой определяется минимальным симплексным отношением:

Строка, соответствующая x n+r , называется ведущей , а элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим элементом.

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

Если в процессе оптимизации решения в ведущем столбце все элементы неположительные, то ведущую строку выбрать невозможно. В этом случае функция в области допустимых решений задачи не ограничена сверху и F max ->&∞.

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

Пример 1. Решить задачу

max{F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0}

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

Графическая интерпретация решения задачи представлена на рис. 2. Максимальное значение функции цели достигается в вершине ОДЗП с координатами . Решим задачу с помощью симплекс-таблиц. Умножим второе ограничение на (-1) и введём дополнительные переменные, чтобы неравенства привести к виду равенств, тогда

Исходные переменные x 1 и x 2 принимаем в качестве небазисных, а дополнительные x 3 , x 4 и x 5 считаем базисными и составляем симплекс-таблицу(симплекс-табл. 2). Решение, соответствующее симплекс-табл. 2, не является допустимым; ведущий элемент обведен контуром и выбран в соответствии с шагом 2 приведенного ранее алгоритма. Следующая симплекс-табл. 3 определяет допустимое базисное решение, ему соответствует вершина ОДЗП на рис. 2 Ведущий элемент обведен контуром и выбран в соответствии с 5-м шагом алгоритма решения задачи. Табл. 4 соответствует оптимальному решению задачи, следовательно: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.

Рис. 2. Графическое решение задачи

Рассмотрен пример решения задачи симплекс методом, а также пример решения двойственной задачи.

Условие задачи

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

Решение задачи симплекс методом

Пусть x 1 , x 2 , x 3 - количество реализованных товаров, в тыс. руб., 1, 2, 3 - ей групп, соответственно. Тогда математическая модель задачи имеет вид:

F = 4·x 1 + 5·x 2 + 4·x 3 ->max

0}}}{~}" title="delim{lbrace}{matrix{4}{1}{{2x_1 + 3x_2 + 6x_3= 0}}}{~}">

Решаем симплекс методом.

Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.

В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.

Данные заносим в симплекс таблицу

Симплекс таблица № 1

Целевая функция:

0 · 240 + 0 · 200 + 0 · 160 = 0

Вычисляем оценки по формуле:

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Вводим переменную x 2 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 2 .

= 26.667

Наименьшее неотрицательное: Q 3 = 26.667. Выводим переменную x 6 из базиса

3-ю строку делим на 6.
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 2

Целевая функция:

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Поскольку есть отрицательная оценка Δ 1 = - 2/3, то план не оптимален.

Вводим переменную x 1 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 1 .

Наименьшее неотрицательное: Q 3 = 40. Выводим переменную x 2 из базиса

3-ю строку делим на 2/3.
Из 2-й строки вычитаем 3-ю строку, умноженную на 8/3

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 3

Целевая функция:

0 · 160 + 0 · 40 + 4 · 40 = 160

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Поскольку отрицательных оценок нет, то план оптимален.

Решение задачи:

Ответ

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.

Решение двойственной задачи

Двойственная задача имеет вид:

Z = 240·y 1 + 200·y 2 + 160·y 3 ->min

Title="delim{lbrace}{matrix{4}{1}{{2y_1 + 4y_2 + 4y_3>=4} {3y_1 + 2y_2 + 6y_3>=5} {6y_1 + 4y_2 + 8y_3>=4} {y_1, y_2, y_3>= 0}}}{~}">

Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.

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

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;