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

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

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

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel . При этом ограничения типа 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 вида было израсходовано полностью», то соответствующее условие представляет собой равенство.

Аналитическое введение в симплекс-метод

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

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

Например, пусть дана система

Здесь число уравнений равно 2, а неизвестных - 3, уравнений меньше. Выразим x 1 и x 2 через x 3:

Это общее решение системы. если переменной x 3 придавать произвольные числовые значения, то будем находить частные решения системы. Например, x 3 =1 → x 1 =1 → x 2 =6. Имеем (1, 6, 1) - частное решение. Пусть x 3 =2 → x 1 =-3, x 2 = 1, (-3, 1, 2) - другое частное решение. Таких частных решений бесконечно много.

Переменные x 1 и x 2 называются базисными , а переменная x 3 - не базисная, свободная .

Совокупность переменных x 1 и x 2 образует базис: Б (x 1 , x 2). Если x 3 = 0, то полученное частное решение (5, 11, 0) называется базисным решением, соответствующим базису Б (x 1 , x 2).

Базисным называется решение, соответствующее нулевым значениям свободных переменных .
В качестве базисных можно было взять и другие переменные: (x 1 , x 3) или (x 2 , x 3).
Как переходить от одного базиса Б (x 1 , x 2) к другому базису Б (x 1 , x 3)?
Для этого надо переменную x 3 перевести в базисные, а x 2 - в небазисные т. е. в уравнениях надо x 3 выразить через x 2 и подставить в 1-е:

Б (x 1 , x 3 ), таково: (-19/5; 0; 11/5).

Если теперь от базиса Б (x 1 , x 3) нам захочется перейти к базису Б (x 2 , x 3), то

Базисное решение, соответствующее базису Б (x 2 , x 3): (0;19/4; 7/8).
Из трех найденных базисных решений решение, соответствующее базису Б (x 1 , x 3) - отрицательное x 1 < 0, нас в ЗЛП интересуют только неотрицательные решения.

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

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

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

Функцию F = x 2 - x 1 → min необходимо минимизировать при заданной системе ограничений:
-2x 1 + x 2 + x 3 = 2
x 1 + x 2 + x 5 = 5
x 1 - 2x 2 + x 4 = 12
x i ≥ 0, i = 1, 5

Эти ограничения могут рассматриваться как произошедшие из неравенств, а переменные x 3 , x 5 , x 4 - как дополнительные.
Запишем ограничения, выбрав базис из переменных Б { x 3 , x 4 , x 5 }:

Этому базису соответствует базисное неотрицательное решение
x 1 = 0, x 2 = 0, x 3 = 2, x 4 = 2, x 5 = 5 или (0, 0, 2, 2, 5).
Теперь нужно выразить F через небазисные переменные, в нашем случае это уже сделано: F = x 2 - x 1 .
Проверим, достигла ли функция F своего минимального значения. Для этого базисного решения F = 0 - 0 = 0 - значение функции равно 0. Но его можно уменьшить, если x 1 будет возрастать, т. к. коэффициент в функции при x 1 отрицателен. Однако при увеличении x 1 значения переменных x 4 , x 5 уменьшаются (смотрите второе и третье равенство системы ограничений). Переменная x 1 не может быть увеличена больше чем до 2, иначе x 4 станет отрицательной (ввиду равенства 2), и не больше, чем до 5, иначе x 5 - отрицателен. Итак, из анализа равенств следует, что переменную x 1 можно увеличить до 2, при этом значение функции уменьшится.
Перейдем к новому базису Б 2 , введя переменную x 1 в базис вместо x 4 .
Б 2 {x 1 , x 3 , x 5 }.
Выразим эти базисные переменные через небазисные. Для этого сначала выразим x 1 из второго уравнения и подставим в остальные, в том числе и в функцию.

Базисное решение, соответствующее базису Б 3 {х 1 , х 2 , х 3 }, выписывается (4, 1, 9, 0, 0), и функция принимает значение F = -3. Заметим, что значение F уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.
Посмотрев на вид целевой функции , заметим, что улучшить, т. е. уменьшить значение F нельзя и только при x 4 = 0, x 5 = 0 значение F = -3. как только x 4 , x 5 станут положительными, значение F только увеличится, т. к. коэффициенты при x 4 , x 5 положительны. Значит, функция F достигла своего оптимального значения F * = -3. Итак, наименьшее значение F , равное -3, достигается при x 1 * = 4, x 2 * = 1, x 3 * = 9, x 4 * = 0, x 5 * = 0.

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

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

рубашка 1

рубашка 2

рубашка 3

Запасы

нитки (м.)

1

9

3

96

пуговицы (шт.)

20

10

30

640

ткань (

1

2

2

44

Прибыль (р.)

2

5

4

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

Построение модели

Через и количество рубашек 1-го, 2-го и 3-го вида, предназначенных к выпуску.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разрешающим элементов является число 4/3. Вектор выводим из базиса и вводим вместо него вектор . Получаем таблицу 2-й итерации.

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

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

Разрешающим элементов является число 10/3. Вектор выводим из базиса и вводим вместо него вектор . Получаем таблицу 3-й итерации.

№

БП

c Б

A o

x 1

x 2

x 3

x 4

x 5

x 6

Симплексные

2

5

4

0

0

0

отношения

0

x 4

0

96

1

9

3

1

0

0

32/3

x 5

0

640

20

10

30

0

1

0

64

x 6

0

44

1

2

2

0

0

1

22

F j - c j

0

-2

-5

-4

0

0

0

1

x 2

5

32/3

1/9

1

1/3

1/9

0

0

32

x 5

0

1600/3

170/9

0

80/3

-10/9

1

0

20

x 6

0

68/3

7/9

0

4/3

-2/9

0

1

17

F j - c j

160/3

-13/9

0

-7/3

5/9

0

0

2

x 2

5

5

-1/12

1

0

1/6

0

-1/4

--

x 5

0

80

10/3

0

0

10/3

1

-20

24

x 3

4

17

7/12

0

1

-1/6

0

3/4

204/7

F j - c j

93

-1/12

0

0

1/6

0

7/4

3

x 2

5

7

0

1

0

1/4

1/40

-3/4

x 1

2

24

1

0

0

1

3/10

-6

x 3

4

3

0

0

1

-3/4

-7/40

17/4

F j - c j

95

0

0

0

1/4

1/40

5/4

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

Необходимо шить 24 рубашки 1-го вида, 7 рубашек 2-го вида и 3 рубашки 3-го вида. При этом получаемая прибыль будет максимальна и составит 95 руб.

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

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

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

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

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

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

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

Задача.

Для изготовления изделий А и В склад может отпустить сырья не более 80 единиц. Причем на изготовление изделия А расходуется две единицы, а изделия В - одна единица сырья. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий А требуется изготовить не более 50 шт., а изделий В - не более 40 шт. Причем, прибыль от реализации одного изделия А - 5 руб., а от В - 3 руб.

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

x 1 ≤50
x 2 ≤40
2x 1 +x 2 ≤80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →max

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

x 1 +x 3 =50
x 2 +x 4 =40
2x 1 +x 2 +x 5 =80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →max
-F = -5x 1 - 3x 2 → min.

Эта задача имеет специальный вид (с базисом, правые части неотрицательны). Ее можно решить симплекс-методом.

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

Таблица 3.4

базисные			свободные

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

Данной таблице 3.4 соответствует следующий опорный план:

(х 1 , х 2 , х 3 , х 4 , х 5) = (0, 0, 50, 40, 80).

Свободные переменные х 1 , х 2 равны 0; х 1 = 0, х 2 = 0. А базисные переменные х 3 , х 4 , х 5 принимают значения х 3 = 50, х 4 = 40, х 5 = 80 - из столбца свободных членов. Значение целевой функции:

-F = - 5х 1 - 3х 2 = -5 · 0 - 3 · 0 = 0.

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

Возможны различные ситуации.

1. В индексной F -строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятому с противоположным знаком. Переходим к IV этапу.

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

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

III этап . Улучшение опорного плана.

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

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

В нашем примере, элемент 2 - разрешающий. Строка, соответствующая этому элементу, тоже называется разрешающей (табл. 3.5).

Таблица 3.5

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

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

Таблица 3.6

2. На месте разрешающего элемента 2 записываем обратное ему число ½.

3. Элементы разрешающей строки делим на разрешающий элемент.

4. Элементы разрешающего столбца делим на разрешающий элемент и записываем с противоположным знаком.

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

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

Итак, . Записываем 10 на место, где было 50. Аналогично:
, , , .

Таблица 3.7

Имеем новую таблицу 3.7, базисными переменными теперь являются переменные {x 3 ,x 4 ,x 1 }. Значение целевой функции стало равно -200, т.е. уменьшилось. Чтобы проверить данное базисное решение на оптимальность надо перейти опять ко II этапу. Процесс, очевидно, конечен, критерием остановки являются пункт 1 и 2 II этапа.

Доведем решение задачи до конца. Для этого проверим индексную строку и, увидев в ней отрицательный элемент -½, назовем соответствующий ему столбец разрешающим и, согласно III этапу, пересчитаем таблицу. Составив отношения и выбрав среди них минимальное = 40, определили разрешающий элемент 1. теперь пересчет осуществляем согласно правилам 2-5.

Таблица 3.8

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

IV этап . Выписывание оптимального решения.

Если симплекс-метод остановился согласно пункту 1 II этапа, то решение задачи выписывается следующим образом. Базисные переменные принимают значения столбца свободных членов соответственно. В нашем примере х 3 = 30, х 2 = 40, х 1 = 20. Свободные переменные равны 0, х 5 = 0, х 4 = 0. Целевая функция принимает значение последнего элемента столбца свободных членов с противоположным знаком: -F = -220 → F = 220, в нашем примере функция исследовалась на min, и первоначально F → max, поэтому фактически знак поменялся дважды. Итак, х * = (20, 40, 30, 0, 0), F * = 220. Ответ к задаче:

Необходимо в план выпуска включить 20 изделий типа А , 40 изделий типа В, при этом прибыль будет максимальной и будет равна 220 руб.

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

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

Пример . Решить следующую задачу ЛП в канонической форме симплекс-методом.
f(x)=x 1 +9x 2 +5x 3 +3x 4 +4x 5 +14x 6 → min
x 1 +x 4 =20
x 2 +x 5 =50
x 3 +x 6 =30
x 4 +x 5 +x 6 =60
x i ≥ 0, i = 1,…,6
Говорят, что задача ЛП имеет каноническую форму, если все ограничения (кроме условий неотрицательности переменных) имеют вид равенств, а все свободные члены неотрицательны. Так что мы имеем задачу в канонической форме.
Идея симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число "шагов" мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).
Таким образом, идея симплекс-метода основывается на трех свойствах задачи ЛП.
Решение. Чтобы найти начальное допустимое базисное решение, т.е. чтобы определить базисные переменные, систему (5.6) нужно привести к "диагональному" виду. Применяя метод Гаусса (метод последовательного исключения неизвестных), получаем из (5.6):
x 2 +x 1 +x 3 =40
x 4 +x 1 =20
x 5 -x 1 -x 3 =10
x 6 +x 3 =30
Следовательно, базисными являются переменные x 2 , x 4 , x 5 , x 6 , им придаем значения, равные свободным членам соответствующих строк: x 2 =40, x 4 =20, x 5 =10, x 6 =30, . Переменные x 1 и x 3 являются небазисными: x 1 =0, x 3 =0 .
Построим начальное допустимое базисное решение
x 0 = (0,40,0,20,10,30) (5.9)
Для проверки на оптимальность найденного решения x 0 нужно из целевой функции исключить базисные переменные (с помощью системы (5.8)) и построить специальную симплекс таблицу.
После исключения переменных целевую функцию удобно записать в виде:
f(x) = -7x 1 – 14x 3 +880 (5.10)
Теперь при помощи (5.8) –(5.10) составляем начальную симплекс-таблицу:

В нулевую строчку записаны коэффициенты с обратным знаком соответствующих переменных при целевой функции. Критерий оптимальности (для задачи на поиск минимума): допустимое базисное решение(x 0 ) оптимально, если в нулевой строчке нет ни одного строго положительного числа (не считая значения целевой функции (880)). Это правило распространяется и на следующие итерации (таблицы). Элементы нулевой строки будем называть оценками столбцов.
Так что начальное допустимое базисное решение (5.9) неоптимально: 7>0, 14>0 .
В нулевом столбике записаны значения базисных переменных. Они обязательно должны быть неотрицательными (см. уравнение (5.7)). От первой по четвертую строки написаны коэффициенты переменных из системы (5.8).
Так как x 0 неоптимально, то надо перейти к другой вершине многогранника допустимых решений (построить новое д.б.р.). Для этого нужно найти ведущий элемент и провести определенное преобразование (симплексное преобразование).
Сначала находим ведущий элемент таблицы, который стоит в пересечении ведущего столбика (столбец с наибольшей положительной оценкой) и ведущей строки (строки, соответствующей минимальному соотношению элементов нулевого столбика к соответствующим элементам (строго положительным) ведущего столбика).
В таблице 1 ведущий столбик - третий столбик, и ведущая строка - четвертая строка (min{40/1,30/1}=30/1) обозначены стрелками, а ведущий элемент - кружочком. Ведущий элемент показывает, что базисную переменную x 6 нужно заменить на небазисную x 3 . Тогда новыми базисными переменными будут x 2 , x 3 , x 4 , x 5 , , а небазисными -x 1 , x 6 , . Это и означает переход к новой вершине многогранника допустимых решений. Чтобы найти значения координат нового допустимого базисного решения x 00 нужно строить новую симплекс-таблицу и провести в ней элементарные преобразования:
а) все элементы ведущей строки поделить на ведущий элемент, превратив этим самым ведущий элемент в 1 (для простоты выкладок);
б) с помощью ведущего элемента (равного 1) все элементы ведущего столбика превратить в нули (аналогично методу исключения неизвестных);
В результате в нулевом столбце получены значения новых базисных переменных x 2 , x 3 , x 4 , x 5 , (см. таблицу 2) - базисные компоненты новой вершины x 00 (небазисные компоненты x 1 =0, x 6 =0, ).

Как показывает таблица 2, новое базисное решение x 00 =(0,10,30,20,40,0) неоптимально (в нулевой строке есть неотрицательная оценка 7). Поэтому с ведущим элементом 1 (см. таблицу 2) строим новую симплекс-таблицу, т.е. строим новое допустимое базисное решение

Таблице 3 соответствует допустимое базисное решение x 000 =(10,0,30,10,50,0) и оно оптимально, т.к. в нулевой строчке нет положительных оценок. Поэтому f(x 000)=390 есть минимальное значение целевой функции.
Ответ: x 000 =(10, 0, 30, 10, 50, 0) - точка минимума, f(x 000)=390 .

Условно стандартная задача линейного программирования

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

1. Найти оптимальный план прямой задачи:
   а) графическим методом ;
   б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
2. Построить двойственную задачу .
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план двойственной задачи по первой теореме двойственности , используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).
6. Найти оптимальное целочисленное решение:
   а) графическим методом ;
   б) Методом Гомори .
   Сравнить значения функций целочисленного и нецелочисленного решений

Вопросы для самоконтроля

1. Как строится симплекс-таблица?
2. Как отражается смена базиса в таблице?
3. Сформулируйте критерий остановки симплекс-метода.
4. Как организовать пересчет таблицы?
5. С какой строки удобно начинать пересчет таблицы?

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

Содержание

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

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве 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;

Y 1 = 0; y 2 = 0; y 3 = 1; Z min = 160;

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

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

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

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

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

при условиях

Здесь и – заданные постоянные числа

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

при условиях

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

Положим Так как векторы – единичные, то и а

Теорема 5

(признак оптимальности опорного плана). Опорный план задачи (22) – (24) является оптимальным, если для любого j

Теорема 6.

Если для некоторого j=k и среди чисел нет положительных , то целевая функция (22) задачи (22) – (24) не ограничена на множестве ее планов.

Теорема 7.

Если опорный план Х задачи (22) – (24)невырожден и , но среди чисел есть положительные (не все ), то существует опорный план X" такой, что

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

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

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

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

В табл. 3 первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора – значение

Значение Z j находится как скалярное произведение вектора на вектор

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

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

1) для j=m+1, (при ). Поэтому в данном случае числа для всех j от 1 до n ;

2) для некоторого j , и все соответствующие этому индексу величины

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

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

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

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

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

(25)

а коэффициенты разложения векторов через векторы нового базиса, соответствующего новому опорному плану, – по формулам

(26)

После вычисления и согласно формулам (25) и (26) их значения заносят в табл. 4. Элементы -й строки этой таблицы могут быть вычислены либо по формулам

(27)

(28)

либо на основании их определения.

Таблица 3

i

Базис

С б

P 0

c 1

c 2

...

c r

...

c m

c m+1

...

c k

...

c n

P 1

P 2

...

P r

...

P m

P m+1

...

P k

...

P n

1

P 1

c 1

b 1

1

0

...

0

...

0

a 1m+1

...

a 1k

...

a 1n

2

P 2

c 2

b 2

0

1

...

0

...

0

a 2m+1

...

a 2k

...

a 2n

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

r

P r

c r

b r

0

0

...

1

...

0

a rm+2

...

a rk

...

a rn

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

m

P m

c m

b m

0

0

...

0

...

1

a mm+1

...

a mk

...

a mn

m+1

F m

0

0

...

0

...

0

Δ m+1

...

Δ k

...

Δ n

Таблица 4

i

Баз ис

С б

P 0

c 1

c 2

...

c r

...

c m

c m+1

...

c k

...

c n

P 1

P 2

...

P r

...

P m

P m+1

...

P k

...

P n

1

P 1

c 1

b 1

1

0

...

a " 1r

...

0

a " 1m+1

...

0

...

a " 1n

2

P 2

c 2

b 2

0

1

...

a " 2r

...

0

a " 2m+1

...

0

...

a " 2n

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

r

P r

c r

b r

0

0

...

a " rr

...

0

a " rm+2

...

1

...

a " rn

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

m

P m

c m

b m

0

0

...

a " mr

...

1

a " mm+1

...

0

...

a " mn

m+1

F m

0

0

...

z " r -c r

...

0

z " m+1 -c m+1

...

0

...

z " n -c n

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

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

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

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

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

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

1) число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;

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

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

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

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

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

Итак, нахождение оптимального плана симплексным методом включает следующие этапы:

1. Находят опорный план.

2. Составляют симплекс-таблицу.

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

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

5. По формулам (25) – (28) определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов Pj по векторам нового базиса и числа , . Все эти числа записываются в новой симплекс-таблице.

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

Пример 9.

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

Таблица 5

Вид сырья	Нормы затрат сырья (кг) на одно изделие			Общее количество сырья (кг)
Цена одного изделия (руб.)

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

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

Решение. Составим математическую модель задачи. Искомый выпуск изделий А обозначим через x 1 , изделий В – через , изделий С – через . Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные должны удовлетворять следующей системе неравенств:

(29)

Общая стоимость произведенной предприятием продукции при условии выпуска x 1 изделий А , изделий В и изделий С составляет

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

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

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений

Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, – это неиспользуемое количество сырья I вида.

Преобразованную систему уравнений запишем в векторной форме:

Поскольку среди векторов имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план Х =(0; 0; 0; 360; 192; 180), определяемый системой трехмерных единичных векторов которые образуют базис трехмерного векторного пространства.

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

Для векторов базиса

Таблица 6

	р 5

Как видно из таблицы 6, значения всех основных переменных равны нулю, а дополнительные переменные принимают свои значения в соответствии с ограничениями задачи. Эти значения переменных отвечают такому “плану”, при котором ничего не производится, сырье не используется и значение целевой функции равно нулю (т. е. стоимость произведенной продукции отсутствует). Этот план, конечно, не является оптимальным.

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

Так, число – 9 означает, что при включении в план производства одного изделия А обеспечивается увеличение выпуска продукции на 9 руб. Если включить в план производства по одному изделию В и С, то общая стоимость изготовляемой продукции возрастет соответственно на 10 и 16 руб. Поэтому с экономической точки зрения наиболее целесообразным является включение в план производства изделий С. Это же необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число стоит в 4-й строке столбца вектора Р 3 . Следовательно, в базис введем вектор Р 3 . определяем вектор, подлежащий исключению из базиса. Для этого находим

Найдя число мы тем самым с экономической точки зрения определили, какое количество изделий С предприятие может изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида. Так как сырья данного вида соответственно имеется 360, 192 и 180 кг, а на одно изделие С требуется затратить сырья каждого вида соответственно 12, 8 и 3 кг, то максимальное число изделий С , которое может быть изготовлено предприятием, равно т. е. ограничивающим фактором для производства изделий С является имеющийся объем сырья II вида. С учетом его наличия предприятие может изготовить 24 изделия С. При этом сырье II вида будет полностью использовано.

Следовательно, вектор Р 5 подлежит исключению из базиса. Столбец вектора Р 3 к 2-я строка являются направляющими. Составляем таблицу для II итерации (табл. 7).

Таблица 7

	P 4 p 3

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

Для определения остальных элементов табл. 7 применяем правило треугольника. Эти элементы могут быть вычислены и непосредственно по рекуррентным формулам.

Вычислим элементы табл. 7, стоящие в столбце вектора Р 0 . Первый из них находится в 1-й строке этого столбца. Для его вычисления находим три числа:

1) число, стоящее в табл. 6 на пересечении столбца вектора Р 0 и 1-й строки (360);

2) число, стоящее в табл. 6 на пересечении столбца вектора P 3 и 1-й строки (12);

3) число, стоящее в табл. 7 на пересечении столбца вектора Р 0 и 2-й строки (24).

Вычитая из первого числа произведение двух других, находим искомый элемент: 360 – 12 х 24=72; записываем его в 1-й строке столбца вектора Р 0 табл. 7.

Второй элемент столбца вектора Р 0 табл. 7 был уже вычислен ранее. Для вычисления третьего элемента столбца вектора Р 0 также находим три числа. Первое из них (180) находится на пересечении 3-й строки и столбца вектора Р 0 табл. 6, второе (3) – на пересечении 3-й строки и столбца вектора P 3 табл. 6, третье (24) – на пересечении 2-й строки и столбца вектора Р 0 табл. 8. Итак, указанный элемент есть 180 – 24 х 3=108. Число 108 записываем в 3-й строке столбца вектора Р 0 табл. 7.

Значение F 0 в 4-й строке столбца этого же вектора можно найти двумя способами:

1) по формуле , т.е.

2) по правилу треугольника; в данном случае треугольник образован числами 0, -16, 24. Этот способ приводит к тому же результату: 0 - (-16) х 24=384.

При определении по правилу треугольника элементов столбца вектора Р 0 третье число, стоящее в нижней вершине треугольника, все время оставалось неизменным и менялись лишь первые два числа. Учтем это при нахождении элементов столбца вектора P 1 табл. 7. Для вычисления указанных элементов первые два числа берем из столбцов векторов P 1 и Р 3 табл. 6, а третье число – из табл. 7. Это число стоит на пересечении 2-й строки и столбца вектора P 1 последней таблицы. В результате получаем значения искомых элементов: 18 – 12 х (3/4) =9; 5 – 3 х (3/4) = 11/4.

Число в 4-й строке столбца вектора P 1 табл. 7 можно найти двумя способами:

1) по формуле Z 1 -С 1 =(C,P 1)-C 1 имеем

2) по правилу треугольника получим

Аналогично находим элементы столбца вектора P 2 .

Элементы столбца вектора Р 5 вычисляем по правилу треугольника. Однако построенные для определения этих элементов треугольники выглядят иначе.

При вычислении элемента 1-й строки указанного столбца получается треугольник, образованный числами 0,12 и 1/8. Следовательно, искомый элемент равен 0 – 12х (1/8) = -3/2. Элемент, стоящий в 3-й строке данного столбца, равен 0 - 3 х (1 /8) = -3/8.

По окончании расчета всех элементов табл. 7 в ней получены новый опорный план и коэффициенты разложения векторов через базисные векторы P 4 , P 3 , P 6 и значения и . Как видно из этой таблицы, новым опорным планом задачи является план X =(0; 0; 24; 72; 0; 108). При данном плане производства изготовляется 24 изделия С и остается неиспользованным 72 кг сырья 1 вида и 108 кг сырья III вида. Стоимость всей производимой при этом плане продукции равна 384 руб. Указанные числа записаны в столбце вектора Р 0 табл. 7. Как видно, данные этого столбца по-прежнему представляют собой параметры рассматриваемой задачи, хотя они претерпели значительные изменения. Изменились данные и других столбцов, а их экономическое содержание стало более сложным. Так, например, возьмем данные столбца вектора Р 2 . Число 1/2 во 2-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий С , если запланировать выпуск одного изделия В. Числа 9 и 3/2 в 1-й и 3-й строках вектора P 2 показывают соответственно, сколько потребуется сырья I и II вида при включении в план производства одного изделия В , а число – 2 в 4-й строке показывает, что если будет запланирован выпуск одного изделия В , то это обеспечит увеличение выпуска продукции в стоимостном выражении на 2 руб. Иными словами, если включить в план производства продукции одно изделие В , то это потребует уменьшения выпуска изделия С на 1/2 ед. и потребует дополнительных затрат 9 кг сырья I вида и 3/2 кг сырья III вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастет на 2 руб. Таким образом, числа 9 и 3/2 выступают как бы новыми “нормами” затрат сырья I и III вида на изготовление одного изделия В (как видно из табл. 6, ранее они были равны 15 и 3), что объясняется уменьшением выпуска изделий С.

Такой же экономический смысл имеют и данные столбца вектора Р 1 табл. 7. Несколько иное экономическое содержание имеют числа, записанные в столбце вектора Р 5 . Число 1/8 во 2-й строке этого столбца, показывает, что увеличение объемов сырья II вида на 1 кг позволило бы увеличить выпуск изделий С на 1/8 ед. Одновременно потребовалось бы дополнительно 3/2 кг сырья I вида и 3/8 кг сырья III вида. Увеличение выпуска изделий С на 1/8 ед. приведет к росту выпуска продукции на 2 руб.

Из изложенного выше экономического содержания данных табл. 7 следует, что найденный на II итерации план задачи не является оптимальным. Это видно и из 4-й строки табл. 7, поскольку в столбце вектора P 2 этой строки стоит отрицательное число – 2. Значит, в базис следует ввести вектор P 2 , т. е. в новом плане следует предусмотреть выпуск изделий В. При определении возможного числа изготовления изделий В следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий В определяется для , т. е. находим

Следовательно, исключению из базиса подлежит вектор Р 4 иными словами, выпуск изделий В ограничен имеющимся в распоряжении предприятия сырьем I вида. С учетом имеющихся объемов этого сырья предприятию следует изготовить 8 изделий В. Число 9 является разрешающим элементом, а столбец вектора P 2 и 1-я строка табл. 7 являются направляющими. Составляем таблицу для III итерации (табл. 8).

Таблица 8

	P 2 P 3

В табл. 8 сначала заполняем элементы 1-й строки, которая представляет собой строку вновь вводимого в базис вектора Р 2 . Элементы этой строки получаем из элементов 1-й строки табл. 7 делением последних на разрешающий элемент (т.е. на 9). При этом в столбце С б данной строки записываем .

Затем заполняем элементы столбцов векторов базиса и по правилу треугольника вычисляем элементы остальных столбцов. В результате в табл. 8 получаем новый опорный план X =(0; 8; 20; 0; 0; 96) и коэффициенты разложения векторов через базисные векторы и соответствующие значения и

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

Следовательно, план выпуска продукции, включающий изготовление 8 изделий В и 20 изделий С , является оптимальным. При данном плане выпуска изделий полностью используется сырье I и II видов и остается неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 руб.

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

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

Таблица 9

	р 5 P 4 p 3 P 2 p 3

Как видно из табл. 10, исходный опорный план не является оптимальным. Поэтому переходим к новому опорному плану. Это можно сделать, так как в столбцах векторов P 1 и p 5 , 4-я строка которых содержит отрицательные числа, имеются положительные элементы. Для перехода к новому опорному плану введем в базис вектор p 5 и исключим из базиса вектор p 4 . Составляем таблицу II итерации.

Таблица 11

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