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

Автор: Пользователь скрыл имя, 18 Декабря 2012 в 21:32, курсовая работа

Краткое описание

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

Оглавление

Введение………………………………………………………………………………..3
1 Описание симплексного метода..…………...……………………………...……….4
2 Алгоритм решения задач симплексным методом……………………...…………..9
2.1 Графический метод……………………………………………………………….16
2.2 Табличный симплекс – метод……………………………………………….…...21
2.3 Модифицированный симплекс – метод.………………………………………...25
2.4 Алгоритм метода искусственного базиса………………...…………….……….29
2.5 Двойственный симплекс-метод………………..………………………………...30
3 Решение реальной производственной задачи…………………………………….32
3.1 Постановка задачи………………………………………………………………..32
3.2 Решение задачи…………………………………………………………………...32
Заключение……………………………………………………………………………42
Список используемой литературы…………………………………………………..44

Файлы: 1 файл

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

— 619.00 Кб (Скачать)

Такой же экономический  смысл имеют и данные столбца вектора таблицы 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) — американский математик.

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




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