1
КП
.2203 81-16
ВВЕДЕНИЕ.
За последние годы одним из основных направлений совершенствования управления экономикой, хозяйственного механизма является применение математических методов и деятельности.
При планировании экономической деятельности необходимо опираться на большое количество данных, и выбрПри планировании экономической деятельности необходимо опираться на большое количество данных, и выбранное решение должно по возможности вычислительной техники в экономике, т.е. во всех областях целенаправленной человеческой гарантировать от ошибок и быть достаточно эффективным для мирового круга условий. Необходимо повышать эффективность управления народным хозяйством, т.к. новые задачи экономического развитиПри планировании экономической деятельности необходимо опираться на большое количество данных, и выбранное решение должно по возможности вычислительной техники в экономике, т.е. во всех областях целенаправленной человеческой гарантировать от ошибок и быть достаточно эффективным для мирового круга условий. Необходимо повышать эффективность управления народным хозяйством, т.к. новые задачи экономического развития нельзя решить, используя старые механизмы.
При решении практических операционных задач находят эффективное применение различных оптимизационных моделей и методов оптимизации, основанные на использовании математического программирования.
При использовании электронно-вычислительной техники возрастает эффектПри использовании электронно-вычислительной техники возрастает эффективность операционных методов анализа и решения задач оптимизации в сфере организационного управления.
Применение электронно-вычислительной техники позволяет решать сложные задачи, математическая постановка, которых сопряжена с необходимостью рассмотрения Применение электронно-вычислительной техники позволяет решать сложные задачи, математическая постановка, которых сопряжена с необходимостью рассмотрения “крупномасштабных”моделей, содержащих большое число ограничений. При решение такого рода задач без применений электронно-вычислительной техники невозможно. Использование этой техники приводит к ускорению темпов производства, что и требуется для развития экономики математических методов.
1. ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ.
В трёх хранилищах горючего ежедневно хранится 180, 350 и 20т бензина.
Этот бензин ежедневно получают пять станций в количествах равных соответственно 110, 90, 120, и 150т бензина. Стоимость перевозок 1т бензина с хранилищ к заправочным станциям задают матрицей:
Составить такой план перевозок бензина, при котором общая стоимость перевозок является минимальной.
2. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ.
m –хранилища, в которых хранятся бензин(i=1,2…m);
Ai– ресурсы в хранилищах;
n – заправочные станции j–ого вида (j=1,2…n);
Bj– заявки АЗС;
CCij– стоимость перевозок 1т бензина из i-го хранилища на j-ую заправочную станцию;
xij– перевозки бензина, т.е. количество бензина перевозимого i-го хранилища в j-ую заправочную станцию;
1.Балансовое ограничение:
2. Плановые ограничения:
(j=1,2…n)
3. Неотрицательность переменных:
xij>=0(4)
4. Целевая функция:
3. ВЫБОР МЕТОДА РЕАЛИЗАЦИИ МОДЕЛИ И ОБОСНОВАНИЕ ВЫБОРА.
Симплекс-метод является универсальным и применим для решения любых задач. Однако существуют некоторые частные типы задач линейСимплекс-метод является универсальным и применим для решения любых задач. Однако существуют некоторые частные типы задач линейного программирования, которые в силу некоторых особенностей своей структуры допускают решение более простыми методами. Для решения моей задачи целесообразно использовать транспортную задачу линейного программирования (ТЗЛП) методом потенциалов.
3.1. Алгоритм решения ТЗЛП методом потенциалом.
1)Строим закрытую модель ТЗЛП, а именно: сумма всех заказов должна равняться сумме всех заявок:
Если соблюдать модель условно, то такая модель называется закрытой.
Если условие не соблюдать, то такая модель ТЗЛП с неправильным балансом.
В этом случае может быть два варианта:
а) ТЗ с избытком запаса
вводим фиктивного потребителя (фиктивный столбец), которым приписываем заявку, равную разности запасов и заявок:
Сiф=0, ( i=1,2…m) – стоимость фиктивных перевозок равна нулю.
Это означает, что если в какой-либо ячейке фиктивного столбца по плану будеЭто означает, что если в какой-либо ячейке фиктивного столбца по плану будет стоять перевозки xij, то фактически эти перевозки останутся не отправленными. Вводят Bфс его заявкой bф,мы уравниваем баланс ТЗ, и теперь эту задачу можно решать как обычную ТЗ.
б) ТЗ с избытком заявок
вводим фиктивного поставщика (фиктивная строка), которым описываем заказчика aф:
Сij=0 (j=1,2…n)
В данном случае мы сводим ТЗ с избытком заявок к ТЗ с правильным балансом, при этом мы не заботились, о справедливости удовлетворения заявок – нас интересовали лишь расходы, которые надо минимизировать.
2)2) Составляем первый опорный план перевозок, в которых обеспечены
m+n-1 базисных клеток, по методу северо-западного угла.
Допустим, план называется опорным, если в нем отличных от нуля не более чем
r=m+n-1 базисных переменных (перевозок), а остальные равны нулю.
План (План (xij) называется оптимальным, если он среди всех допустимых планов приводит к наименьшей стоимости всех перевозок.
Таблица 2.
Транспортная таблица.
|
ПО/ПН
|
B1 |
B2 |
… Bn |
ЗАПАСЫ ai
|
A1
A2
…
Am |
C11
C21
…
Cm1 |
C12
C22
…
Cm2 |
… C1n
… C2n
… …
… Cmn
|
a1
a2
…
am
|
ЗАЯВКИ bJ |
b1 |
b2 |
… bn
|
|
ПН – пункт назначения;
ПО – пункт отправления.
В правых верхних углах каждой ячейки указана стоимоть перевозок из каждого i-ого пункта в каждыйj-ый пункт.
Не учитывая стоимости перевозок и единицы груза, произвоНе учитывая стоимости перевозок и единицы груза, производим удовлетворение потребностей 1-ого потребителя В1за счет запаса поставщика А1, начиная с верхнего левого угла.
Для этого сравниваем а1с b1. Меньший из объемов записываем в клетку А1В1.
Процесс продолжаем до тех пор, пока не удовлетворим всех потребностей за счет запасов. Процесс продолжаем до тех пор, пока не удовлетворим всех потребностей за счет запасов. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце – заявке.
Клетки таблицы, в которых не нулевые перевозки являются базисными, и их число удовлетворяет условию Клетки таблицы, в которых не нулевые перевозки являются базисными, и их число удовлетворяет условию r=m+n-1. Остальные клиенты свободные в них стоят нулевые перевозки, их число равно(n-1)*(m-1).Полученное решение является не только допустимым, но и опорным решением ТЗ.
Если число базисных клеток rm+n-1, то вводим r бесконечно малых фиктивных перевозок, напримерe.
3)Для первого плана строим систему платежей. Предположим, что каждый из пунктов отправления А: вносит за перевозки единицы, к3)Для первого плана строим систему платежей. Предположим, что каждый из пунктов отправления А: вносит за перевозки единицы, какую-то суммуai, какому-то третьему лицу; в свою очередь каждый из пунктов значения Bjтак же вносит за перевозку единицы груза этому же лицу суммуbj.aiиbjназываются платежами . Обозначим сумму этих платежей:
Si,j=ai+bj, (12)
( i=1,2…m, j=1,2…n )
и назовем псевдостоимостью.
Теорема платежей:
Если:
а) для базисных клеток ( xi,j>0)ai+bj=Si,j=Ci,j(псевдостоимость равна стоимости);
б) для свободных клеток ( xi,j0)ai+bj=Si,j>0 (псевдостоимость больше стоимости), то план не является оптимальным.
Если же первое условие выполняется, а второеЕсли же первое условие выполняется, а второе Si,jCi,j, то план является оптимальным и никаким образом улучшен быть не может.
С помощью базисных клеток, в которых сумма этих платежей равна Si,j=Ci,j=ai+bj(i=1,2…m j=1,2…n), а число базисных клеток равно r, то первый платеж значением произвольно (например,a1=0).
4)Находим псевдостоимость для всех свободных ячеек, и если в каждой свободной клеткеSi,jCi,j,то план оптимален и считаем целевую функцию.
5)Если хотябы в одной клетке псевдостоимость больше стоимости, то организовываем цикл пересчета. Метод последовательного улучшения плана перевозок состоит в том, что в таблице отыс5) Если хотябы в одной клетке псевдостоимость больше стоимости, то организовываем цикл пересчета. Метод последовательного улучшения плана перевозок состоит в том, что в таблице отыскивается цикл с отрицательной ценой, по ним перемещаются перевозки и план улучшается до тех пор, пока циклов с отрицательной ценой уже не остается (при каждом шаге заменяют одну свободную переменную на базисную).
4. СИМВОЛЬНАЯ СХЕМА АЛГОРИТМОВ.
Процедура balans.
Процедура north_west_angle.
Процедура PEpsilon.
Процедура psevdostoimost.
Процедура Pmax. Процедура Px1.
Процедура Pschet.
Процедура sravn. Процедура sravn1.
Процедура Px.
Основная программа.
5. КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕГО ПРОГРАМНОГО ОБЕСПЕЧЕНИЯ.
В данной курсовой работе использовалась ЭВМ –IBM PC в состав которой входят:
1.Системный блок с пороцессором Intel Pentium II с тактовой частотой 300 MHz, оперативной памятью 64Мb, с видеоадаптером ATI 3D RAGE PRO и винчестеромWestern digital объемом 4 Gb.
2.Клавиатура типа IBM PS/2.
3.Манипулятор типа “ Microsoft Inteli Mouse ”.
4.Мониор SVGA SONY “ Trinitron “.
5.Принтер HP DeskJet 400 Color.
6. ОБОСНОВАНИЕ ВЫБОРА ЯЗЫКА ПРОГРАММИРОВАНИЯ.
Для реализации данной программы был выбран Турбо Паскаль – универсальный язык программирования высокого уровня.
Как известно, в настоящее время наиболее распространенным алгоритмическим языком является Паскаль. Именно этот язык иКак известно, в настоящее время наиболее распространенным алгоритмическим языком является Паскаль. Именно этот язык используется практически на всех действующих вычислительных системах – от супер ЭВМ до персональных компьютеров.
Турбо Паскаль 7.0 разработан фирмой Borland.Это последняя версия позволила объединить в рамках единой системы мощный алгоритмический потенциал языка, методы объектно-ориентированного программирования, Турбо Паскаль 7.0 разработан фирмой Borland.Это последняя версия позволила объединить в рамках единой системы мощный алгоритмический потенциал языка, методы объектно-ориентированного программирования, современную графику, удобные средства тестирования и отладки программ, а также обеспечить дружественный интерфейс с пользователями.
Турбо Паскаль способствует внедрению современной технологии программирования, основанной на принципах структурного программирования и пошаговом методе проектирования программ.
ЭтоЭтот язык программирования очень удобен для использования в различных приложениях, в том числе для решения задач вычислительного и логического характера, символьной обработки и системного программирования.
Турбо Паскаль – это строго типизированный язык. Развитая система типов позволяет легко разрабатывать адеквТурбо Паскаль – это строго типизированный язык. Развитая система типов позволяет легко разрабатывать адекватные представления для структур данных любой решаемой задачи. В тоже время существующие в Турбо Паскале средства преобразования типов дают возможность гибко манипулировать различнымиданными.
Основные операторы языка являются хорошей иллюстрацией базовых управляющих конструкций структурного программировОсновные операторы языка являются хорошей иллюстрацией базовых управляющих конструкций структурного программирования. Их использование позволяет записывать сложные алгоритмы обработки данных в компактной форме.
Большую помощь программистам оказывает библиотека стандартных программ Турбо Паскаля. Эта библиотека модернизируется и пополняется уже более 5 лет. В нее входят средства для работы с оперативной и внешней памятью, кБольшую помощь программистам оказывает библиотека стандартных программ Турбо Паскаля. Эта библиотека модернизируется и пополняется уже более 5 лет. В нее входят средства для работы с оперативной и внешней памятью, клавиатурой, дисплеем и другими внешними устройствами ПЭВМ.
Система программирования Турбо Паскаля поддерживает модульный принцип программирования, который лежит в основе всех современных технологий разработки программ. Программа написанная на Турбо Паскале, обычно разбивается на модули, а те, в свою очередь, состоСистема программирования Турбо Паскаля поддерживает модульный принцип программирования, который лежит в основе всех современных технологий разработки программ. Программа написанная на Турбо Паскале, обычно разбивается на модули, а те, в свою очередь, состоят из подпрограмм.
Поддержка, оказываемая пользователю на всех этапах разработки программ, обеспечивается во многом благодаря развитой системе справочной информации. Придусмотренно широкое использование манипулятора мыши, выделение различных синтаксических единиц языка разными цветами. В среду встроен многоПоддержка, оказываемая пользователю на всех этапах разработки программ, обеспечивается во многом благодаря развитой системе справочной информации. Придусмотренно широкое использование манипулятора мыши, выделение различных синтаксических единиц языка разными цветами. В среду встроен многофункциональный отладчик, позволяющий проводить пошаговое выполнение программы, генерировать условные и безусловные точки остановок. Общепризнанно, что среда системы программирования ТП играет роль эталона для программных продуктов этого типа.
Опираясь на все вышесказанное, можно утверждать, что система программирОпираясь на все вышесказанное, можно утверждать, что система программирования ТП еще много лет будет незаменимым инструментом и полезным партнером для многих из тех, кто программирует на универсальных алгоритмических языках.
7. РЕШЕНИЕ ЗАДАЧИ-ТЕСТА ДЛЯ НАПИСАНИЯ И ОТЛАДКИ ПРОГРАММЫ.
Составим математическую модель задачи. Будем считать, что iСоставим математическую модель задачи. Будем считать, что i-ый тип станков занят изготовлением j-го вида тканей xi,jст./час. Тогда переменные xi,jдолжны удовлетворять следующим условием:
ix11+x12+x13+x14=180
ix21+x22+x23+x24=350 (1)
ix31+x32+x33+x34=20
ix11+x12+x13=110
ix21+x22+x23=90 (2)
ix31+x32+x33=120
ix41+x42+x43=80
ix51+x52+x53=150
Переменные должны удовлетворять условию неотрицательности:
xi,j0 ( i=1,2…m, j=1,2…n ) (3)
Среди всех возможных значений неизвестных, не удовлетворяющих условие (1), (2) и (3), требуется найти такое, при котором линейная функция: Fmin=7x11+12x12+4x13+6x14+5x15+x21+8x22+6x23+5x24+3x25+6x31+13x32+8x33+
+7x34+4x35, примет наименьшее значение.
Так как полученная задача имеет открытую модель, а именно:
Поэтому, согласно условию (8), чтобы найти ее решение, считаем, что имеется фиктивная потребность в тканях, на выработку которых необходимо затратить:
Полученную задачу решаем методом потенциалов:
1 итерация
|
ПО/ПН
|
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
ai |
А1 |
77
110 |
1212
70 |
104
|
9 6 |
75
|
180 |
0 |
А2 |
31
|
88
20
|
66
120 |
5 5
80
|
33
130 |
350 |
-4 |
А3 |
46
|
9 13 |
7 8 |
6 7 |
4 4
20
|
20 |
-3 |
bj |
110 |
90 |
120 |
80 |
150 |
550
|
|
|
bj
|
7 |
12 |
10 |
9 |
7 |
|
|
