Математические методы и языки программирования симплекс метод
Приложение 3
ЛИСТИНГ РЕЗУЛЬТАТОВ ПРОГРАММЫ Simplex Method
C Б H X1 X2 X3
X4 X5 X6 X7 Y1 Y2
0.00 X5
760.00 1.20 1.80
2.40 0.00 1.00
0.00 0.00 0.00 0.00
0.00 X6
600.00 2.40 0.00 1.20
2.40 0.00 1.00 0.00
0.00 0.00
0.00 X7
480.00 0.00 1.20 1.20
1.20 0.00 0.00 1.00
0.00 0.00
+M Y1 0.00 1.00
-2.00 0.00 0.00 0.00
0.00 0.00 1.00 0.00
+M Y2 0.00 0.00 0.00 1.00 -4.00 0.00 0.00
0.00 0.00 1.00
0.00 1.00 -2.00
1.00 -4.00 0.00 0.00
0.00 0.00 0.00
Ключевой столбец: 3 Ключевая
строка: 5
C Б H X1 X2
X3 X4 X5 X6 X7 Y1
0.00 X5
760.00 1.20 1.80 0.00
9.60 1.00 0.00 0.00
0.00
0.00 X6
600.00 2.40 0.00 0.00
7.20 0.00 1.00 0.00
0.00
0.00 X7
480.00 0.00 1.20 0.00
6.00 0.00 0.00 1.00 0.00
+M Y1 0.00 1.00
-2.00 0.00 0.00 0.00
0.00 0.00 1.00
-1.00 X3
0.00 0.00 0.00 1.00
-4.00 0.00 0.00 0.00
0.00
0.00 1.00 -2.00
0.00 0.00 0.00 0.00
0.00 0.00
Ключевой столбец: 1 Ключевая
строка: 4
C Б H X1 X2 X3 X4 X5
X6 X7
0.00 X5
760.00 0.00 4.20 0.00
9.60 1.00 0.00 0.00
0.00 X6
600.00 0.00 4.80 0.00
7.20 0.00 1.00 0.00
0.00 X7
480.00 0.00 1.20 0.00
6.00 0.00 0.00 1.00
-1.00 X1
0.00 1.00 -2.00 0.00
0.00 0.00 0.00 0.00
-1.00 X3
0.00 0.00 0.00 1.00
-4.00 0.00 0.00 0.00
0.00 0.00 3.00
0.00 5.00 0.00 0.00
0.00
Ключевой столбец: 4 Ключевая
строка: 1
C Б H X1 X2
X3 X4 X5 X6 X7
-1.00 X4
79.17 0.00 0.44 0.00
1.00 0.10 0.00 0.00
0.00 X6
30.00 0.00 1.65 0.00
0.00 -0.75 1.00 0.00
0.00 X7
5.00 0.00 -1.43 0.00
0.00 -0.63 0.00 1.00
-1.00 X1
0.00 1.00 -2.00 0.00 0.00 0.00 0.00
0.00
-1.00 X3
316.67 0.00 1.75 1.00
0.00 0.42 0.00 0.00
-395.83 0.00 0.81 0.00 0.00
-0.52 0.00 0.00
Ключевой столбец: 2 Ключевая
строка: 2
C Б H X1 X2
X3 X4 X5 X6 X7
-1.00 X4
71.21 0.00 0.00 0.00
1.00 0.30 -0.27 0.00
-1.00 X2
18.18 0.00 1.00 0.00
0.00 -0.45 0.61 0.00
0.00 X7
30.91 0.00 0.00 0.00 0.00 -1.27
0.86 1.00
-1.00 X1
36.36 1.00 0.00 0.00
0.00 -0.91 1.21 0.00
-1.00 X3
284.85 0.00 0.00 1.00
0.00 1.21 -1.06 0.00
-410.61 0.00 0.00
0.00 0.00 -0.15 -0.49
0.00
В 5 -й итерации было получено
оптимальное решение
т.к. при исследовании на МИНИМУМ индексная строка не содержит положительных
элементов.
При этом:
Fmax= 410.61
X4= 71.21
X2= 18.18
X7= 30.91
X1= 36.36
X3= 284.85
Курсовой
проект.
Тема:
Вариант 10.
СОДЕРЖАНИЕ: Введение 1. Экономическая постановка задачи.. 2. Математическая постановка задачи.. 3. Выбор метода реализации модели. Обоснование выбора.. 4. Схема алгоритма и его описание. 5. Краткая характеристика ЭВМ и ее программного обеспечения. 6. Обоснование выбора языка программирования. 7. Решение задачи-теста для написания и отладки программы. 8. Анализ полученных результатов. 9. Инструкции пользователю и описание программы. Заключение. Литература. Приложение. 3 4 5 6 10 12 15 16 19 20 21 22 23
ВВЕДЕНИЕ
Проникновение
математики в экономическую науку
связано с преодолением значительных трудностей. В этом отчасти была
"повинна" математика,
развивающаяся на протяжении нескольких веков в основном в связи с потребностями
физики и техники. Но главные
причины лежат все же в природе экономических процессов, в специфике экономической
науки.
Большинство объектов, изучаемых экономической
наукой, может быть охарактеризовано кибернетическим понятием сложная система.
Наиболее распространено понимание системы как
совокупности элементов, находящихся во взаимодействии и образующих некоторую
целостность, единство. Важным
качеством любой системы является эмерджентность - наличие таких свойств,
которые не присущи ни одному из элементов, входящих в систему. Поэтому при изучении систем недостаточно
пользоваться методом их расчленения на
элементы с последующим изучением
этих элементов в отдельности. Одна из трудностей экономических исследований - в
том, что почти не существует экономических объектов,
которые можно было бы
рассматривать как отдельные
(внесистемные) элементы.
Сложность
системы определяется количеством входящих в нее элементов, связями между этими
элементами, а также взаимоотношениями между
системой и средой.
Экономика страны обладает всеми признаками очень сложной системы. Она объединяет огромное число
элементов, отличается многообразием
внутренних связей и связей с другими системами (природная среда,
экономика других стран и т.д.).
В народном хозяйстве взаимодействуют
природные, технологические, социальные процессы, объективные и субъективные
факторы.
Сложность
экономики иногда рассматривалась как
обоснование невозможности ее моделирования, изучения средствами математики. Но такая точка зрения в принципе
неверна. Моделировать можно объект любой природы и любой сложности. И как раз сложные объекты представляют
наибольший интерес для моделирования; именно здесь моделирование может дать
результаты, которые нельзя
получить другими способами исследования.
Потенциальная
возможность математического моделирования любых экономических объектов и
процессов не означает, разумеется, ее
успешной осуществимости при данном уровне экономических и математических
знаний, имеющейся конкретной информации и вычислительной технике. И хотя нельзя указать абсолютные границы
математической формализуемости экономических проблем, всегда будут
существовать еще неформализованные
проблемы, а также ситуации, где
математическое моделирование недостаточно эффективно.
2. ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ
Цеху, располагающему тремя видами металлорежущего оборудования, планируется изготовить
в течении определенного периода времени два изделия, причем первое изделие
комплектуется на двух деталях А1 и А2, которые должны изготовляться в
соответствии 2:1.
Второе изделие также
комплектуется на двух деталях А3 и А4, которые изготовляются соответственно в
соотношении 4:1
Эффективные фонды времени
работы оборудования и нормы штучно-калькуляционного времени, требуемые на
изготовление каждой детали на соответствующем оборудовании, приведены в таблице
2.1:
Таблица 2.1 Детали Группы оборудования А1 А2 А3 А4 Эффективный фонд времени Нормы трудоемкости I 1.2 1.8 2.4 0 768 II 2.4 0 1.2 2.4 600 III 0 1.2 1.2 1.2 480
Определить производственную программу выпуска
деталей А1, А2, А3, А4 при обеспечении заданной комплектности, а также
максимально возможную загрузку наличных производственных мощностей.
3. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА
ЗАДАЧИ
Общая модель:
m(i=1,2..m) - группы оборудования на цехе.
Ai - ресурсы
по i-ой группе оборудования.
n(j=1,2..n) - виды деталей.
ai,j - нормы трудоемкости
затраченных на i-м
виде оборудования на изготовление единицы j-го
вида продукции.
Xj - выпуск
продукции j-го
вида в оптимальном плане.
Kr - Соотношение
деталей в изделии.
Система
ограничений:
1. Ресурсные ограничения:
n
å
a i j
* x j £ A i (i=1,2,..,m)
j=1
2. Реальность плана выпуска:
Xj ³ 0
3. Ограничение по комплектности:
Xk
Kl (k=1,2,…,l); (r=1,2,….,p)
Xr
Kp
Целевой функционал:
n
Fmax = å Xj
j=1
3. ВЫБОР МЕТОДА РЕАЛИЗАЦИИ МОДЕЛИ.
ОБОСНОВАНИЕ
МЕТОДА
Симплекс метод - универсальный метод для решения линейной системы уравнений или
неравенств и линейного функционала.
Для привидения системы
ограничений неравенств к каноническому виду, необходимо в системе ограничений
выделить единичный базис.
I. Ограничения вида «£»- ресурсные ограничения. Справа находится то что мы
используем на производстве, слева - то что получаем. При таких
ограничения вводят дополнительные переменные с коэффициентом «+1», образующие
единичный базис. В целевую функцию эти переменные войдут с коэффициентом
«0».
II. Ограничения вида «=». Часто бывает, что несмотря на то что ограничения
имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом
случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они
входят с коэффициентом «1» , а в целевую функцию с коэффициентом
«M», стремящимся к бесконечности (при Fmin -
«+M», при Fmax - «-M»).
III. Ограничения вида «³» - Плановые ограничения. Дополнительные
переменные (X), несущие определенный экономический смысл - перерасход
ресурсов или перевыполнение плана, перепроизводство, добавляются с
коэффициентом «-1», в целевую функцию - с коэффициентом «0». А
искусственные переменные (Y) как в предыдущем случае.
Алгоритм симплекс метода.
(первая симплекс таблица)
Пусть система приведена к каноническому виду.
X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1
X2+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1
X3+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1
.
Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm
В ней m базисных
переменных, k свободных переменных.
m+k=n - всего переменных.
Fmin= C1X1+ C2X2+ C3X3+....+ CnXn
Все hi должны быть больше либо равны нулю, где i=1,2...m. На
первом шаге в качестве допустимого решения принимаем все Xj=0 (j=m+1,m+2,...,m+k). При этом все базисные переменные
Xi=Hi.
Для дальнейших рассуждений
вычислений будем пользоваться первой симплекс таблицей (таблица 3.1).
Таблица 3.1.
Симплекс таблица. C Б H C1 C2 … Cm Cm+1 … Cm+k X1 X2 … Xm Xm+1 … Xm+k C1 C2 C3 : : Cm X1 X2 X3 : : Xm h1 h2 h3 : : hm 1 0 0 : : 0 0 1 0 : : 0 : : : : : : 0 0 0 : : 0 q1,m+1 q2,m+1 q3,m+1 : : qm,m+1 : : : : : : q1,m+k q2,m+k q3,m+k : : qm,m+k F= F0 D1 D2 … Dm Dm+1 … Dm+k
Первый столбец- коэффициенты в целевой функции при базисных переменных.
Второй столбец - базисные переменные.
Третий столбец - свободные члены (hi³0).
Самая верхняя строка - коэффициенты при целевой функции.
Вторая верхняя строка - сами переменные, входящие в целевую функцию и в
систему ограничений.
Основное поле симплекс
метода - система коэффициентов из уравнения.
Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет».
Для
первой итерации F0= å ci*hi.
D1, D2, D3,..., Dm - оценки
они рассчитываются по формуле:
D j = å ciqij-cj.
Индексная строка позволяет нам судить об оптимальности плана:
1. При отыскании Fmin в индексной строке должны
быть отрицательные и нулевые оценки.
2. При отыскании Fmax в индексной строке должны
быть нулевые и положительные оценки.
Переход ко
второй итерации:
Для этого отыскиваем ключевой
(главный) столбец и ключевую (главную) строку.
Ключевым столбцом
является тот в котором находится наибольший положительный элемент индексной
строки при отыскании Fmin или
наименьший отрицательный элемент при отыскании Fmax.
Ключевой строкой называется та, в которой содержится наименьшее положительное частное
от деления элементов столбца H на соответствующие элементы
ключевого столбца.
На пересечении строки и
столбца находится разрешающий элемент.
На этом этапе осуществляется
к переходу к последующим итерациям.
Переход к итерациям:
1. Выводится базис ключевой
строки, уступая место переменной из ключевого столбца со своим коэффициентом.
2. Заполняется строка вновь
введенного базиса путем деления соответствующих элементов выделенной строки
предыдущей итерации на разрешающий элемент.
3. Если в главной строке
содержится нулевой элемент, то столбец, в котором находиться этот элемент
переноситься в последующую итерацию без изменения.
4. Если в главном столбце
имеется нулевой элемент, то строка, в которой он находиться переноситься без
изменения в последующую итерацию.
5. Остальные элементы
переносятся по формуле:
Метод искусственного базиса.
(Вторая симплекс таблица)
При использовании искусственного базиса необходимо добиваться выхода искусственных
переменных из базиса и введение в него независимых переменных. Для этой цели можно
также использовать симплекс метод, причем решение распадается на две фазы:
I.
Построение
искусственного базиса и оптимизация
функции суммы искусственных переменных, т.е. F0=Y1+Y2+…+Yn = 0 (F®min). Если при этом F0=0, то искусственный базис мы
вывели из состава переменных, переходим ко второй фазе – решаем задачу по
первой симплекс таблице с действительными переменными. Если же F0¹0, т.е. искусственный базис
не выведен из состава переменных – ОЗЛП решений не имеет.
II.
Решение
преобразованной системы ограничений с заданной целевой функцией и действительными
переменными. При этом столбцами искусственных переменных в симплекс методе
пренебрегаем.
Замечания:
1. При решении задач на max с искусственным
базисом следует переходить к решению на min, меняя лишь только целевую
функцию:
Fmax = - Fmin.
2. При решении ОЗЛП с
искусственным базисом особое внимание следует обратить на вычисление элементов
индексных строк.
a) Для
столбцов X вычисление элементов идет по формулам:
D j = å qij.
å yi = y1+y2+…+yR.
åHi=F0.
Примечание: только для
строк Y.
б) Для столбцов Y работает
старая формула:
D j = å ciqij-cj.
1.
СХЕМА АЛГОРИТМА И ЕЕ
ОПИСАНИЕ
1. Начало программы
2.
Процедура
ввода данных
3.
Процедура
привидения к каноническому виду
4.
Процедура
построения симплекс таблицы
5.
Функция
поиска ключевого столбца
6.
Функция
поиска ключевой строки
7.
Проверка
условия: Если в главной строке нулевой элемент.
8.
Процедура
переноса в следующую итерацию главной строки.
9.
Проверка
условия: Если в главном столбце нулевые элементы.
10.
Процедура
переноса столбца в следующую итерацию.
11, 12. Процедура расчета остальных элементов по формуле.
13, 14. Функция исследования на max.
15, 16. Функция исследования на min.
17.
Процедура
вывода оптимального решения.
18.
Конец
программы.
5. КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И
ЕЕ
ПРОГРАМНОГО ОБЕСПЕЧЕНИЯ
Общие
сведения о IBM PC
Когда произносят слова "персональный компьютер", обычно
подразумевается не что иное, как компьютер типа IBM PC. Именно
американская компания IBM в августе 1981 года объявила о выпуске самого первого
компьютера, получившего название
Personal Computer, или просто PC.
Впрочем, еще до
создания IBM PC множеством разных фирм вы пускались компьютеры, которые было
бы вполне уместно называть
персональными. Даже весьма далекая от электроники фирма Coca -
Cola пыталась выпускать собственную модель персонального компьютера!
Несовместимость многочисленных моделей компьютеров была главным препятствием для создания
достаточно совершенных программ универсального применения.
Когда IBM вышла на рынок настольных компьютеров,
казавшийся сомнительным и рискованным, разнобой среди персональных
компьютеров довольно быстро пошел на
убыль. Маленький персональный компьютер IBM
PC на процессоре 8088 фирмы Intel оказался тем долгожданным стандартом,
который с радостью поддержали многочисленные программисты и фирмы - изготовители
прикладного программного обеспечения: наконец - то появился компьютер
солидной фирмы, для
которого можно было разрабатывать
и успешно продавать большими тиражами достаточно сложные, совершенные и универсальные программы. По сути дела,
компьютер IBM PC создал не только стабильный и обширный рынок персональных
компьютеров, но и огромный рынок прикладного программного
обеспечения, на котором за последние
полтора десятилетия разбогатело множество венчурных фирм.
Вот яркий тому пример. Компьютер IBM PC почти с
самого начала работал под управлением дисковой операционной системы DOS,
которую разработала для IBM маленькая и никому тогда не известная
фирма Microsoft. Сегодня Microsoft - бесспорный флагман индустрии
программного обеспечения, одна из богатейших фирм мира, выпускающая не только операционные средства MS - DOS и
Windows для управления компьютерами, но и различные прикладные пакеты. А
основатель и руководитель Microsoft Билл Гейтс, несмотря на молодость, один из самых богатых людей.
Разумеется, персоналка IBM PC оказалась только первым
шагом в верном направлении. Затем фирма
IBM выпустила множество моделей персональных компьютеров XT, AT, PS/2 и
PS/1 на различных процессорах Intel 80286, 80386, 80486, Pentium. Все эти компьютеры
предназначены для работы под управлением
операционных систем DOS,
WINDOW’95, OS/2.
Основной поставщик процессоров для IBM-совместимых компьютеров является фирма INTEL. В последнее время многие другие
фирмы, такие как AMD, CYREX стали
выпускать собственные процессоры, которые полностью совместимы с процессорами
фирмы INTEL.
Фирма AMD
выпускает более дешевые, но не уступающие по качеству, а иногда и превосходящие процессоры (например процессоры серии K6). И многие фирмы, которые
выпускают персональные компьютеры, стали переходить с процессоров фирмы INTEL на процессоры фирмы AMD.
Операционная система MS DOS и
другие
Операционная система - это программа, которая
загружается при включении компьютера. Она производит диалог с
пользователем, посредством команд (каждая команда означает действие, которое
MSDOS должна выполнить), осуществляет
управление компьютером, его ресурсами (оперативной памятью, местом на дисках и
т. д.), выводит информацию на видеомонитор,
запускает другие (прикладные) программы на выполнение. Операционная система обеспечивает
пользователю и прикладным программам
удобный способ общения (интерфейс) с устройствами компьютера. Она
выполняет также различные вспомогательные действия, например
копирование или печать файлов (файл
- это поименованный набор
информации на диске или другом машинном носителе). Все функции по обслуживанию
таблиц размещения файлов, поиску информации в них, выделению
места для файлов на дискетах выполняются операционной системой.
Главным достоинством MS DOS является ее способность управлять устройствами памяти на магнитных
дисках (именно поэтому она названа - дисковая операционная система).
Операционная система
осуществляет загрузку в оперативную память всех программ, передает
им управление в начале их работы, выполняет различные действия по запросу
выполняемых программ и освобождает занимаемую программами
оперативную память при их завершении.
В
настоящее время существуют более современные операционные системы, с гораздо
большим набором возможностей. Это WINDOWS’ 95, OS/2. Но так как эти операционные
системы диктуют пользователю «свои условия», такие как работать в окне,
программы должны иметь стандартные меню и общий вид, многие программисты делают
свои программы по DOS, так как она позволяет более гибко использовать
возможности компьютера.
Рекомендуемая конфигурация для программы SIMPLEX METHOD:
Данной
программе требуется минимальная конфигурация:
Процессор 386
(рекомендуется 486 or high)
1М оперативной
памяти.
2М жесткого
диска.
VGA monitor
6. ОБОСНОВАНИЕ
ВЫБОРА ЯЗЫКА ПРОГРАММИРОВАНИЯ
Язык Borland Pascal
7.0 обладает свойствами использования графики, строковых типов и констант,
любых видов переменных, имеет возможность использования модулей (как уже
существующих, так и созданных пользователями).
Язык Borland Pascal 7.0 - язык высокого уровня, на нем писать программы намного
удобнее так, как языки высокого уровня имеют резервированные слова, которые
замещают ряд кодовых символов на языках низкого уровня. Язык Borland Pascal 7.0
имеет практичный интерфейс, который позволяет быстро и удобно совершить те или
иные действия. Мой выбор остановился на этом языке.
7. РЕШЕНИЕ ЗАДАЧИ ТЕСТА ДЛЯ
НАПИСАНИЯ И ОТЛАДКИ ПРОГРАММЫ
Для нашей конкретной задачи ресурсные ограничения имеют
вид:
1.2X1 + 1.8X2 +
2.4X3 £ 768
2.4X1 + 1.2X3 +
2.4X4 £ 600
1.2X2 + 1.2X3 + 1.2X4 £ 480
Ограничения по комплектности: A1 2 A2 1 A1 = 2A2 A3 4 A4 1 A3 = 4A4
Отсюда составляем систему
уравнений:
X1 - 2X2 = 0
X3 - 4X4 = 0
Итак, система ограничений
задачи состоит из 5 уравнений и целевой функции:
Fmax = X1+X2+X3+X4
Приводим
систему к каноническому виду:
1.2X1 + 1.8X2 +
2.4X3 +X5 £ 768
2.4X1 + 1.2X3 +
2.4X4 +X6 £ 600
1.2X2 + 1.2X3 + 1.2X4 +X7 £ 480
X1 - 2X2 +Y1 = 0
X3 - 4X4 +Y2 = 0
Приводим целевую функцию к каноническому виду:
Fmax = X1+X2+X3+X4 + 0X5+0X6+0X7-My1-My2
Так как введены
искусственные переменные – исследуем на минимум.
Fmin = -X1-X2-X3-X4 - 0X5-0X6-0X7+My1+My2
Таблица 7.1
Симплекс таблица -1 -1 -1 -1 0 0 0 M M C Б H X1 X2 X3 X4 X5 X6 X7 Y1 Y2 0 0 0 M M X5 X6 X7 Y1 Y2 768 600 480 0 0 1.2 2.4 0 1 0 1.8 0 1.2 -2 0 2.4 1.2 1.2 0 1 0 2.4 1.2 0 -4 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 -2 1 -4 0 0 0 0 0 0 0 0 M -1 X5 X6 X7 Y1 X3 768 600 480 0 0 1.2 2.4 0 1 0 1.8 0 1.2 -2 0 0 0 0 0 1 9.6 7.2 6.0 0 -4 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 -2 0 0 0 0 0 0 0 0 0 -1 -1 X5 X6 X7 X1 X3 768 600 480 0 0 0 0 0 1 0 4.2 4.8 1.2 -2 0 0 0 0 0 1 9.6 7.2 6.0 0 -4 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 3 0 5 0 0 0 0 0 -1 -1 -1 X5 X6 X4 X1 X3 0 24 80 0 320 0 0 0 1 0 2.28 3.36 0.2 -2 0.8 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 -1.6 -1.2 0.16 0 0.66 -400 0 2 0 0 0 0 -0.83 -1 0 -1 -1 -1 X2 X6 X4 X1 X3 0 24 80 0 320 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0.43 -1.47 -0.08 0.87 -0.35 0 1 0 0 0 -0.7 1.15 0.3 -1.4 1.22 -400 0 0 0 0 -0.87 0 0.57 -1 0 -1 -1 -1 X2 X7 X4 X1 X3 14.54 20.72 73.63 29.08 294.5 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 -0.45 -1.27 0.3 -0.9 1.21 0.6 0.86 -0.26 1.21 -1.06 0 1 0 0 0 -410 0 0 0 0 -0.15 -0.49 0
Индексная строка при
исследовании на минимум не содержит
положительных элементов, значит, получено оптимальное решение:
Fmax = - Fmin = 410 – максимально возможный выпуск продукции (шт).
X1 = 29, 08 – Детали А1 (шт).
X2 = 14, 54 – Детали А2 (шт).
X3 = 294, 52 – Детали А3 (шт).
X4 = 73, 63 – Детали А4 (шт).
X7 = 20, 72 – Недостающие ресурсы (станко-часы).
8. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ
Решая задачу симплекс методом мы получили:
Детали A1 так относятся к деталям A2, как
2:1, т.е. деталей A1 – 30 штук, а деталей A2 – 15 штук. Соотношение,
поставленное условием задачи, выполнено.
Соотношение между деталями A3 и A4 тоже выполнено. Детали
A3 должны относиться к деталям A4 как 4:1. Это
верно, так как деталей A3 – 292 штуки, а деталей
A4 – 73 штуки.
Но на третьей группе
оборудования идет недоиспользование ресурсов на 20 станко-часов.
Максимально возможная
загрузка имеющегося оборудования – 410 деталей.
При решении с помощью
компьютера получились более точные результаты, которые приблизительно равны
ручным.
9. ИНСТРУКЦИИ ПОЛЬЗОВАТЕЛЮ И
ОПИСАНИЕ
ПРОГРАММЫ
Данная программа используется в графической оболочке
KoSer, которая была написана мною для олимпиады по программированию. Эта
оболочка имеет интерфейс, чем-то напоминающий WINDOWS.
К
данной курсовой работе прилагается инсталляционная дискета с данной оболочкой и
программой SIMPLEX.
Она может быть установлена в двух типах:
-
Для
преподавателя, устанавливается с текстами программ.
-
Для
пользователей, только запускаемые модули.
В любом случае вы запускаете
ТОЛЬКО файл KoSer.EXE. У вас запустится графическая оболочка.
В этой оболочке будут следующие иконки:
-
Simplex Method, это сама программа для решения уравнений.
-
Просмотр
результатов, Чтобы просмотреть результат после решения.
-
Tetris, обычная игра для развлечения.
-
MsDos, Временный выход в DOS
-
Exit, выход из оболочки KoSer.
В программе «Simplex Method» есть кнопки «Добавить строку», «Добавить столбец», «Удалить строку»,
«Удалить столбец», «Рассчитать», «Решить на MAX или MIN», «Решение
ЦЕЛОЧИСЛЕННОЕ или НЕ ЦЕЛОЧИСЛЕННОЕ».
Переход к этим кнопкам
осуществляется клавишей «TAB» или (рекомендуется) с помощью
мышки.
Движение по числовым
значениям уравнения осуществляется стрелками. Ввод чисел производится просто
набором цифр на данной ячейки.
Смена знака осуществляется
клавишей «пробел».
Выход – крестик в верхнем
углу экрана или клавиша «ESC».
ЗАКЛЮЧЕНИЕ
Данная
курсовая работа включает в себя два предмета: «языки программирования» и
«математические методы в экономике».
В курсовой работе были рассмотрены следующие вопросы:
-
Рассмотрен
и дан алгоритм симплекс метода.
-
Дана
краткая характеристика ЭВМ, включая историю появления и описание операционной
системы MSDOS.
-
Рассмотрен
выбор языка программирования.
-
Написана
программа для решения данной и многих других задач.
-
Даны
инструкции пользователю.
Данная
программа была протестирована на очень многих примерах и везде она выдавала
правильные результаты.
Единственное
ограничение, количество столбцов не должно превышать 7 и строк не должно превышать
10.
Программа
считает с точностью 2 знака после запятой.
Список используемой литературы:
1.
Лищенко
«Линейное и нелинейное программирование», 1987
2.
А.Н.
Карасев, Н.Ш. Кремер, Т.Н. Савельева
«Математические методы в
экономике», 1987
ПРИЛОЖЕНИЯ
PROGRAM
SIMPLEX_METOD;
USES
CRT;
LABEL
ZN,ST,ELL,_END;
TYPE MAS=ARRAY[1..30] OF REAL;
MASB=ARRAY[1..30] OF STRING[3];
MASX=ARRAY[1..30,1..30] OF REAL;
VAR
Fo,FunctPr,B,H,Hnew,C,Cnew,CPr,CPrnew,FX:MAS;
X,Xnew:MASX;
BS,Bvsp,ZNAC:MASB;
MIN,I1,I,J,Kx,Ky,Kit,NachKell,NachY,K_st:INTEGER;
PriznacY,KLstr,KLst,ErrCode,Dop_X:INTEGER;
P,P1,Mo,F0,Epsilon,Z:REAL;
VSP,S,PrGomory:STRING;
F:TEXT;
DPx,DPy,Fm,Kell,Kstr:INTEGER;
{ Функция создания
индексов }
FUNCTION
SIMVB(V:INTEGER;S:CHAR):STRING;
VAR M,Z:STRING;
BEGIN
STR(V,M);
Z:=S+M;
SIMVB:=Z;
END;
{ Процедура записи данных
в файл }
PROCEDURE
SAVE(X1:REAL;K:STRING;Mstr:INTEGER);
VAR
V:STRING;
BEGIN
ASSIGN(F,'SIMPLEX.DAT');
APPEND(F);
CASE
Mstr OF
0:WRITELN(F,'');
1:BEGIN
IF K=' ' THEN STR(X1:1:0,V) ELSE
STR(X1:10:4,V);
WRITE(F,V);
WRITE(F,'
');
END;
2:WRITE(F,K);
3:WRITELN(F,K);
END;
CLOSE(F);
END;
{ Определение дополнительных переменных }
PROCEDURE
DOP_PER;
BEGIN
IF ZNAC[I1]='=' THEN
BEGIN
Kell:=Kell+1;Bvsp[Kell]:=SIMVB(DPy,'Y');
DPy:=DPy+1;
Xnew[I1,Kell]:=1;
IF Fm=1 THEN FX[Kell]:=-1 ELSE
FX[Kell]:=1;
FunctPr[Kell]:=1;
FOR I:=1 TO Kstr DO
IF I<>I1 THEN Xnew[I,Kell]:=0;
END;
IF ZNAC[I1]='>=' THEN
BEGIN
Kell:=Kell+1;Bvsp[Kell]:=SIMVB(DPx,'X');
DPx:=DPx+1;Dop_X:=Dop_X+1;
Xnew[I1,Kell]:=-1;FX[Kell]:=0;
FOR I:=1 TO Kstr DO
IF I<>I1 THEN Xnew[I,Kell]:=0;
Kell:=Kell+1;Bvsp[Kell]:=SIMVB(DPy,'Y');
DPy:=DPy+1;
Xnew[I1,Kell]:=1;
IF Fm=1 THEN FX[Kell]:=-1 ELSE
FX[Kell]:=1;
FunctPr[Kell]:=1;
FOR I:=1 TO Kstr DO
IF I<>I1 THEN Xnew[I,Kell]:=0;
END;
IF ZNAC[I1]='<=' THEN
BEGIN
Kell:=Kell+1;Bvsp[Kell]:=SIMVB(DPx,'X');
DPx:=DPx+1;Dop_X:=Dop_X+1;
Xnew[I1,Kell]:=1;FX[Kell]:=0;
FOR I:=1 TO Kstr DO
IF I<>I1 THEN Xnew[I,Kell]:=0;
END;
END;
{ Процедура сокращения Y
}
PROCEDURE
SOKR;
VAR
P:INTEGER;
BEGIN
Kell:=Kell-1;
FOR P:=NachKell+DOP_X TO Kell DO
IF Bvsp[P]=BS[KLstr] THEN BEGIN
FOR J:=P TO Kell DO
Bvsp[J]:=Bvsp[J+1];
FunctPr[J]:=FunctPr[J+1];
Fx[J]:=Fx[J+1];
FOR I:=1 TO Kstr DO
Xnew[I,J]:=Xnew[I,J+1]
END;
END;
{ Процедура, выполняющая
метод Гомори }
PROCEDURE
GOMORY;
VAR
MAX,Z:REAL;
BEGIN
KLstr:=1;
MAX:=H[1]-INT(H[1]);
FOR I1:=2 TO Kstr DO
IF (H[I1]-INT(H[I1]))>=MAX THEN BEGIN
MAX:=H[I1]; KLstr:=I1;END;
Kstr:=Kstr+1;
Hnew[Kstr]:=H[KLstr]-INT(H[KLstr]);
FOR I1:=1 TO Kell DO
BEGIN
Z:=INT(X[KLstr,I1]);
IF X[KLstr,I1]<0 THEN Z:=Z-1;
Xnew[Kstr,I1]:=X[KLstr,I1]-Z;
END;
ZNAC[Kstr]:='>=';
END;
{ Процедура, выполняющая
Симплекс метод }
PROCEDURE
SIMPLEX;
LABEL POVZNAC,NACH;
BEGIN
{ Подготовка к вводу данных }
NachKell:=Kell;
DPx:=Kell+1;DPy:=1;
Kx:=1;Ky:=4;
Epsilon:=0.00001;
CLRSCR;
WRITELN('Введите
систему уравнений:');
WRITELN('(коэффициенты
при всех Х,знак и свободные члены)');
{ Ввод данных }
FOR I:=1 TO Kstr DO
BEGIN
POVZNAC:
WRITELN('Введите ',I,'-е уравнение:');
{ Ввод коэффициентов при X в I-том
уравнении }
FOR J:=1 TO Kell DO
BEGIN
GOTOXY(Kx,Ky);Kx:=Kx+6;
READLN(Xnew[I,J]);
END;
{ Ввод знака в I-том уравнении }
Kx:=Kx+6;GOTOXY(Kx,Ky);READLN(ZNAC[I]);
{Проверка введенного знака на
правильность}
IF (ZNAC[I]<>'>=') AND
(ZNAC[I]<>'=') AND (ZNAC[I]<>'<=')
THEN BEGIN
WRITELN('Неправильно задан знак');
Ky:=Ky+3;Kx:=1;
GOTO POVZNAC;
END;
IF (ZNAC[I]='=') OR (ZNAC[I]='>=') THEN
PriznacY:=1;
{ Ввод свободного члена в I-том
уравнении }
Kx:=Kx+6;GOTOXY(Kx,Ky);READ(B[I]);
Kx:=1;
Ky:=Ky+2;
END;
WRITELN('Введите
коэффициенты при Х в целевой функции:');
{ Ввод коэффициентов при Х в целевой
функции }
FOR J:=1 TO Kell DO
BEGIN
GOTOXY(Kx,Ky);Kx:=Kx+6;
READ(FX[J]);
END;
{ Подготовка индексации X }
FOR
J:=1 TO Kell DO
Bvsp[J]:=SIMVB(J,'X');
{ Определение дополнительных
переменных }
FOR
I1:=1 TO Kstr DO
DOP_PER;
{ Замена оптимальной функции с MAX на
MIN при наличии
в базисе Y-ков если идет
исследование на минимум }
MIN:=0;
IF
(Fm=1) AND (PriznacY=1) THEN
BEGIN
MIN:=Fm;Fm:=2;
FOR J:=1 TO Kell DO
FX[J]:=-FX[J];
END;
{ Сортировка дополнительных
переменных по индексу }
FOR
I1:=NachKell+1 TO Kell DO
FOR J:=I1+1 TO Kell DO
IF Bvsp[J]<Bvsp[I1] THEN
BEGIN
VSP:=Bvsp[J];Bvsp[J]:=Bvsp[I1];Bvsp[I1]:=VSP;
P:=FX[J];FX[J]:=FX[I1];FX[I1]:=P;
P:=FunctPr[J];FunctPr[J]:=FunctPr[I1];FunctPr[I1]:=P;
FOR I:=1 TO Kstr DO
BEGIN
P:=Xnew[I,I1];Xnew[I,I1]:=Xnew[I,J];Xnew[I,J]:=P;
END;
END;
Kit:=1;
CLRSCR;
{ Подготовка столбцов C,B,H }
FOR I:=1 TO Kstr DO
BEGIN
Hnew[I]:=B[I];
FOR J:=NachKell+1 TO Kell DO
IF Xnew[I,J]=1 THEN
BEGIN
BS[I]:=Bvsp[J];
Cnew[I]:=FX[J];
CPrnew[I]:=FunctPr[J];
END;
END;
NACH:;
REPEAT
PriznacY:=0;
{ Передача данных в исходные
переменные c обнулением чисел,
по модулю меньших чем 0.00001 }
FOR
I:=1 TO Kstr DO
BEGIN
IF INT(10000*Hnew[I])=0 THEN H[I]:=+0 ELSE
H[I]:=Hnew[I];
C[I]:=Cnew[I];
CPr[I]:=CPrnew[I];
IF BS[I][1]='Y' THEN PriznacY:=1;
FOR J:=1 TO Kell DO
IF INT(10000*Xnew[I,J])=0 THEN X[I,J]:=+0
ELSE X[I,J]:=Xnew[I,J];
END;
{ Обнуление и вывод индексации
элементов индексной строки }
SAVE(0,' C
Б H ',2);
FOR
J:=1 TO Kell DO
BEGIN
SAVE(0,Bvsp[J],2);
P1:=LENGTH(Bvsp[J]);
IF P1=2 THEN SAVE(0,' ',2);
SAVE(0,' ',2);
Fo[J]:=0;
END;
SAVE(0,'',0);
{ Вывод Симплекс-таблицы }
P1:=0;
FOR
I:=1 TO Kstr DO
BEGIN
IF CPr[I]=1 THEN
IF C[I]<0 THEN SAVE(0,'-M ',2)
ELSE SAVE(0,'+M ',2)
ELSE SAVE(C[I],'',1);
SAVE(0,BS[I],2);
P1:=LENGTH(BS[I]); IF P1=2 THEN SAVE(0,'
',2);
SAVE(0,' ',2);SAVE(H[I],'',1);
FOR J:=1 TO Kell DO
SAVE(X[I,J],'',1);
SAVE(0,'',0);
END;
{ Вычисление значений в индексной
строке }
F0:=0;
FOR
J:=1 TO Kell DO
Fo[J]:=0;
FOR
I1:=1 TO Kstr DO
BEGIN
IF PriznacY=1 THEN
IF BS[I1][1]='Y' THEN
BEGIN
F0:=F0+H[I1];
FOR J:=1 TO Kell DO
Fo[J]:=Fo[J]+X[I1,J];
END;
IF PriznacY=0 THEN
BEGIN
F0:=F0+H[I1]*C[I1];
FOR J:=1 TO Kell DO
Fo[J]:=Fo[J]+C[I1]*X[I1,J];
END;
FOR
J:=1 TO Kell DO
IF Bvsp[J][1]='Y' THEN Fo[J]:=+0
ELSE IF
ABS(Fo[J])<Epsilon THEN Fo[J]:=+0;
END;
{ Вывод значений целевой функции }
SAVE(0,' ',2);SAVE(F0,'',1);
FOR
J:=1 TO Kell DO
BEGIN
IF PriznacY<>1 THEN
Fo[J]:=Fo[J]-FX[J];
SAVE(Fo[J],'',1);
END;
SAVE(0,'',0);
{ Проверка условия оптимальности }
P:=0;
FOR
J:=1 TO Kell DO
IF Fm=1 THEN IF Fo[J]<-Epsilon THEN
BEGIN
P:=1;
CONTINUE;
END ELSE
ELSE IF Fo[J]>Epsilon THEN
BEGIN
P:=1;
CONTINUE;
END;
IF
P<>1 THEN
BEGIN
SAVE(0,'В ',2);SAVE(Kit,' ',1);
SAVE(0,'-й итерации было получено
оптимальное решение',3);
SAVE(0,'т.к. при исследовании на ',2);
IF Fm=1 THEN
SAVE(0,'МАКСИМУМ индексная строка не
содержит отицательных элементов.',3)
ELSE
SAVE(0,'МИНИМУМ индексная строка не
содержит положительных элементов.',3);
FOR I1:=1 TO Kstr DO
IF BS[I1][1]='Y' THEN
BEGIN
SAVE(0,'Но т.к. из базиса не выведены
все Y, то ',3);
SAVE(0,'можно сделать вывод, что
РЕШЕНИЙ НЕТ',3);
HALT;
END;
{ Округление значений массива Х до
целого числа,
если разность округленного и
обычного значений
по модулю меньше чем 0.00001 }
FOR
I:=1 TO Kstr DO
BEGIN
Z:=ROUND(H[I]);
IF ABS(Z-H[I])<Epsilon THEN
H[I]:=ROUND(H[I]);
FOR J:=1 TO Kell DO
BEGIN
IF X[I,J]<0 THEN
Z:=ROUND(X[I,J]);
IF ABS(Z-X[I,J])<Epsilon THEN
X[I,J]:=ROUND(X[I,J]);
END;
END;
{ Проверка целочисленности решения }
P1:=0;
FOR
I:=1 TO Kstr DO
BEGIN
IF INT(10000*FRAC(H[I]))<>0 THEN BEGIN
P1:=1;CONTINUE; END;
FOR J:=1 TO Kell DO
IF BS[I]=Bvsp[J] THEN
FOR I1:=1 TO Kstr DO
IF ABS(FRAC(X[I1,J]))>=Epsilon
THEN BEGIN P1:=1;CONTINUE; END;
END;
{ Составление новой базисной строки
для целочисленного решения }
IF (PrGomory='Y') AND (P1=1) THEN
BEGIN
GOMORY;
NachKell:=Kell;
I1:=Kstr;DPy:=1;
DOP_PER;
BS[Kstr]:=Bvsp[Kell];
CPrnew[Kstr]:=FunctPr[Kell];
Cnew[Kstr]:=FX[Kell];
GOTO NACH;
END;
IF P1=0 THEN SAVE(0,'Данное решение
является целочисленым.',3);
SAVE(0,'При этом:',3);
IF MIN=1 THEN BEGIN F0:=-F0;Fm:=MIN; END;
IF Fm=1 THEN
SAVE(0,'Fmax=',2)
ELSE
SAVE(0,'Fmin=',2);
SAVE(F0,'',1);
SAVE(0,'',0);
FOR I1:=1 TO Kstr DO
BEGIN
SAVE(0,' ',2);
SAVE(0,BS[I1],2);SAVE(0,'=',2);
SAVE(H[I1],'',1);
SAVE(0,'',0);
END;
HALT;
END;
{ Нахождение ключевого столбца }
KLst:=1;Mo:=0;
FOR
J:=1 TO Kell DO
IF Fm=1 THEN
IF Fo[J]<Mo THEN Mo:=Fo[J];
FOR
J:=1 TO Kell DO
BEGIN
IF Bvsp[J][1]<>'Y' THEN
IF Fm=1 THEN
BEGIN
IF Fo[J]<0 THEN
IF Fo[J]>=Mo THEN
BEGIN
Mo:=Fo[J]; KLst:=J;
END;
END
ELSE
BEGIN
IF Fo[J]>0 THEN
IF Fo[J]>=Mo THEN
BEGIN
Mo:=Fo[J]; KLst:=J;
END;
END;
END;
SAVE(0,'Ключевой столбец: ',2);SAVE(KLst,'
',1);
{ Нахождение ключевой строки }
P1:=0;K_st:=0;
FOR
J:=1 TO Kell DO
IF ABS(Mo-Fo[J])<Epsilon THEN
BEGIN
K_st:=K_st+1;
FOR I:=1 TO Kstr DO
IF X[I,KLst]>0 THEN BEGIN
B[I]:=H[I]/X[I,KLst]; P:=B[I];KLstr:=I; END
ELSE BEGIN B[I]:=-1; P1:=P1+1; END;
END;
IF
P1=Kstr*K_st THEN
BEGIN
SAVE(0,'',0);
SAVE(0,'РЕШЕНИЙ НЕТ т.к. невозможно
определить ключевую строку',3);
HALT;
END;
P1:=0;
FOR
J:=1 TO Kell DO
IF ABS(Mo-Fo[J])<Epsilon THEN
FOR
I:=1 TO Kstr DO
IF B[I]>=0 THEN BEGIN
IF B[I]<P THEN IF
Bvsp[KLst]<>BS[I] THEN BEGIN P:=B[I]; KLstr:=I; END;
IF INT(10000*B[I])=INT(10000*P) THEN
IF (BS[I][1]='Y') AND
(BS[KLstr][1]='X') THEN
IF Bvsp[KLst]<>BS[I] THEN
BEGIN P:=B[I]; KLstr:=I; END;
END;
SAVE(0,'Ключевая
строка: ',2);SAVE(KLstr,' ',1);
SAVE(0,'',0);
FOR
I:=1 TO Kstr DO
IF Bvsp[KLst]=BS[I] THEN
BEGIN
SAVE(0,'РЕШЕНИЙ НЕТ т.к. в базисном
столбце уже есть ',3);
SAVE(0,'такая переменная.',3);
HALT;
END;
{ Вызов процедуры сокращения Y }
IF
CPr[KLstr]=1 THEN SOKR;
{ Построение следующей
Симплекс-таблицы }
BS[KLstr]:=Bvsp[KLst];
Cnew[KLstr]:=FX[KLst];
CPrnew[KLstr]:=FunctPr[KLst];
FOR
I:=1 TO Kstr DO
BEGIN
IF I=KLstr THEN
Hnew[I]:=H[I]/X[KLstr,KLst]
ELSE
Hnew[I]:=H[I]-(H[KLstr]*X[I,KLst]/X[KLstr,KLst]);
FOR J:=1 TO Kell DO
BEGIN
IF (I=KLstr) AND (J=KLst) THEN
Xnew[I,J]:=1;
IF (I=KLstr) AND (J<>KLst)
THEN Xnew[I,J]:=X[I,J]/X[KLstr,KLst];
IF (I<>KLstr) AND (J=KLst)
THEN Xnew[I,J]:=0;
IF (I<>KLstr) AND
(J<>KLst) THEN
Xnew[I,J]:=X[I,J]-(X[KLstr,J]*X[I,KLst]/X[KLstr,KLst]);
END;
END;
KLst:=0;KLstr:=0;
Kit:=Kit+1;
UNTIL
(Kit=0);
END;
{ Основная программа }
BEGIN
CLRSCR;
Kit:=0;Dop_X:=0;
ASSIGN(F,'SIMPLEX.DAT');
REWRITE(F);
CLOSE(F);
ST:;
WRITE('Введите кол-во строк:');READLN(Kstr);
IF Kstr>10 THEN
BEGIN
WRITELN('Программа не расчитана на
введенное кол-во строк!');
GOTO ST;
END;
ELL:
WRITE('Введите кол-во
элементов:');READLN(Kell);
IF Kell>10 THEN
BEGIN
WRITELN('Программа не расчитана на
введенное кол-во элементов!');
GOTO ELL;
END;
ZN:
WRITE('Исследуем на МАКСИМУМ(1) или
МИНИМУМ(2):');READLN(Fm);
IF (Fm<>1) AND (Fm<>2) THEN
BEGIN
WRITELN('Введите снова');GOTO
ZN;
END;
WRITE('Целочисленное решение(Y/N):
');READLN(PrGomory);
IF (PrGomory='Y') OR (PrGomory='y') THEN
PrGomory:='Y' ELSE PrGomory:='N';
{ Вызов процедуры SIMPLEX}
SIMPLEX;
END.
Ответы на тесты мэси по математическим методам исследований в экономике. Реализация симплекс метода в случае положительных свободных членов. Курсовая работа по языкам программирования и методам трансляции. Темы курсовых работ по математическому программированию. Курсовая работа по методам искусственного базиса. Симплекс метод подробное описание алгоритма. Алгоритм симплекс метода и его обоснование. Как индексную строку в симплексном методе. Симплекс метод нет положительных элементов. Программа для решения симплекс уравнений. Курсовые работы по методике математики. Симплекс метод математическая модель. Симплекс метод искусственный базис. Языки и методы программирования. Курсовая математические методы.
|
