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

Базис			9	10 ( )	16 ( )	0 ( )	0 ( )	0 ( )
	0 ( )	72	9	9	0	1		0
	16 ( )	24			1	0		0
	0 ( )	108			0	0		1
		384	3	-2	0	0	2	0

 

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

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

1) Число, стоящее на месте этого элемента в предыдущей таблице. В нашем случае это число, стоящее в таблице 3.2.2 на пересечении столбца вектора и первой строки (360);

2) Число, стоящее в той же строке что и искомый элемент, а также в столбце вектора, вводимого в базис из предыдущей симплекс-таблицы. В нашем случае это число, стоящее в таблице 3.2.2 на пересечении столбца вектора и первой строки (12);

3) Число в строке введённого в базис вектора и в столбце искомого элемента в текущей симплекс-таблице. В нашем случае это число, стоящее в таблице 3.2.3 на пересечении столбца вектора и второй строки (24).

Вычитая из первого числа произведение двух других, находим искомый элемент: 360-12*24=72.

Записываем его в первой строке столбца вектора таблицы 3.2.3. Аналогичным образом находим и все остальные элементы:

180 - 3*24 = 108;

18 - 12*3/4 = 9;

15 - 12*1/2 = 9;

0 - 12*1/8 = -3/2;

5 - 3*3/4 = 11/4;

3 – 3*1/2 = 3/2;

0 – 3*1/8 = -3/8.

По окончании расчёта всех элементов таблицы 3.2.3 в ней получены новый опорный план и коэффициенты разложения векторов ( ) через базисные векторы , , и значения и . Как видно из этой таблицы, новым опорным планом задачи является план Х = [0; 0; 24; 72; 0; 108]. При данном плане производства изготовлены 24 изделия C и остаётся неиспользованным 72 кг сырья I вида и 108 кг сырья III вида. Стоимость всей производимой при этом плане продукции равна 384 руб. Указанные числа записаны в столбце вектора таблицы 3. Как видно, данные этого столбца по-прежнему представляют собой параметры рассматриваемой задачи, хотя они были значительно изменены. Изменились данные и других столбцов, а их экономическое содержание стало более сложным.

Так, например, возьмём два столбца вектора . Число 1/2 во 2-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий С, если запланировать выпуск одного изделия В. Числа 9 и 3/2 в первой и третьей строках вектора показывают соответственно, сколько потребуется сырья I и II вида при включении в план производства одного изделия В. Это обеспечит увеличение выпуска продукции в выражении стоимости на 2 руб. Другими словами, если включить в план производства продукции одно изделие В, то это потребует уменьшения выпуска изделия С на ½ ед. и потребует дополнительных затрат 9 кг сырья I вида и 3/2 кг сырья III вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастёт на 2 руб. Таким образом, числа 9 и 3/2 выступают как бы новыми «нормами» затрат сырья I и III вида на изготовление одного изделия В (как видно из таблицы 3.2.2, ранее они были равны 15 и 3), что объясняется уменьшением выпуска изделий С.

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

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

.

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

4) Составляем таблицу для третьей итерации.

Таблица 3.2.4. Симплекс-таблица для третьей итерации.

Базис			9	10	16	0	0	0
	10	8	1	1	0			0
	16	20		0	1			0
	0	96		0	0			1
		400	5	0	0			0

 

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

Затем заполняем элементы столбцов-векторов базиса и по правилу треугольника  вычисляем элементы  остальных столбцов.

В результате получаем новый опорный план Х = [0; 8; 20; 0; 0; 96] и коэффициенты разложения векторов через базисные векторы p2, p3, p6 и соответствующие значения и .

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

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

Ответ: Х = (0; 8; 20), fmax=400.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

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

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

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

Вычислительную эффективность симплекс-метода можно оценить с помощью 2-х параметров:

1) число итераций, необходимых для  достижения оптимума;

2) общие затраты машинного времени.

Подведем итог нашей работы.

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

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

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

 

 

Список используемой литературы

 

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

2. Н. И. Глебов, Ю. А. Кочетов, А. В. Плясунов. Методы оптимизации. Учебное пособие. — Новосибирск: Новосибирский государственный университет, 2000. 105 с.

3. www.simplexwin.narod.ru/Simpl_metod

4. ru.wikipedia.org/wiki/Симплекс-метод

5. www.math.nsc.ru/LBRT/k5/opt.html

6. www.np.vspu.ac.ru/doc/zadachnik_optimizacya

 

 

                                                                                                          

1 Данный метод был разработан американским математиком Джорджем Данцигом в 1947 году.

2 Альберт Вильям Таккер (1905–1995) — американский математик.