Симплексный метод решения ЗЛП (стр. 1 из 5)

Министерство образования и науки Украины

Донбасская государственная машиностроительная академия

Факультет автоматизации машиностроения
и информационных технологий

Кафедра интеллектуальных систем принятия решений

курсовая работа

подисциплине «МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ»

на тему

«Симплексный метод решения ЗЛП»

Выполнила

Студентка гр. ИС-09-1 __________________ ___________________

подпись Германенко М.А.

Руководители __________________ ___________________

подпись Протыняк С. И.

__________________ ___________________

подпись Сташкевич И. И.

Краматорск 2011

реферат

Курсовая работа по дисциплине «Математические методы исследования операций» на тему: "Симплексный метод решения ЗЛП" студентки группы ИС 09–1 Германенко М.А. содержит 53 страницы машинописного текста, 4 рисунка, 4 таблицы, 19 страниц приложения.

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

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

МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ, ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ, ЭМЕРДЖЕНТНОСТЬ, СИМПЛЕКС-МЕТОД, ПРЯМАЯ ЗАДАЧА, ДВОЙСТВЕННАЯ ЗАДАЧА, УСЛОВИЕ НЕОТРИЦАТЕЛЬНОСТИ, ЦЕЛЕВАЯ ФУНКЦИЯ, БАЗИСНОЕ РЕШЕНИЕ, ПРОГРАММНЫЙ ПРОДУКТ.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ…………………………………………………………………4

І Основные теоретические положения симплексного метода решения ЗЛП…………………………………………………….…6

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

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

1.3 Методы решения задач линейного программирования…………..10

1.4 Общая характеристика симплекс-метода……………………………12

ІІ РЕШЕНИЕ ЗЛП СИМПЛЕКСНЫМ МЕТОДОМ………………..…..14

2.1 Примеры использования симплекс-метода в экономике…………14

2.2 Алгоритм решения ЗЛП симплексным методом……………………15

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

методом…………………………………………………………………...17

2.4 Двойственная задача………………………………………………....23

ІІІ КОМПЬЮТЕРНАЯ РЕАЛИЗАЦИЯ СИМПЛЕКС-МЕТОДА ПРИ РЕШЕНИИ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ……….....28

3.1 Описание программного продукта……………………………...…28

3.2 Тестирование программного продукта………………….…………30

ВЫВОДЫ………………………………………………………………….32

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ………………………….34

ПРИЛОЖЕНИЕ А………………………………………………………...35

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

Как известно, в практике хозяйственной деятельности выбор между различными вариантами (планами, решениями) предполагает поиск наилучшего. Когда хозяйка отправляется на рынок для закупки мяса, а проектировщик стремится найти оптимальный способ размещения станков, они занимаются поисками вариантов, требующих минимума затрат или максимума результата с учетом определенных ограничений (денег, ресурсов, времени).

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

Линейное программирование — решение линейных уравнений (уравнений первой степени) посредством составления программ и применения различных методов их последовательного решения, существенно облегчающих расчеты и достижение искомых результатов.

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

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

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

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

Z(X)=c₁x₁+c₂x₂+…+c_nx_n→ max(min), (1.1)

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁,

…………………………

a_i1x₁+a_i2x₂+…+a_inx_n=b_i,

a_(i+1)1x₁+a_(i+1)2x₂+…+a_(i+1)nx_n≤b_i+1 (1.2)

………………………..

a_m1x₁+a_m2x₂+…+a_mnx_n≤b_m

x_j≥0, j=1,2,…,t; t≤n. (1.3)