‚ ваҐе еа Ё«Ёй е Ј®ао祣® Ґ¦Ґ¤Ґў® еа пвбп 180, 350 Ё 20 в. ЎҐ§Ё . ќв®в ЎҐ§Ё Ґ¦Ґ¤Ґў® Ї®«гз ов Їпвм § Їа ў®зле бв жЁ© ў Є®«ЁзҐc⢥ а ў®¬ ᮮ⢥вб⢥® 110, 90, 120, 80, Ё 150 в. ЎҐ§Ё . ‘в®Ё¬®бвм ЇҐаҐў®§®Є 1 в. ЎҐ§Ё б еа Ё«Ёй Є § Їа ў®зл¬ бв жЁп¬ § ¤ ов ¬ ваЁжҐ©. ( 7 12 4 6 5 ) ‘ = ( 1 8 6 5 3 ) ( 6 13 8 7 4 ) ‘®бв ўЁвм в Є®© Ї« ЇҐаҐў®§®Є ЎҐ§Ё ЇаЁ Є®в®а®¬ ®Ўй п бв®Ё¬®бвм ЇҐаҐў®§®Є пў«пҐвбп ¬ЁЁ¬ «м®©.
28
КП.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 – заявки АЗС;
Cij – стоимость перевозок 1т бензина из i-го хранилища на j-ую заправочную станцию;
xij – перевозки бензина, т.е. количество бензина перевозимого i-го хранилища в j-ую заправочную станцию;
Балансовое ограничение:
2. Плановые ограничения:
(j=1,2…n)
3. Неотрицательность переменных:
xij>=0 (4)
4. Целевая функция:
3. ВЫБОР МЕТОДА РЕАЛИЗАЦИИ МОДЕЛИ И ОБОСНОВАНИЕ ВЫБОРА.
Симплекс-метод является универсальным и применим для решения любых задач. Однако существуют некоторые частные типы задач линейного программирования, которые в силу некоторых особенностей своей структуры допускают решение более простыми методами. Для решения моей задачи целесообразно использовать транспортную задачу линейного программирования (ТЗЛП) методом потенциалов.
3.1. Алгоритм решения ТЗЛП методом потенциалом.
Строим закрытую модель ТЗЛП, а именно: сумма всех заказов должна равняться сумме всех заявок:
Если соблюдать модель условно, то такая модель называется закрытой.
Если условие не соблюдать, то такая модель ТЗЛП с неправильным балансом.
В этом случае может быть два варианта:
а) ТЗ с избытком запаса
вводим фиктивного потребителя (фиктивный столбец), которым приписываем заявку, равную разности запасов и заявок:
Сiф=0, ( i=1,2…m) – стоимость фиктивных перевозок равна нулю.
Это означает, что если в какой-либо ячейке фиктивного столбца по плану будет стоять перевозки xij, то фактически эти перевозки останутся не отправленными. Вводят Bф с его заявкой bф, мы уравниваем баланс ТЗ, и теперь эту задачу можно решать как обычную ТЗ.
б) ТЗ с избытком заявок
вводим фиктивного поставщика (фиктивная строка), которым описываем заказчика aф:
Сij=0 (j=1,2…n)
В данном случае мы сводим ТЗ с избытком заявок к ТЗ с правильным балансом, при этом мы не заботились, о справедливости удовлетворения заявок – нас интересовали лишь расходы, которые надо минимизировать.
Составляем первый опорный план перевозок, в которых обеспечены
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 бесконечно малых фиктивных перевозок, например .
Для первого плана строим систему платежей. Предположим, что каждый из пунктов отправления А: вносит за перевозки единицы, какую-то сумму i, какому-то третьему лицу; в свою очередь каждый из пунктов значения Bj так же вносит за перевозку единицы груза этому же лицу сумму j. i и j называются платежами
. Обозначим сумму этих платежей:
Si,j=i+j, (12)
( i=1,2…m, j=1,2…n )
и назовем псевдостоимостью.
Теорема платежей:
Если:
а) для базисных клеток (xi,j>0) i+j=Si,j=Ci,j (псевдостоимость равна стоимости);
б) для свободных клеток (xi,j0) i+j=Si,j>0 (псевдостоимость больше стоимости), то план не является оптимальным.
Если же первое условие выполняется, а второе Si,jCi,j, то план является оптимальным и никаким образом улучшен быть не может.
С помощью базисных клеток, в которых сумма этих платежей равна Si,j=Ci,j=i+j (i=1,2…m j=1,2…n), а число базисных клеток равно r, то первый платеж значением произвольно (например, 1=0).
Находим псевдостоимость для всех свободных ячеек, и если в каждой свободной клетке Si,jCi,j, то план оптимален и считаем целевую функцию.
Если хотябы в одной клетке псевдостоимость больше стоимости, то организовываем цикл пересчета. Метод последовательного улучшения плана перевозок состоит в том, что в таблице отыскивается цикл с отрицательной ценой, по ним перемещаются перевозки и план улучшается до тех пор, пока циклов с отрицательной ценой уже не остается (при каждом шаге заменяют одну свободную переменную на базисную).
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. Это последняя версия позволила объединить в рамках единой системы мощный алгоритмический потенциал языка, методы объектно-ориентированного программирования, современную графику, удобные средства тестирования и отладки программ, а также обеспечить дружественный интерфейс с пользователями.
Турбо Паскаль способствует внедрению современной технологии программирования, основанной на принципах структурного программирования и пошаговом методе проектирования программ.
Этот язык программирования очень удобен для использования в различных приложениях, в том числе для решения задач вычислительного и логического характера, символьной обработки и системного программирования.
Турбо Паскаль – это строго типизированный язык. Развитая система типов позволяет легко разрабатывать адекватные представления для структур данных любой решаемой задачи. В тоже время существующие в Турбо Паскале средства преобразования типов дают возможность гибко манипулировать различными данными.
Основные операторы языка являются хорошей иллюстрацией базовых управляющих конструкций структурного программирования. Их использование позволяет записывать сложные алгоритмы обработки данных в компактной форме.
Большую помощь программистам оказывает библиотека стандартных программ Турбо Паскаля. Эта библиотека модернизируется и пополняется уже более 5 лет. В нее входят средства для работы с оперативной и внешней памятью, клавиатурой, дисплеем и другими внешними устройствами ПЭВМ.
Система программирования Турбо Паскаля поддерживает модульный принцип программирования, который лежит в основе всех современных технологий разработки программ. Программа написанная на Турбо Паскале, обычно разбивается на модули, а те, в свою очередь, состоят из подпрограмм.
Поддержка, оказываемая пользователю на всех этапах разработки программ, обеспечивается во многом благодаря развитой системе справочной информации. Придусмотренно широкое использование манипулятора мыши, выделение различных синтаксических единиц языка разными цветами. В среду встроен многофункциональный отладчик, позволяющий проводить пошаговое выполнение программы, генерировать условные и безусловные точки остановок. Общепризнанно, что среда системы программирования ТП играет роль эталона для программных продуктов этого типа.
Опираясь на все вышесказанное, можно утверждать, что система программирования ТП еще много лет будет незаменимым инструментом и полезным партнером для многих из тех, кто программирует на универсальных алгоритмических языках.
7. РЕШЕНИЕ ЗАДАЧИ-ТЕСТА ДЛЯ НАПИСАНИЯ И ОТЛАДКИ ПРОГРАММЫ.
Составим математическую модель задачи. Будем считать, что i-ый тип станков занят изготовлением j-го вида тканей xi,j ст./час. Тогда переменные xi,j должны удовлетворять следующим условием:
x11+x12+x13+x14=180
x21+x22+x23+x24=350 (1)
x31+x32+x33+x34=20
x11+x12+x13=110
x21+x22+x23=90 (2)
x31+x32+x33=120
x41+x42+x43=80
x51+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 |
i |
| А1 |
7 110 |
12 70 |
4 |
9 6 |
5 |
180 |
0 |
| j |
7 |
12 |
10 |
9 |
7 |
r=m+n-1=7
2 итерация
| ПО/ПН |
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
i |
| А1 |
7 7 110 |
6 12 |
4 4 70 |
3 6 |
1 5 |
180 |
0 |
| j |
7 |
6 |
4 |
3 |
1 |
r=m+n-1=7
3 итерация
| ПО/ПН |
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
i |
| А1 |
7 7 60 |
14 12 |
4 4 120 |
11 6 |
1 5 |
180 |
0 |
| j |
7 |
14 |
4 |
11 |
9 |
r=m+n-1=7
4 итерация
| ПО/ПН |
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
i |
| А1 |
2 7 |
9 12 |
4 120 |
6 60 |
4 5 |
180 |
0 |
| j |
2 |
9 |
4 |
6 |
4 |
В последней итерации план является оптимальным, тюкю в каждой пустой клетке Si,jCi,j.
Используя соотношение (4), для определения оптимального плана исходной задачи, получим матрицу:
Получен оптимальный план:
Fmin=4*120+6*60+1*110+8*90+5*20+3*130+4*20=2240 руб.
8. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ.
Проанализировав полученный результат, согласно плану перевозки бензина предусматриввается перевозить:
а) с первого хранилища 120т бензина на третью заправочную станцию и 60т бензина на четвертую;
б) со второго хранилища 110т бензина на первую заправочную станцию, 90т бензина на вторую, 20т бензина на четвертую и 130т бензина на пятую заправочную станцию;
в) с третьего хранилища 20т бензина на пятую заправочную станцию.
При полученном плане перевозок бензина их стоимость является минимальной и составляет: Fmin=2240 руб.
Все результаты теста-задачи полностью сходятся с полученными результатами машинного счета (смотри приложение).
ЗАКЛЮЧЕНИЕ.
Главной целью данной курсовой работы является нахождение оптимального плана перевозок груза от постовщика к потребителям.
В процессе разработки курсового проэкта была составленна универсальная программа для решения аналогичных задач.
Правильность работы программы определяется с помощью задачи-теста, для проверки правильности работы программы были заданы: количество поставщиков и потребителей, наличие груза, заявки и тарифы перевозок. Результаты были посчитаны в ручную, и их ответы совподают с ответами программы.
В исходную программу могут быть внесены изменения: в описании массива данных увеличить размерность массива и тогда программа будет работать с большим диапозоном данных.
ЛИТЕРАТУРА.
Малик Г.С. “Основы экономики и матемотические методы в планировании”, Москва “Высшая школа”, 1988г.
Акулич И.Л. “Матемотическое программирование в примерах и задачах”, Москва “Высшая школа”, 1986г.
ПРИЛОЖЕНИЕ.