Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Методические указания'
Методические указания к написанию и оформлению рефератов и курсовых работ по дисциплине «Экономическая теория» / Уфимск. гос. авиац. техн. ун-т; сост...полностью>>
'Документ'
09:00 Экскурсия  «Лабиринтами львовских улиц …» - здесь все дышит древностью, кажется, что мы переносимся на несколько веков назад. Именно здесь можн...полностью>>
'Документ'
Автор: неизвестен.Этот бестиарий нельзя считать древне-кельтским, хотя в него включены только существа, обитающие в традиционно кельтских странах - в ...полностью>>
'Документ'
А.В. Колодійчук , В.М. Пісний; Ж.В. Семчук Сутність інновацій, структура та основні етапи інноваційного процесу [Електронний ресурс]. –Режим доступу:...полностью>>

Домашнее задание по Теории информационных процессов и систем (

Главная > Курсовая
Сохрани ссылку в одной из сетей:

Федеральное агентство по образованию РФ

ГОУ ВПО «УГТУ-УПИ»

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

по Теории информационных процессов и систем

(ДИСЦИПЛИНА)

на тему: Линейное программирование и симплекс метод

Вариант № 13

Семестр № 7

Преподаватель Александров О.Е.

(ФИО)

Студент гр. № ДО-43010ди Сосновских В.П.

(ФИО)

номер зачетной книжки 17341907

Екатеринбург

2007

Домашнее задание по _Теории информационных процессов и систем______

(ДИСЦИПЛИНА)

№ записи в книге регистрации дата регистрации 200 7 г.

Преподаватель __ Александров О.Е._________________________________

(ФИО)

Студент Сосновских В.П. группа № ДО-43010ди

(ФИО)

Деканат ФДО

СОДЕРЖАНИЕ

КРАТКАЯ ИСТОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 4

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

Таблица 1 9

Вид сырья 9

Запас сырья, Т 9

CX  max 11

2. ВЫБОР МЕТОДА РЕАЛИЗАЦИИ МОДЕЛИ. ОБОСНОВАНИЕ МЕТОДА 13

4. ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ. 18

ВВЕДЕНИЕ.

В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства. Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования. В конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач – симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.

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

КРАТКАЯ ИСТОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной , если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника; Ганнибалу, чтобы разбить римлян при Каннах, командуя вдвое меньшей армией, нужно было действовать очень обдуманно.

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

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

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

Эти премии получили свое название в честь их учредителя – известного химика и изобретателя Альфреда Нобеля, они должны были присуждаться за научные открытия в области физики, химии, физиологии или медицины, за литературные произведения, «отражающие человеческие идеалы», а так же тем, кто «внесет весомый вклад в сплочение народов, уничтожение рабства, снижение численности существующих армий и содействие мирной договоренности». Математикам премия не предназначалась. Однако в 1969 году Шведский банк по случаю 300-летия со дня своего образования учредил премию памяти А.Нобеля – по экономическим наукам. Она то и была присуждена в 1975 году Л.В.Канторовичу и Т.Купмансу за создание новой математической науки (получившей название линейного программирования) и применение этой теории в экономике.

В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда… Поэтому простой перебор вершин не годился. Леонид Витальевич писал: «оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения». И уже летом 1939 года была сдана в набор книга Л.В.Канторовича «Математические методы организации и планирования производства», в которой закладывались основания того, что ныне называется математической экономикой.

Но вернемся в 1939 год. Говорят, что истина рождается ересью и увы, так случилось и с идеями Л.В.Канторовича в области экономики. Они не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана.

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

Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течении пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

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

А самому Леониду Витальевичу – как естественно было бы ему, испытав первые грозные удары ретроградов, остеречься от «грехов» молодости, забыть про всю эту экономику и вернуться к математике. Но Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет и кое что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А начиная с 1960 года Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году.

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

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

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

Рассмотрим задачу из экономической области на составление оптимальной производственной программы [1]. Для изготовления двух видов продукции Р1, Р2 используется три вида сырья S1, S2, S3. Запасы сырья, количество единиц сырья, затраченных на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице1.

Таблица 1

Вид сырья

Запас сырья, Т

Затраты сырья на единицу продукции

Р1

Р2

S1

9

1

1

S2

3

0,5

1

S3

3

1

0,5

Прибыль от единицы продукции,

денежных единиц

1

2

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

Математически эта задача формулируется следующим образом.

Переменные.

Так как нужно определить объем производства каждого вида продукции, переменными в модели являются:

x1 – объем производства продукции Р1

х2 – объем производства продукции Р2

Целевая функция. Конечную цель задачи- получение максимальной прибыли при реализации продукции – выразим как функцию 2-х переменных х1 и х2.

Суммарная прибыль Z = x1 + 2 x2

Ограничения.

При решении рассматриваемой задачи должны быть учтены ограничения на расход сырья.

х1 + х2  9 (для вида S1),

0,5 х1 + х2  3 (для вида S2),

х1 + 0,5 х2  3 (для вида S3).

Добавим ограничения на неотрицательность значений объемов производства продукции

х1  0, х2  0.

Итак, математическая модель формулируется следующим образом.

Определить объемы производства х1, х2 продукции вида р1 и р2 в тоннах, при которых достигается максимум целевой функции

Z = х1 + 2 х2

при

х1 + х2  9

0,5 х1 + х2  3 ограничения

х1 + 0,5 х2  3

Таким образом, задача ЛП заключается в отыскании вектора (х1, х2,…,хJ,…,хn), максимизирующего линейную целевую функцию

Z= с1х12х2+…+сjхj+…+сnхn, (1)

при следующих линейных ограничениях

11х1 + 12 х2 + …+1n xn  b1

21х1 + 22 х2 + …+2n xn  b2

. . . (2)

m1х1 + m2 х2 + …+mn xn  bm

x1 0, x2 0,. . .,xn 0. (3)

Запись задачи ЛП в виде (1)-(3) называется нормальной формой задачи.

Эту же задачу ЛП можно представить в векторно-матричной записи:

CX  max

AX  B, x  0, где C = (c1, c2,…,cn), , ,

A=(ij), , – матрица коэффициентов,

С - вектор коэффициентов целевой функции.

Область называется областью допустимых значений (ОДЗ) задач линейного программирования.

Соотношения (2), (3) называются системами ограничений задачи ЛП.

Так как , то можно ограничиться изучением задачи одного типа.

Решением задачи ЛП называется вектор, удовлетворяющий системе ограничений задачи и оптимизирующий целевую функцию.

Другая форма представления задачи ЛП – каноническая. Она имеет вид:

CX  max
AX = B, X  0.

Наряду с задачей ЛП в нормальной форме (1)-(3) рассмотрим задачу

BU  min (4)

ATU  C, U  0, (5)

где - переменные двойственной задачи.

Задача (4), (5) называется двойственной по отношению к задаче (1)-(3).

2. ВЫБОР МЕТОДА РЕАЛИЗАЦИИ МОДЕЛИ. ОБОСНОВАНИЕ МЕТОДА

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.

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

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

  2. Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1» , а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).

  3. Ограничения вида «» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.

3. АЛГОРИТМ СИМПЛЕКС-МЕТОДА.

Симплекс метод является наиболее распространенным вычислительным методом, который может быть применен для решения любых задач ЛП как вручную, так и с помощью ЭВМ.

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

1. Рассмотрим задачу ЛП в нормальной форме (1)-(3). Сделаем допущения: В  0.

Введем вектор Y такой, что Y = B   AX, YRm, Y  0,

Y = (xn+1, xn+2, . . .,xn+m)T. Вектор Y называют балансовым, а xn+1, xn+2, . . .,xn+m – балансовыми переменными.

Тогда систему ограничений (2) задачи ЛП можно записать:

11х1 + 12 х2 + …+1n xn n+1 = b1

21х1 + 22 х2 + …+2n xn n+2 = b2

. . . (6)

m1х1 + m2 х2 + …+mn xn n+m = bm

причем xj  0, (7)

Таким образом, задачу ЛП (1)-(3) привели от нормальной формы к канонической.

В целевую функцию балансовые переменные входят с нулевыми коэффициентами, т.е.

=c1x1 + c2x2 +…+ cnxn + 0xn+1 +…+ 0xn+m



Скачать документ

Похожие документы:

  1. Домашнее задание по Теория информационных процессов №1

    Курсовая
    Настоящее руководство содержит сведения необходимые для практического изучения проблемы составления оптимальных конвейерных расписаний. Эта проблема может быть актуальна на этапе технологической подготовки производства при выборе
  2. Рабочая программа дисциплины Теория информационных процессов и систем  Рекомендована методическим Советом Урфу для специальностей и направлений подготовки: Специальности (направления)

    Рабочая программа
    Программа составлена в соответствии с Государственным образовательным стандартом высшего и среднего профессионального образования по направлению подготовки 230200 –ИНФОРМАЦИОННЫЕ СИСТЕМЫ, степень (квалификация) БАКАЛАВР ИНФОРМАЦИОННЫХ
  3. Программа дисциплины опд. Ф. 05. Теория информационных процессов и систем для студентов специальности 230201 Информационные системы и технологии

    Программа дисциплины
    Целью преподавания дисциплины «Теория систем» является ознакомление студентов с наиболее общими свойствами, закономерностями и классификацией систем, с основными особенностями и свойствами сложных систем, с современными подходами и
  4. Рабочая программа дисциплины «теория информационных процессов и систем» опд. Ф. 05

    Рабочая программа
    Рабочая программа составлена на основе Государственного образовательного стандарта высшего профессионального образования к содержанию и уровню подготовки выпускника по специальности 230201 (071900) «Информационные системы и технологии», № 276 тех.
  5. Рабочая программа По дисциплине «Теория информационных процессов и систем» По специальности 230201. 65 Информационные системы и технологии

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

Другие похожие документы..