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

Такой же экономический  смысл имеют и данные столбца вектора таблицы 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 сначала заполняем элементы первой строки, которая представляет собой строку вновь вводимого в базис вектора р². Элементы этой строки получаем из элементов первой строки таблицы 3.2.3 делением последних на разрешающий элемент (то есть на 9). При этом в столбце С^к данной строки записываем С₂=10.

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

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

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

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

Ответ: Х = (0; 8; 20), f_max=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

 

 

                                                                                                          

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

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

³ Роберт Гэри Бленд – американский математик.