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

Автор работы: Пользователь скрыл имя, 12 Ноября 2009 в 18:52, Не определен

Описание работы

1.Краткий обзор алгоритмов решения задач данного типа
2.Содержательная постановка задачи
3.Разработка и описание алгоритма решения задачи
4.Назначение программы
5.Инструкция пользователю
6.Текст исходного модуля

Файлы: 2 файла

simpleks_metod1.xls

— 118.00 Кб (Просмотреть файл, Скачать файл)

курсовик.doc

— 247.00 Кб (Скачать файл)

Оглавление

 

ВВЕДЕНИЕ

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

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

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

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

       Сложность экономики иногда рассматривалась  как  обоснование невозможности ее моделирования,  изучения средствами математики. Но такая точка зрения в принципе неверна. Моделировать можно объект любой природы и любой сложности.  И как раз сложные объекты представляют наибольший интерес для моделирования; именно здесь  моделирование  может  дать  результаты,  которые нельзя получить другими способами исследования.

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

 

1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА

1.1 Математическое программирование

       Математическое  программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x1, x2, ... , xn ) при ограничениях gi ( x1, x2, ... , xn ) * bi , где gi - функция, описывающая ограничения, * - один из следующих знаков £ , = , ³ , а bi - действительное число, i = 1, ... , m. f называется функцией цели ( целевая функция ).

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

       Задачу  линейного программирования можно сформулировать так . Найти max

       

       при условии : a11 x1 + a12 x2 + . . . + a1n xn £ b1 ;

         a21 x1 + a22 x2 + . . . + a2n xn £ b2 ;

        . . . . . . . . . . . . . . . . . . . . . . . . . . . .

        am1 x1 + am2 x2 + . . . + amn xn £ bm ;

         x1 ³ 0, x2 ³ 0, . . . , xn ³ 0 .

       Эти ограничения называются условиями  неотрицательности. Если все ограничения  заданы в виде строгих равенств, то данная форма называется канонической.

       В матричной форме задачу линейного  программирования записывают следующим образом. Найти max cT x

       при условии

       A x £ b ;

       x ³ 0 ,

       где А - матрица ограничений размером ( m´n), b(m´1) - вектор-столбец свободных членов, x(n ´ 1) - вектор переменных, сТ = [c1, c2, ... , cn ] - вектор-строка коэффициентов целевой функции.

       Решение х0 называется оптимальным, если для него выполняется условие сТ х0 ³ сТ х , для всех х Î R(x).

       Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной  задаче максимизации.

       Для решения задач данного типа применяются  методы:

       1) графический;

       2) табличный ( прямой, простой ) симплекс - метод;

       3) метод искусственного базиса;

       4) модифицированный симплекс - метод;

       5) двойственный симплекс - метод. 

1.2 Табличный симплекс - метод

       Для его применения необходимо, чтобы  знаки в ограничениях были вида “  меньше либо равно ”, а компоненты вектора b - положительны.

       Алгоритм  решения сводится к следующему :

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

         Если в исходной системе ограничений  присутствовали знаки “ равно  ” или “ больше либо равно  ”, то в указанные ограничения  добавляются

       искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.

         Формируется симплекс-таблица.

         Рассчитываются симплекс-разности.

         Принимается решение об окончании  либо продолжении счёта.

         При необходимости выполняются итерации.

         На каждой итерации определяется  вектор, вводимый в базис, и  вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

1.3 Метод искусственного  базиса

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

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

  1.4 Модифицированный симплекс - метод

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

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

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

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

 

2.СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

         Для производства двух видов  изделий А и В используется  три типа технологического оборудования. На производство единицы изделия А идёт времени, часов : оборудованием 1-го типа - а1 , оборудованием 2-го типа - а2 , оборудованием 3-го типа - а3 . На производство единицы изделия В идёт времени, часов : оборудованием 1-го типа - b1 , оборудованием 2-го типа - b2 ,, оборудованием 3-го типа - b3 .

       На  изготовление всех изделий администрация предприятия может предоставить оборудование 1-го типа не более, чем на t1 , оборудование 2-го типа не более, чем на t2 , оборудование 3-го типа не более, чем на t3 часов.

       Прибыль от реализации единицы готового изделия  А составляет a рублей, а изделия В - b рублей.

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

       а1 = 1 b1 = 5 t1 = 10 a = 2

       а2 = 3 b2 = 2 t2 = 12 b = 3

       а3 = 2 b3 = 4 t3 = 10

 

3.РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

3.1 Построение математической  модели задачи

    На произв-во изделия А, часов  На произв-во изделия B, часов  Предпр-е  предоставит, часов
 Оборуд-е 1го типа  1  5  10
 Оборуд-е 2го типа  3  2  12
 Оборуд-е 3го типа  2  4  10
 Прибыль от реализации, за ед. изд-я  2  3   

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