Вопрос 2 Симплекс-метод: общее понятие и его особенности

Основное содержание симплексного метода заключается в следующем:

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

1. Привести задачу к каноническому виду¹

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

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

■ Ограничения определяют зависимость между величинами, влияющими на решение задачи.

■ Граничные условия показывают, в каких пределах могут находиться искомые величины

Система линейных уравнений решается с помощью метода Жордана – Гаусса

Вопрос 3 Пример решения задачи оптимизации симплекс-методом

Для изготовления различных изделий (А, В,С) предприятие использует три различных вида сырья.

Вид сырья	Нормы затрат сырья на 1 изделие			Общее количество сырья
	А	Б	С
1	18	15	12	360
2	6	4	8	192
3	5	3	3	180
Цена 1-го изд. (грн)	9	10	16

Составим математическую модель задачи. Искомый выпуск изделий А обозначим через Х₁, В - Х₂, С - X₃.

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

F = 9X₁ + 10 Х₂ + I6X₃ (5.1)

(целевая функция)

Поскольку имеются ограничения по ресурсам, то составляются следующая система неравенств. Переменные Х₁, Х₂, Х₃ должны удовлетворять следующие системы неравенств:

(5.2)

(ограничения)

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

(граничное условие)

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

(5.3)

Эти дополнительные переменные у₁, у₂, у₃ по экономическому смыслу означают неиспользуемое при данном плане производства количество сырья того или иного вида. Параметр

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

В общем виде:

	-X1	-X2	-X3	Свободный член
Y1	a11	a12	a13	b1
Y2	a21	a22	a23	b2
Y3	a31	a32	a33	b3
F	-c1	-c2	-c3	0

Согласно данным примера:

	-X1	-X2	-X3	Свободный член
Y1	18	15	12	360
Y2	6	4	8	192
Y3	5	3	3	180
F	-9	-10	-16	b

Это план не является оптимальным, так как элементы F-строки отрицательные. Отрицательные числа свидетельствуют не только о возможности увеличения общей стоимости производимой продукции, но и показывает, на сколько увеличится та сумма при введении в план того пли иного вида продукции. Так, число -9 означает, что при включении в план производства одного изделия А обеспечивается увеличение выпуска продукции на 9 грн. и т.д. Здесь с экономической точки зрения наиболее целесообразным является включение в план производства изделия С

Оптимизация целевой функции состоит из двух этапов:

a) Поиск опорного решения;

b) Поиск оптимального решения

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

1. В строке с наибольшим по модулю отрицательным членом строки F выбирают элемент - с₃ (-16)и столбец Хз называют разрешающим. Если в строке у₂ все коэффициенты положительные, то задача оптимизации не разрешима в связи с противоречивостью исходных данных.

2. Для элементов этого столбца (кроме элементов строки-F), имеющих тот же знак, что и соответствующие им свободные члены, вычисляют неотрицательные частные и выбирают наименьшее. Соответствующий элемент строки и столбца называют разрешающим. Например, находят 360/12=30; 192/8=24; 180/3=60. Наименьшее - 24,следственно, разрешающая строка у₂, разрешающий элемент - 8.

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

■ Разрешающий элемент а₂₃ заменяют на новый по формуле а₂₃⁼1/а₂₃

■ Элементы разрешающей строки вычисляются по формуле:

a¹₂₁=a₂₁/a₂₃; a¹₂₂=a₂₂/a₂₃; b¹₂=b₂/a₂₃

Элементы разрешающего столбца вычисляются по формулам:

a¹₁₃= -a₁₃/a₂₃; a¹₃₃= -a₃₃/a₂₃; c¹₃= -c₃/a₂₃

■ Прочие элементы таблицы (включая свободные члены и элементы F - строки) вычисляют по правилу прямоугольника:

a¹₁₁=a₁₁ - (a₂₁*a₁₃/a₂₃)

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

Перейдем к следующей таблице

	-X1	-X2	Y2	Свободный член
Y1	9	9	-1,5	72
-X3	0,75	0,5	-0,125	24
Y3	2,75	1,5	-0,375	156
F	3	-2	2	384

Экономическая интерпретация:

Найдя число 24, мы с экономической точки зрения определили какое количество изделий С предприятие может изготавливать с учетом норм расхода и имеющихся объемов сырья каждого вида. То есть ограничивающим фактором дл производства изделий С является имеющийся объем сырья второго вида. С учетом его наличия может быть изготовлено 24 изделия С. 72 кг - неиспользованное сырье первого вида, 108 кг - неиспользованное сырье третьего вида; 384 -стоимость всей произведенной продукции.

■ Экономическая интерпретация второю столбца:

Число 0,5 показывает на сколько следует уменьшить изготовление изделия С, если запланировать изготовление одного изделия В. 9 и 1,5 показывают сколько потребуется сырья первого и третьего вида при включении в план производства одного изделия В. - 2 показывает, что если будет запланирован выпуск одного изделия В, то это обеспечит увеличение выпуска продукции в стоимостном выражении на две гривны. Аналогично дается экономическая интерпретация первого столбца.

■ Экономическая интерпретация третьего столбца:

Число 0,125 показывает, что увеличение объема сырья второго вида на 1 кг позволило бы увеличить выпуск изделий С на 0,125 единицы. Одновременно потребовалось бы 1,5 сырья первого вида и 0,375 кг сырья третьего вида. Увеличение выпуска изделий С на 0,125 снизит выпуск продукции на 2грн.

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

Здесь в качестве разрешающего элемента берем хг, в качестве разрешающей строки у₅, разрешающий элемент 9

	-X1	Y1	Y2	Свободный член
-X2	1	0,11	00,017	8
-X3	0,25	-0,06	0,208	20
Y3	1,25	-0,017	-0,125	96
F	5	0,22	1,67	400

Как видно, в строке F нет отрицательного элемента, следовательно этот план является оптимальным. План выпуска продукции, включающий 8 изделий В и 20 изделий С. при данном плане выпуска изделий полностью используется сырье первого и второго вида и остается неиспользованным 96 кг. Сырья третьего вида, а стоимость производимой продукции равна 400 грн. оптимальным планом не предусматривается изготовление изделия А. Число 56 показывает, что при данном плане включения в него выпуска единиц изделия А приводит лишь к уменьшению общей величины стоимости на 5 грн.