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

Министерство  образования и науки Российской Федерации

Федеральное государс Й    твенное бюджетное образовательное учреждение высшего профессионального образования

ТАМБОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ  УНИВЕРСИТЕТ

Институт экономически и качества жизни

Кафедра «Коммерция и бизнес-информатика»

 

УТВЕРЖДАЮ И.о. зав. кафедрой                                              М.А. Блюм          подпись                                         инициалы, фамилия «____»___________________2013г.

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

 

к курсовой работе по                               исследованию операции  

                                                                            наименование учебной дисциплины

 

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

 

Автор работы                      А.Я. Туре                                   Группа          ББИ-22

                                                инициалы, фамилия

Специальность                      080500 – «Бизнес информатика» 

                                                                                     номер, наименование

Обозначение курсовой работы ТГТУ.080500.211 

 

Руководитель работы                                                                       А.Н. Пчелицев 

                                                             ^{подпись, дата                                                       инициалы, фамилия}

Работа защищена                                       Оценка_______________________

 

 

Члены комиссии:

____________________________________________            подпись, дата                                                                   инициалы, фамилия ____________________________________________            подпись, дата                                                                    инициалы, фамилия ____________________________________________            подпись, дата                                                                    инициалы, фамилия

Нормоконтролер

Т.И. Лапина      подпись,  дата                                                                              инициалы, фамилия

                                                        

Тамбов 2013 г.

Министерство  образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное  учреждение высшего профессионального  образования

ТАМБОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ Задание принял к исполнению УНИВЕРСИТЕТ

Институт экономически и качества жизни

Кафедра «Коммерция и бизнес-информатика»

 

УТВЕРЖДАЮ И.о. зав. кафедрой                                              М.А. Блюм          подпись                                         инициалы, фамилия «____»____________________2013 г.

 

ЗАДАНИЕ

на курсовую работу

 

Студент         А.Я. Туре             код      211  Группа ББИ-22     

                                    инициалы, фамилия

 

1 Тема    Симплекс-метод исследования задачи линейного программирования 

 

2 Срок представления  работы к защите 

«   »           2013 г.

 

3 Исходные  данные для проектирования (научного  исследования)

 

Учебная литература по теме работы 

 

4 Перечень  разделов пояснительной записки

 

4.1 Введение 

4.3 Основные теоритические положения симплексного метода решения Задачи линейного программирования 

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

4.5 Конпьютерная реализация симплекс-метода при решении задачи линейного програмирования 

4.6 Заключение 

4.7 Список используемых источников 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Руководитель  работы                                                                       А.Н. Пчелицев 

                                                             ^{подпись, дата                                                       инициалы, фамилия}

 

 

 

 

 

 

Задание принял к исполнению                                                               А.Я. Туре 

                                                             ^{подпись, дата                                                       инициалы, фамилия}

СОДЕРЖАНИЕ

 

 

Введение…………………………......………………......………………………4 
 
1 Основные теоретические положения симплексного метода решения задачи линейного програмирования…............................……………………………6 
 
1.1 Теория линейного программирования…………........…………………...6 
 
1.2 Общий вид задач линейного программирования….....……………….8 
 
1.3 Методы решения задач линейного программирования….....………...10 
 
1.4 Общая характеристика симплекс-метода……………......………………12 
 
2  Решение задачи линейного программирования симплексным методом 14 

2.1 Примеры  использования симплекс-метода в  экономике…………14 
 
2.2 Алгоритм решения задачи линейного програмирования симплексным методом………...................................................................................……………15 
 
2.3 Решения задачи линейного програмирования симплекс-метод..............17 
 
2.4 Двойственная задача........…………………………………..…….………....23 
 
3 Конпьютерная реализация симплекс-метода при решении задачи линейного программирования.........................................................................….......…….....28 
 
3.1 Описание программного продукта.............……………………………...…28 
 
3.2 Тестирование программного продукта.........………………….…………30 
 
Заключение........………………………………………………………………….32 
 
Список используемой литературы.................................………………………….34 
 
                                                                                              

 

 

 

 

 

ВВЕДЕНИЕ 

 

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

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

            

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

         1.1 Теория линейного программирования

          Как известно, в практике хозяйственной деятельности выбор между различными вариантами (планами, решениями) предполагает поиск наилучшего. Когда хозяйка отправляется на рынок для закупки мяса, а проектировщик стремится найти оптимальный способ размещения станков, они занимаются поисками вариантов, требующих минимума затрат или максимума результата с учетом определенных ограничений (денег, ресурсов, времени). 
          Решить подобную задачу бывает непросто, особенно при наличии большого числа вариантов. Время и затраты при выборе оптимума не всегда оправданны: издержки поиска и перебора вариантов могут превысить достигнутый выигрыш.Как показывает практика, опыт и интуиция оказываются недостаточными для обоснования оптимального решения.Более надежный и эффективный способ — использова0ние математических (количественных) подходов и расчетов. Однако математические подходы и обоснования длительное время игнорировались теоретиками, делавшими “погоду” в экономической науке. Многие важные работы были заморожены, публикации экономистов-математиков тормозились и ограничивались. И все же в тот период математические изыскания продолжались, даже в условиях гонения на математиков были достигнуты блестящие результаты.Одним из наиболее значительных и ярких достижений в области экономико-математических исследований было открытие Леонидом Витальевичем Канторовичем (1912—1986) Метода линейного программирования.  
          Линейное программирование — решение линейных уравнений (уравнений первой степени) посредством составления программ и - 
применения различных методов их последовательного решения, существенно облегчающих расчеты и достижение искомых результатов.

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

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

          1.2 Общи вид задая линейного програмирования

          В общем случае задача линейного программирования может быть записана в таком виде (формула 1)                             

                                               (1)

 

                                                                                                                                                                                   

                                       ,                                                (2)                

 

                                                                                  

 

 
          Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).