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

ВВЕДЕНИЕ

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

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

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

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

Цель данной курсовой работы: изучить и научиться на практике применять симплекс-метод для решения задач линейного программирования.

Задачи курсовой работы:

1. Изучить теоретические основы симплекс-метода.

2. Рассмотреть алгоритм решения задач, с помощью симплекс-таблиц.

3. Применить симплексный метод к решению экономических задач.

ГЛАВА 1 ТЕОРИЯ СИМПЛЕКС-МЕТОДА

1.1 История создания и применения симплекс-метода

Первый, кто упомянул о математических методах в эффективном управлении производством, был советский математик и экономист - Леонид Витальевич Канторович в 1938 году. Спустя год, Леонид Витальевич опубликовал работу «Математические методы организации и планирования производства» и на практике применил результаты, полученные в этой работе.

Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Джорд Бернард Данциг разработал симплексный алгоритм, который применялся при решении задач линейного программирования. Д. Данциг считается «отцом линейного программирования», наряду с Л. В. Канторовичем.

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

После того как Данциг включил целевую функцию в свою формулировку в середине 1947 года, задача стала математически более сговорчивой. Данциг понял, что одна из нерешенных задач, которую он ошибочно принял за домашнее задание на уроке профессора Ежи Неймана (и которую позже действительно решил), применима к поиску алгоритма для линейных программ. Эта задача состояла в нахождении существования множителей Лагранжа для общих линейных программ над континуумом переменных,