Введение
Под термином«программирование» понимают выбор программных действий для решения задачи.
Математическоепрограммирование представляет собой математическую дисциплину, занимающуюсяизучением экстремальных задач и разработкой методов их решения. В зависимостиот свойств функций раздел математического программирования можно рассматриватькак ряд самостоятельных дисциплин. Задачи математического программированияделятся на задачи линейного и нелинейного программирования.
Задачи нелинейногопрограммирования возникают в естественных и физических науках, техники,экономики, в сфере деловых отношений и в науке управления государством.Преобразование реальной задачи в задачу нелинейного программирования взначительной мере является искусством, направляемым теорией. Теория точноуказывает, какая из многих возможных формулировок задачи решается наиболееэффективно, а какая не может быть решена вовсе [1].
Прежде всего, задачиматематического программирования делятся на линейного и нелинейного программирования.При этом если все функции f и /> линейные, тосоответствующая задача является задачей линейного программирования. Если жехотя бы одна из указанных функции нелинейная, то соответствующая задачаявляется задачей нелинейного программирования.
Наиболее изученнымразделом математического программирования является линейное программирование.Для решения задач линейного программирования разработан целый ряд эффективныхметодов, алгоритмов и программ [2].
Анализ линейногопрограммирования имеет статическое оптимальное решение, по этому, как толькоизменяются исходные условия, полученное решение теряет свою актуальность.Анализ чувствительности задачи линейного программирования как раз и связан сисследованием возможных изменений полученного оптимального решения в результатеизменений исходных данных задачи. Анализ чувствительности – это процесс,который реализуется после того, как получено оптимальное решение [1].
Данная курсовая работапосвящена общему методу решения задач линейного программирования, известномукак симплекс-метод. Процесс решения любой задачи линейного программированиясимплекс-методом имеет итерационный характер: однотипные вычислительные процедурыв определенной последовательности повторяются до тех пор, пока не будет найденооптимальное решение. Информация, которую можно получить с использованиемсимплекс-метода, не ограничивается оптимальным решением. Этот метод позволяетдать экономическую интерпретацию решения.
1. Теоретическая часть
1.1 Общая и основнаязадачи линейного программирования
Общей задачей линейногопрограммирования называется задача, которая состоит в определении максимального(минимального) значения функции
n
L = ∑ cjxj(1.1)
j=1
при условиях
n
∑ aijxj≤ bi (i=1,k) (1.2)
j=1
n
∑ aijxj= bi (i=k+1,m) (1.3)
j=1
xj ≥ 0 (j=1,l ,l ≤ n), (1.4)
где aij, bi, cj – заданные постоянные величины и k ≤ m.
Функция (1.1) называетсяцелевой функцией задачи (1.1) – (1.4), а условия (1.2) – (1.4) – ограничениямиданной задачи.
Стандартной илисимметричной задачей линейного программирования называется задача, котораясостоит в определении максимального значения функции (1.1) при выполненииусловий (1.2) и (1.4), где k=m и l=n.
Канонической или основнойзадачей линейного программирования называется задача, которая состоит вопределении максимального значения функции (1.1) при выполнении условий (1.3) и(1.4), где k=0 и l=n.
Совокупность чисел X=(x1, x2, …, xn), удовлетворяющих ограничениямзадачи (1.2) – (1.4), называется допустимым решением или планом.
План X*=(x1*, x2*,…, xn*), при котором целевая функция задачи (1.1) принимаетсвое максимальное (минимальное), значение, называется оптимальным.
Указанные выше три формызадачи линейного программирования эквивалентны в том смысле, что каждая из нихс помощью несложных преобразований может быть переписана в форме другой задачи.Это означает, что если имеется способ нахождения решения одной из задач, то темсамым может быть определен оптимальный план любой из трех задач
1.1.1 Алгоритмсимплексного метода
Симплексный метод решениязадач линейного программирования основан на переходе от одного опорного плана кдругому, при котором значение целевой функции возрастает (при условии, чтоданная задача имеет опорный план, и когда ее опорный план являетсяневырожденным, причем, целевая функция исследуется на максимум).
Указанный переходвозможен, если известен какой-либо исходный план. Рассмотрим задачу (1.1) — (1.4), где
/>;/>;/>;…; />; />;…;
/>; />.
Так как
/>,
то опорный план согласнопризнаку оптимальности будет иметь вид:
/>
В опорном планеприсутствует (n-m) –нулей. Этот план определяется системой единичных векторов P1,…,Pm, которые образуют базис m-мерного пространства, следовательно, некоторые из векторов /> могут быть представленыв виде линейной комбинации векторов данного базиса. Пусть
/>.
Положим
/>; />/>.
Так как P1,…,Pm являются единичными векторами, то /> и
/> а />, (1.5)
где Δj – критерий остановки, j=/>.
В симплекс методе всерешения связанные с определением оптимальности и выявлением целесообразностиперехода к новому опорному плану принимаются в соответствии с ниже приведеннымитеоремами.
Теорема 1. (Признакоптимальности опорного плана) Опорный план
/>
для задач (1.3), (1.4)является оптимальным, если все оценки
/>.
Теорема 2. (Признакнеограниченности сверху) Если /> для некоторого /> и среди чисел /> нетположительных (/>), то задачи (3), (4) являютсянеограниченными сверху на множестве плана.
Сформулированные теоремыпозволяют проверить, является ли найденный опорный план оптимальным, и выявитьцелесообразность перехода к новому плану.
Исследование опорногоплана на оптимальность, а также дальнейший вычислительный процесс удобнеевести, если условия задачи и первоначальные данные, полученные послеопределения исходного опорного плана, записать в симплексную таблицу (таблица1).
Таблица 1
Симплексная таблицаi базис
Cбаз
P0
С1
С2 …
Cr …
Сm
Cm+1 …
Ck …
Cn
P1
P2 …
Pr …
Pm
Pm+1 …
Pk …
Pn 1
P1
C1
b1 1 … …
a1m+1 …
a1k …
a1n 2
P2
C2
b2 1 … …
a2m+1 …
a2k …
a2n … … … … … … … … … … … … … … … r
Pr
Cr
br … 1 …
arm+1 …
ark …
arn … … … … … … … … … … … … … … … m
Pm
Cm
bm … … 1
amm+1 …
amk …
amn m+1
F0
D1
D2 …
Dr …
Dm
Dm+1 …
Dk …
Dn
В столбце Cбаз записываются коэффициенты при неизвестных целевой функции,имеющие те же индексы, что и векторы данного базиса.
В столбце P0записываются положительные компоненты искомогоопорного плана. В нем же в результате вычислений записываются компонентыопорного плана. Столбцы векторов Pj представляют собой коэффициенты разложения по векторам данного базиса.
В таблице 1.1 первые m строк определяются исходными даннымизадачи, а показатели (m+1)-ой строки вычисляют. В этой строке в столбце вектораP0записывается значение целевой функции, которое онапринимает при данном опорном плане, а в столбце вектора Pj – значение
/>.
Значение F0равно скалярному произведению вектора Р0на вектор сбаз:
/>.
После заполнения таблицы(1.1) исходный опорный план проверяют на оптимальность. Для этого просматриваютэлементы (m+1) – ой строкитаблицы. В результате может иметь место один из следующих трех случаев:
1) Значения Δj больше или равны нулю для всех />;
2) Δjaij;
3) Δj0.
В первом случае наосновании признака оптимальности исходный опорный план является оптимальным. Вовтором случае целевая функция не ограничена сверху на множестве планов, а втретьем случае можно перейти от исходного плана к новому опорному плану, прикотором значение целевой функции увеличится. Этот переход от нового опорногоплана к другому осуществляется исключением из исходного базиса какого-нибудь извекторов и введением в него нового вектора, исходя из максимальной абсолютнойвеличины отрицательных чисел Δj. Если таких чисел несколько, то в базис вводитсявектор, имеющий тот же индекс, что и максимум из чисел cj, где Δj
Пусть />, остальные Δj³ 0, следовательно, в базис вводится вектор Pk. Для того чтобы определить вектор,подлежащий исключению из базиса, находим минимальное значение отношения: />.
Пусть это достигается длянекоторого i=r. Тогда из базиса исключается вектор Рr, а число ark называют разрешающим (генеральным)элементом. Столбец и строку, на пересечении которых находится элемент ark называют направляющими(генеральными).
После выделениянаправляющей строки и направляющего столбца находят новый опорный план икоэффициенты разложения векторов Рj через векторы нового базиса, соответствующего новомуопорному плану. Положительные компоненты нового опорного плана вычисляются поформулам:
/>(1.6)
/>(1.7)
После вычисления aijиbi согласно формулам (1.6) и (1.7) ихзначения заносят в новую таблицу. Элементы (m+1)-ой строки вычисляются на основе их определения. Послезаполнения новой симплекс-таблицы просматривают элементы (m+1)-ой строки. Если все />≥0, тоновый опорный план является оптимальным. Если же среди указанных чисел имеютсяотрицательные, то, используя описанную выше последовательность действий,находят новый опорный план. Этот процесс продолжают до тех пор, пока либо неполучают оптимальный план задачи, либо не устанавливают ее неразрешимость
1.2 Двойственная задачалинейного программирования
Каждойзадаче линейного программирования можно определенным образом сопоставитьнекоторую другую задачу (линейного программирования), называемую двойственнойили сопряженной по отношению к исходной (прямой) задаче.
Рассмотримследующую задачу линейного программирования.
/>(1.8)
приусловиях
/>(1.9)
/>(1.10)
Определение. Задача, состоящая в нахождении минимального значенияфункции
/>(1.11)
при условиях
/>(1.12)
/>(1.13)
называется двойственной по отношению к задаче (1.8)–(1.10).
Задачи (1.8)–(1.10) и (1.11)–(1.13) образуют пару задач,называемую в линейном программировании двойственной парой.
1.2.1 Правила составлениядвойственной задачи
Двойственная задача по отношению к исходной составляетсясогласно следующим правилам:
Целевая функция исходной задачи (1.8)–(1.10) исследуется намаксимум, а целевая функция двойственной (1.11)–(1.13) –на минимум.
/>
Матрица, составленная из коэффициентов при неизвестных всистеме ограничений (1.9) исходной задачи (7.1)–(7.3), и аналогичная матрица вдвойственной задаче (1.8)–(1.10) получаются друг из друга транспонированием(т.е. заменой строк столбцами, а столбцов – строками).
/>
Число переменных в двойственной задаче (1.11)–(1.13) равночислу соотношений в системе (1.9) исходной задачи (1.8)–(1.10), а числоограничений в системе (1.12) двойственной задачи–числу переменных в исходнойзадаче.
Коэффициентами при неизвестных в целевой функции (1.11)двойственной задачи (1.11)–(1.13) являются свободные члены в системе (1.9)исходной задачи (1.8)–(1.10) а правыми частями в соотношениях системы (1.12)двойственной задачи – коэффициенты при неизвестных в целевой функции (1.8)исходной задачи.
Если переменная />, исходной задачи (1.8)–(1.10)может принимать только лишь положительные значения, то j-е условие в системе(1.12) двойственной задачи (1.11)–(1.13) является неравенством вида «/>». Если жепеременная /> можетпринимать как положительные, так и отрицательные значения, то j-е соотношение всистеме (1.12) представляет собой уравнение. Аналогичные связи имеют местомежду ограничениями (7.2) исходной задачи (1.8)–(1.10) и переменнымидвойственной задачи (1.11)–(1.13), т.е. если i-е соотношение в системе (1.9)исходной задачи является неравенством, то i-я переменная двойственной задачи />. В противномслучае переменная /> может принимать какположительные, так и отрицательные значения.
1.2.2 Правила анализа на чувствительность двойственной оценки
Всякое изменение исходных данных прямой задачи может оказатьвлияние, как на ее оптимальный план, так и на систему оптимальных двойственныхоценок. Поэтому, чтобы проводить экономический анализ с использованиемдвойственных оценок, нужно знать их интервал устойчивости.
Рассмотрим пару двойственных задач.
Исходная задача: найти максимум функции
/>(7.7)
при условиях
/>/> (7.8)
/> (7.9)
Двойственная задача: найти минимум функции
/>(7.10)
при условиях
/>/>(7.11)
Предположим, что задача (7.7)–(7.9) имеет невырожденныеопорные планы и хотя бы один из них является оптимальным.
Максимальное значение целевой функции (7.7) задачи(7.7)–(7.9) будем рассматривать как функцию свободных членов системы линейныхуравнений (7.8): />.
Теорема. В оптимальномплане двойственной задачи (7.10), (7.11) значение переменной /> численно равно частнойпроизводной функции /> по данному аргументу, т. е.
/>(7.12)
Последнее равенство означает, что изменение значений величин /> приводит кувеличению или уменьшению />. Это изменение /> определяется величиной /> и может бытьохарактеризовано лишь тогда, когда при изменении величин /> значения переменных /> в оптимальномплане соответствующей двойственной задачи (7.10), (7.11) остаются неизменными.Поэтому представляет интерес определить такие интервалы изменения каждого из свободныхчленов системы линейных уравнений. (7.8), в которых оптимальный пландвойственной задачи (7.10), (7.11) не меняется. Это имеет место для всех техзначений />,при которых столбец вектора /> последней симплекс-таблицырешения задачи (7.7)–(7.9) не содержит отрицательных чисел, т. е. тогда, когдасреди компонент вектора нет отрицательных. Здесь /> — матрица, обратная матрице В,составленной из компонент векторов базиса, который определяет оптимальный планзадачи (7.7)–(7.9).
/>
Таким образом, если найдено решение задачи (7.7)–(7.9), тонетрудно провести анализ устойчивости двойственных оценок относительноизменений />.Это, в свою очередь, позволяет:
1. проанализировать устойчивость оптимального плана задачи(7.10), (7.11) относительно изменений свободных членов системы линейныхуравнений (7.8),
2. оценить степень влияния изменения />, на максимальное значение целевойфункции задачи (7.7)–(7.9), что дает возможность определить наиболеецелесообразный вариант возможных изменений />.
Вывод
В теоретической частипояснительной записки к курсовой работе приведен краткий теоретический материало формах представления задач линейного программирование, симплексный метод иметод двойственной задачи, необходимый для решения задач линейногопрограммирования.
линейныйсимплекс программирование двойственный
2. Практическая часть
2.1 Постановка задачи
Для изготовления трехвидов продукции грузовик, легковой автомобиль и мотоцикл игрушечная фабрикаиспользует три вида продукции, их наличие в распоряжении предприятия, а так жецена единицы продукции приведены в таблице 2
Таблица 2
Исходные данные№ Вид сырья Нормы затрат сырья Наличие ресурса A B C 1 грузовик 1 1 1 430 2 Легковой автомобиль 3 2 460 3 мотоцикл 1 4 420 4 Цена ед. продукции 3 2 5
Требуется:
сформулироватьдвойственную задачу и найти оптимальные планы прямой и двойственной задачи.
найти интервалыустойчивости двойственных оценок по отношению к изменениям ресурсов каждоготипа.
выявить изменения общейстоимости изготовляемой продукции, определяемой оптимальным планом еепроизводства при уменьшении количества ресурса I типа на 130 единиц и увеличения количества ресурсов II и III типа на 120 и 110 единиц.
Провести анализвозможного изменения общей стоимости продукции как при изменении объемовкаждого из ресурсов по отдельности, так и при одновременном изменении вуказанных размерах.
2.2 Математическая модельисходной задачи
Пусть xj – количество изделий j –го вида;aij – затраты времени на единицупродукции вида j на оборудовании i-го типа, cj – стоимость единицы изделия вида j, si – общий фонд рабочего времени наоборудовании типа i.
Целевая функция:
L = 3x1 + 2x2 + 5x3 → max
Ограничения:
/>x1 +x2 +x3 + x4=430
3x1 + 2x3 + x5 = 46
/>x1 + 4x2 +x6 =420
xj ≥ 0, j = 1,6
Составляется матрица изкоэффициентов при неизвестных в системе ограничений исходной задачи.
А=/>
2.3 Математическая модельдвойственной задачи
Число переменных в двойственной задаче равно числу уравненийв системе исходной задачи, т. е. равно семи.
Целевая функция исходной задачи исследуется на максимум, асистема условий содержит только уравнения. Поэтому в двойственной задачецелевая функция исследуется на минимум, а ее переменные могут принимать любыезначения (в том числе и отрицательные). Следовательно, для исходной задачидвойственная задача такова:
Найти минимум функции:
/>
Ограничения:
/>
И составляетсяаналогичная матрица, которая получается транспонированием (т.е. заменой строкстолбцами, а столбцов – строками).
АТ=/>
2.4 Нахождение решенияисходной задачи
Задача записывается вформе основной задачи линейного программирования.
Целевая функция:
L = 3x1 + 2x2 + 5x3 → max
Ограничения:
/>x1 +x2 +x3 + x4=430
3x1 + 2x3 + x5 = 46
/>x1 + 4x2 +x6 =420
xj ≥ 0, j = 1,6
Сначала проверяется,можно ли решить задачу симплексным методом:
m
Таблица 3
Симплекс-таблица (1-аяитерация)i Базис
/>
/>
/>
/>
/>
/>
/>
/> 1
/> 430 1 1
1 1 2
/>
460
3
2
1 3
/> 420 1 4 1 m+1 -3 -2 -5
В (m+1)-ой строке находится максимальнаяпо абсолютной величине оценка ∆j=∆3= — 8. Таким образом, столбец Р3является генеральным. Среди элементов ai1находится такой, который соответствует минимальному значению bi / ai1. Это элемент a21. Таким образом, 2-ая строка является генеральной. Все элементыbi и aij пересчитываются соответственно поформулам (1.6) и (1.7). Новые данные заносятся в таблицу 4.
Таблица 4
Симплекс-таблица (2-аяитерация)i Базис
/>
/> 3 2 5
/>
/>
/>
/>
/>
/> 1
/> 220 -1/2
1 1 -1/2 2
/>
5
230
3/2
1/2 3
/> 420 1
4 1 m+1 1150 9/2
-2 5/2
Новый опорный план: X =(0,0,230,220,0,420). Не все оценки ∆j ≥ 0. Находятся генеральныестрока и столбец. Это столбец Р2 и 2-я строка. Все элементы bi и aij пересчитываются соответственно поформулам (1.6) и (1.7). Новые данные заносятся в таблицу 5.
Таблица 5
Симплекс-таблица (3-аяитерация)i Базис
/>
/> 3 2 5
/>
/>
/>
/>
/>
/> 1
/> 230 -3/4 1 -1/2 -1/4 2
/> 5 230 3/2 1 1/2 3
/> 2 105 1/4 1 1/4 m+1 1360 5 5/2 1/2
В (m+1)-ой строке все оценки ∆j ≥ 0. Найденный план X*=(0,230,0,230, 0,105,) является оптимальным.
Из данной симплекснойтаблицы видно, что оптимальным планом производства изделии является такой план,при котором изготавливается 230 изделии вида С и 105 изделии вида B при данном плане производства, общаястоимость изделии равна 1360 денежных единиц.
2.5 Нахождение решениядвойственной задачи
2.5.1 Нахождениеинтервалов устойчивости двойственной оценки по отношению к изменениям ресурсовкаждого типа
/>
/> обратная матрицы В составленная изкомпонентов векторов />,/>,/>базиса, который определяет оптимальный план задачи взятыхиз столбцов векторов />,/>,/>образующий первоначальный единичный базис
/>
/> />
/>
/>=/>*/>=/>
если
/> />
/>
Очевидно если /> /> это означает, что если количество ресурсов I типа будет увеличено в пределах555, то несмотря на это оптимальным планом двойственной задачи остаётся план Y(0;5/2:1/2).
Далее если
/> /> />
если
/> /> />
если III тип ресурсапринадлежит соответственно />, а количество остальных ресурсов остаетсяпервоначальным, то двойственная задача имеет один и тот же план.
2.5.2 Выявление измененийобщей стоимости изготовляемой продукции, определяемый оптимальным планом еепроизводства при уменьшении количества ресурса
В данной задачеодновременно изменяется количество ресурсов всех трех типов.
При этом количестворесурса I типа уменьшается -130, II и III ресурсы увеличивается на 120 и 110 денежных единиц.
Следовательно выяснитьостается ли /> оптимальным планом двойственнойзадачи при указанном изменении количества ресурсов или нет. Для этого подставимв неравенство вместо
/> />/>
/>
Следовательно, несмотряна изменения объем ресурсов в указанных размерах. Оптимальным планомдвойственной задачи остается />. Данное заключение позволяет воспользоваться равенством
/> денежных единиц
Это означает, чтоуменьшение количества ресурсов I типана 130 единиц и увеличение ресурсов II и III типов на 120 и 110 единиц квозможности построения такого плана производства продукции, реализация которогообеспечит выпуск изделии на 355 денежных единиц больше, чем при планепроизводства продукции, обусловленным первоначальным количеством ресурсов.Уменьшение количества ресурсов на 130 не позволяет на изменение max значения функции, в то время какувеличение ресурсов II и III типов на 120и 110 единиц приведёт кувеличению max значения функции соответственно
/> ./>
2.5.3 Экономическаяинтерпретация двойственных оценок
Экономическую интерпретацию двойственных задач и двойственныхоценок рассмотрим по таблице 2, где оптимальным решением двойственной задачиявляется
/>, />; />.
Переменные /> и /> обозначают условные двойственныеоценки единицы сырья, соответственно II и III видов. Эти оценки отличны отнуля, а сырье II и III видов полностью используется при оптимальном планепроизводства продукции. Двойственная оценка единицы сырья I вида равна нулю.Этот вид сырья не полностью используется при оптимальном плане производствапродукции.
Таким образом, положительную двойственную оценку имеют лишьте виды сырья, которые полностью используются при оптимальном планепроизводства изделий. Поэтому двойственные оценки определяют дефицитностьиспользуемого предприятием сырья. Более того, величина данной двойственнойоценки показывает, на сколько возрастает максимальное значение целевой функциипрямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение количества сырья I вида на 1 кг приведет к тому, что появится возможностьнайти новый оптимальный план производства изделий, при котором общая стоимостьизготовляемой продукции возрастет на /> руб. и станет равной1360+2,5=1362,5 руб. При этом числа, стоящие в столбце вектора /> таблицы 7показывают, что указанное увеличение общей стоимости изготовляемой продукцииможет быть достигнуто за счет уменьшения выпуска изделий В на /> ед. и увеличениявыпуска изделий А на /> ед. Вследствие этого использованиесырья I вида увеличится на /> кг. Точно так же уменьшенияна /> 1 кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общаястоимость изготовляемой продукции возрастет на /> руб. и составит 1360+0,5=1360,5 руб.Это будет достигнуто в результате увеличения выпуска изделий А на /> ед. иуменьшения изготовления изделий B на /> ед., причем объем используемогосырья II вида будет использована полностью.
Продолжим рассмотрениеоптимальных двойственных оценок. Вычисляя минимальное значение целевой функциидвойственной задачи
/>
видим, что оно совпадаетс максимальным значением целевой функции исходной задачи
/>.
При подстановке оптимальных двойственных оценок в системуограничений двойственной задачи получаем
/>
Первое ограничениедвойственной задачи выполняется как строгое неравенство. Это означает, чтодвойственная оценка сырья, используемого на производство одного изделия вида А,выше цены этого изделия и, следовательно, выпускать изделия вида А невыгодно.Его производство и не предусмотрено оптимальным планом прямой задачи. Второе итретье ограничения двойственной задачи выполняются как строгие равенства. Этоозначает, что двойственные оценки сырья, используемого для производства единицысоответственно изделий В и С, равны в точности их ценам. Поэтому выпускать этидва вида продукции по двойственным оценкам экономически целесообразно. Ихпроизводство и предусмотрено оптимальным планом прямой задачи.
Таким образом,двойственные оценки тесным образом связаны с оптимальным планом прямой задачи.
2.6Обоснование выбора программного инструментария
Насегодняшний день существует достаточно языков и сред программирования, припомощи которых можно создавать приложения. Наиболее известные: Delphi, Pascal, C++ и т.д.
C++ — универсальный язык программирования, задуманный так, чтобы сделатьпрограммирование более приятным для серьезного программиста. За исключениемвторостепенных деталей C++ является надмножеством языка программирования C.Помимо возможностей, которые дает C, C++ предоставляет гибкие и эффективныесредства определения новых типов. Используя определения новых типов, точноотвечающих концепциям приложения, программист может разделять разрабатываемуюпрограмму на легко поддающиеся контролю части. Такой метод построения программчасто называют абстракцией данных. Информация о типах содержится в некоторыхобъектах типов, определенных пользователем. Такие объекты просты и надежны виспользовании в тех ситуациях, когда их тип нельзя установить на стадиикомпиляции. Программирование с применением таких объектов часто называютобъектно-ориентированным. При правильном использовании этот метод дает болеекороткие, проще понимаемые и легче контролируемые программы.
Pascal, один из структурированных языковвысокого уровня, который может использоваться для написания программ любоготипа и размера.
Delphi, также замечательный инструментпрограммирования. При помощи Delphiс минимальными затратами времени создаются различные приложения для Windows 95/98. Поскольку в основе лежитконцепция быстрого создания приложений.
Основное вниманиесосредоточено на следующих ключевых особенностях среды Delphi:
- интегрированнаясреда разработки приложений – позволяет создавать, компилировать, тестировать иредактировать проект или группу проектов в единой среде программирования;
- визуальнаятехнология разработки программ – позволяет быстро создавать приложения путемразмещения в форме стандартных компонентов. При этом соответствующий кодпрограммы автоматически генерируется Delphi. Такая технология освобождает разработчика от рутинной работы посозданию пользовательского интерфейса и позволяет уделить больше вниманиявнутренней организации программы и обработке данных;
- библиотека компонентовсодержит множество стандартных компонентов, которые можно использовать присоздании приложений. Сюда относятся элементы управления в стиле Windows 95/98, а также шаблоны для форм;
- поддержка базданных в среде Delphi широкоиспользуются компоненты, предназначенные для работы с базами данных. С ихпомощью можно создавать простые приложения, предназначенные для обработкиданных и приложений типа клиент/сервер. Особенностью этих компонентов являетсято, что уже во время создания приложения Delphi отображает результаты обработки данных и позволяет проанализироватьразличные ситуации, которые могут сложиться при работе программы;
- 32-битовыйкомпилятор Delphi генерирует исполняемые exe-файлы. При этом существуетвозможность генерировать либо простые exe-файлы, либо сложные приложения, требующие подключения dll-библиотек.
На основе анализарассмотренного программного обеспечения можно сделать вывод, что для реализациипоставленной задачи наиболее подходящим программным обеспечением являетсяименно Delphi.
Вывод:
В практической части былорассмотрен анализ двойственных оценок основной задачи линейногопрограммирования. При ручном способе вычислении задачу симплексным методоммаксимальное значение целевой функции равна X* = (0,230,0,230, 0,105), а оптимальный план равен
/>,
При ручном способевычислении задачу двойственным симплекс методом минимальное значение целевойфункции равна/>, а оптимальный план равен
/>
Так же были определеныинтервалы устойчивости
/>.,/>,/>,
а так же влияниеколичества ресурса I типа при уменьшении на 130, II и III ресурсы увеличения на 120 и 110 денежных единиц. Приэтом оптимальным планом двойственной задачи остается />
/> денежных единиц
Это означает, чтоуменьшение количества ресурсов I типана 130 единиц и увеличение ресурсов II и III типов на 120 и 110 единиц квозможности построения такого плана производства продукции, реализация которогообеспечит выпуск изделии на 355 денежных единиц больше, чем при планепроизводства продукции, обусловленным первоначальным количеством ресурсов.
Заключение
При подготовке квыполнению практических работ студенты, недостаточно владеющиепрограммированием, после ручного решения задачи могут использовать этотпрограммный продукт для проверки своих расчетов.
В теоретической частипояснительной записки к курсовой работе приведен краткий теоретический материало формах представления задач линейного программирование, симплексный метод иметод двойственной задачи, необходимый для решения задач линейногопрограммирования
В практической части былорассмотрено анализ двойственных оценок основной задачи линейногопрограммирования. При ручном способе вычислении задачу симплексным методоммаксимальное значение целевой функции равна X* = (0,230,0,230, 0,105), а оптимальный план равен
/>,
при ручном способевычислении задачу двойственным симплекс методом минимальное значение целевойфункции равна />, а оптимальный план равен
/>.
Так же были определеныинтервалы устойчивости
/>., />, />,
а так же влияниеколичества ресурса I типа при уменьшении на 130, II и III ресурсы увеличения на 120 и 110 денежных единиц. Приэтом оптимальным планом двойственной задачи остается
/>.
/>
денежных единиц
Это означает, чтоуменьшение количества ресурсов I типана 130 единиц и увеличение ресурсов II и III типов на 120 и 110 единиц квозможности построения такого плана производства продукции, реализация которогообеспечит выпуск изделии на 355 денежных единиц больше, чем при планепроизводства продукции, обусловленным первоначальным количеством ресурсов. Также приведена экономическая интерпретация двойственной оценки.
После выше перечисленногоделаю заключение, что цель данной курсовой работы была достигнута.
Списокиспользованной источников
1. К.В. Балдин, Н.А. Брызгалов, А.В. Рукосуев«Математическое программирование», «Дашков и К» 2009 г.
2. И.Л. Акулич «Математическоепрограммирование в примерах и задачах», «Высшая школа» 1986 г.
3. Кузнецов Ю.Н., Кузубов В.И.,Волощенко А.Б Математическое программирование – М.: Высшая школа, 1980.
ПриложениеА
Листинг программы
unit Unit1;
interface
uses
Windows,Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs,Grids, Menus, StdCtrls;
type
TForm1 =class(TForm)
MainMenu1:TMainMenu;
N1: TMenuItem;
N2: TMenuItem;
N3: TMenuItem;
N4: TMenuItem;
StringGrid1:TStringGrid;
StringGrid2:TStringGrid;
Label1:TLabel;
StringGrid3:TStringGrid;
Label2:TLabel;
N11:TMenuItem;
StringGrid4:TStringGrid;
Label3:TLabel;
procedureFormCreate(Sender: TObject);
procedureN2Click(Sender: TObject);
procedureN3Click(Sender: TObject);
proceduretab1;
proceduretabrez;
procedurevich;
procedureStringGrid1SelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect:Boolean);
procedureStringGrid2SelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect:Boolean);
procedureN4Click(Sender: TObject);
procedureN11Click(Sender: TObject);
procedureButton1Click(Sender: TObject);
procedureStringGrid4SelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect:Boolean);
private
{ Privatedeclarations }
public
{ Publicdeclarations }
end;
var
Form1: TForm1;
ns,ms:string;
n,m,mm,nm,b:integer;
mas,mas2:array[1..20,1..20]of currency;
ma:array[1..20,1..2]of currency;
m1:array[1..20,1..2] of currency;
bz:array[1..2,1..20] of currency;
min,min2,razr:currency;
y: array[1..10] of currency;
implementation
{$R *.dfm}
procedureTForm1.vich;
vari,j,l,k,o:integer;
lg:currency;
begin
for i:=1 to nmdo m1[i,1]:=0;
for i:=1 to nmdo m1[i,2]:=0;
for i:=1 to mmdo bz[i,1]:=0;
for i:=1 to mmdo bz[i,2]:=0;
for j:=1 tomm-1 do
for i:=2 tonm-1 do
begin
m1[i-1,1]:=m1[i-1,1]+mas[i,j];
if(m1[i-1,1]=1) and (m1[i-1,2]=0) then m1[i-1,2]:=j;
end;
for j:=1 to mdo
for i:=1 to ndo
if (m1[i,1]=1)and (j=m1[i,2]) then
begin
bz[1,j]:=i;
end;
for j:=1 to mdo
bz[2,j]:=ma[trunc(bz[1,j]),1];
for i:=1 to ndo ma[i,2]:=0;
for i:=1 to ndo
begin
for j:=1 to mdo
ma[i,2]:=ma[i,2]+(mas[i+1,j]*bz[2,j]);
ma[i,2]:=ma[i,2]-ma[i,1];
end;
min:=ma[1,2];
l:=0;
o:=0;
for i:=2 to ndo
ifmin>ma[i,2] then begin min:=ma[i,2]; k:=i+1 end;
min2:=0;
for j:=1 to mdo
ifmas[k,j]>0 then begin l:=1; min2:=mas[1,j]/mas[k,j]; o:=j end;
if min2=0 thenbegin b:=1;ShowMessage('Решений нет'); Form1.Free end
else begin
for j:=1 to mdo
ifmas[k,j]>0 then
ifmin2>(mas[1,j]/mas[k,j]) then
begin
min2:=mas[1,j]/mas[k,j];
o:=j;
end;
end;
if(mas[k,o]0) then razr:=mas[k,o];
for j:=1 to mdo
for i:=1 ton+1 do
begin
if j>o thenmas2[i,j]:=mas[i,j];
if j=o thenmas2[i,j]:=mas[i,j]/razr;
if j
end;
for j:=1 to mdo
mas2[1,j]:=abs(mas2[1,j]);
//ShowMessage(currtostr(razr)+' '+inttostr(k)+' '+inttostr(o));
end;
procedureTForm1.tabrez;
vari,j:integer;
l1:currency;
begin
Form1.StringGrid4.Visible:=True;
Form1.StringGrid3.Visible:=True;
Form1.Label2.Visible:=True;
for j:=1 tomm-2 do
for i:=3 tonm-1 do
Form1.StringGrid3.Cells[i,j]:=currtostr(mas[i-2,j]);
// for i:=1 ton do
// Form1.StringGrid3.Cells[i+3,m+1]:=inttostr(ma[i]);
for j:=1 to mdo
Form1.StringGrid3.Cells[1,j]:='P'+inttostr(trunc(bz[1,j]));
for j:=1 to mdo
Form1.StringGrid3.Cells[2,j]:=currtostr(bz[2,j]);
l1:=0;
for j:=1 to mdo
l1:=l1+mas[1,j]*bz[2,j];
Form1.StringGrid3.Cells[3,m+1]:=currtostr(l1);
for i:=1 to ndo
Form1.StringGrid3.Cells[i+3,m+1]:=currtostr(ma[i,2]);
end;
procedureTForm1.tab1;
vari,j:integer;
begin
Form1.StringGrid1.ColCount:=2*n+2;
Form1.StringGrid1.RowCount:=m;
Form1.StringGrid2.ColCount:=2*n+2;
Form1.StringGrid2.RowCount:=1;
Form1.StringGrid1.Width:=((2*n)+2)*36+5;
Form1.StringGrid1.Height:=(32*m);
Form1.StringGrid2.Width:=((2*n)+2)*36+5;
Form1.StringGrid2.Height:=(32*1);
for i:= 0 ton*2 do
begin
if (i mod 2=1) then
begin
Form1.StringGrid2.Cells[i,j]:='X'+inttostr((idiv 2)+1);
end;
if (i mod 2=0) then Form1.StringGrid2.Cells[i,j]:='0';
Form1.StringGrid2.DefaultColWidth:=35;
Form1.StringGrid2.DefaultRowHeight:=30;
end;
Form1.StringGrid2.Cells[2*n,j]:='->';
Form1.StringGrid2.Cells[2*n+1,j]:='min';
for j:= 0 to mdo
begin
for i:= 0 ton*2 do
begin
if (i mod 2=1) then Form1.StringGrid1.Cells[i,j]:='X'+inttostr((i div 2)+1);
if (i mod 2=0) then Form1.StringGrid1.Cells[i,j]:='0';
Form1.StringGrid1.DefaultColWidth:=35;
Form1.StringGrid1.DefaultRowHeight:=30;
end;
Form1.StringGrid1.Cells[2*n,j]:='=';
Form1.StringGrid1.Cells[2*n+1,j]:='0';
end;
Form1.StringGrid2.Top:=(32*m)+15;
Form1.StringGrid3.Top:=(32*m)+65;
Form1.StringGrid3.Width:=((2*n)+2)*36+5;
form1.StringGrid3.Height:=(32*m);
Form1.Label1.Top:=32*m;
Form1.Label2.Top:=32*m+50;
Form1.Label1.Visible:=True;
Form1.StringGrid1.Visible:=True;
Form1.StringGrid2.Visible:=True;
end;
procedureTForm1.FormCreate(Sender: TObject);
vari,j:integer;
begin
end;
procedureTForm1.N2Click(Sender: TObject);
begin
ns:=InputBox('Числопеременных','Введите чесло переменных','4');
n:=strtoint(ns);
Form1.tab1;
end;
procedureTForm1.N3Click(Sender: TObject);
begin
ms:=InputBox('Число функций','Введите чесло функций','3');
m:=strtoint(ms);
Form1.tab1;
end;
procedureTForm1.StringGrid1SelectCell(Sender: TObject; ACol,
ARow: Integer;var CanSelect: Boolean);
begin
if ((ACol mod2 =0)and(ACol
begin
Form1.StringGrid1.Cells[ACol,ARow]:=InputBox('Число','Введите чесло
при X'+inttostr((ACol div 2)+1)+' для функции '+inttostr(ARow+1),'0');
if ((ACol mod2 =0)and(ACol
2)+2,ARow+1]:=strtoint(Form1.StringGrid1.Cells[ACol,ARow]);
// if(ACol=(2*n+1)) then
mas[1,ARow+1]:=strtoint(Form1.StringGrid1.Cells[ACol,ARow]);
end;
end;
procedureTForm1.StringGrid2SelectCell(Sender: TObject; ACol,
ARow: Integer;var CanSelect: Boolean);
begin
if ((ACol mod2 =0)and(ACol
begin
Form1.StringGrid2.Cells[ACol,ARow]:=InputBox('Число','Введите чесло
при Х'+inttostr((ACol div 2)+1)+' для целевой функции ','0');
// if ((AColmod 2 =0)and(ACol
2)+2,1]:=strtoint(Form1.StringGrid2.Cells[ACol,0]);
end;
end;
procedureTForm1.N4Click(Sender: TObject);
vari,j,l:integer;
label 10;
begin
mm:=m+2;
nm:=n+4;
Form1.StringGrid3.RowCount:=mm;
Form1.StringGrid3.ColCount:=nm;
Form1.StringGrid3.FixedCols:=1;
Form1.StringGrid3.FixedRows:=1;
Form1.StringGrid3.DefaultRowHeight:=30;
Form1.StringGrid3.DefaultColWidth:=35;
Form1.StringGrid4.DefaultRowHeight:=30;
Form1.StringGrid4.DefaultColWidth:=35;
Form1.StringGrid4.Width:=m*36+5;
Form1.StringGrid4.Height:=32*2;
Form1.StringGrid4.ColCount:=m;
Form1.StringGrid4.RowCount:=2;
Form1.StringGrid4.FixedRows:=1;
for i:=0 tom-1 do
begin
Form1.StringGrid4.Cells[i,0]:='Y'+inttostr(i+1);
Form1.StringGrid4.Cells[i,1]:='0';
end;
Form1.StringGrid4.Left:=Form1.StringGrid1.Width+10;
Form1.StringGrid3.Width:=nm*36+5;
Form1.StringGrid3.Height:=32*mm;
Form1.StringGrid3.Cells[0,0]:='i';
Form1.StringGrid3.Cells[1,0]:='Бз';
Form1.StringGrid3.Cells[2,0]:='СБз';
Form1.StringGrid3.Cells[0,m+1]:='m+1';
// заполнение таблицырешения
for i:=3 to nm-1 do
Form1.StringGrid3.Cells[i,0]:='P'+inttostr(i-3);
for j:=1 tomm-2 do
Form1.StringGrid3.Cells[0,j]:=inttostr(j)+'.)';
for i:=1 to ndo
for j:=0 to mdo
mas[i+1,j+1]:=strtoint(Form1.StringGrid1.Cells[(i-1)*2,j]);
for j:=1 to mdo
mas[1,j]:=strtoint(Form1.StringGrid1.Cells[2*n+1,j-1]);
for i:=1 to ndo
ma[i,1]:=strtoint(Form1.StringGrid2.Cells[(i-1)*2,0]);
b:=0;
l:=0;
while b=0 do
begin
l:=l+1;
if l=100 thenbegin ShowMessage('Решений нет'); goto 10 end;
Form1.vich;
Form1.tabrez;
for i:=1 ton+1 do
for j:=1 to mdo
mas[i,j]:=mas2[i,j];
for i:=1 to ndo
ifma[i,2]>0 then b:=1 else b:=0;
end;
l:=1;
for i:=n-m+4to n+3 do
begin
y[l]:=strtocurr(Form1.StringGrid3.Cells[i,m+1]);
l:=l+1;
end;
Form1.Label2.Caption:='Решение: У=( '+currtostr(y[1]);
for j:=2 to mdo
Form1.Label2.Caption:=Form1.Label2.Caption+'; '+currtostr(y[j]);
Form1.Label2.Caption:=Form1.Label2.Caption+')';
10:// ShowMessage('Далее');
//Form1.tabrez;
end;
procedureTForm1.N11Click(Sender: TObject);
begin
m:=3;
n:=6;
Form1.tab1;
Form1.StringGrid1.Cells[0,0]:='1';
Form1.StringGrid1.Cells[2,0]:='1';
Form1.StringGrid1.Cells[4,0]:='1';
Form1.StringGrid1.Cells[6,0]:='1';
Form1.StringGrid1.Cells[0,1]:='3';
Form1.StringGrid1.Cells[4,1]:='2';
Form1.StringGrid1.Cells[8,1]:='1';
Form1.StringGrid1.Cells[0,2]:='1';
Form1.StringGrid1.Cells[2,2]:='4';
Form1.StringGrid1.Cells[10,2]:='1';
Form1.StringGrid1.Cells[13,0]:='430';
Form1.StringGrid1.Cells[13,1]:='460';
Form1.StringGrid1.Cells[13,2]:='420';
Form1.StringGrid2.Cells[0,0]:='3';
Form1.StringGrid2.Cells[2,0]:='2';
Form1.StringGrid2.Cells[4,0]:='5';
end;
procedureTForm1.Button1Click(Sender: TObject);
var i:integer;
begin
end;
procedureTForm1.StringGrid4SelectCell(Sender: TObject; ACol,
ARow: Integer;var CanSelect: Boolean);
var i:integer;
begin
Form1.StringGrid4.Cells[ACol,ARow]:=InputBox('Число','Введите чесло
при Y'+inttostr(ACol+1),'0');
Form1.Label3.Visible:=true;
Form1.Label3.Top:=Form1.StringGrid3.Top+Form1.StringGrid3.Height;
Form1.Label3.Caption:='Ответ:
Y='+currtostr(y[1]*strtocurr(Form1.StringGrid4.Cells[0,1]))+'y1';
for i:=1 tom-1 do
Form1.Label3.Caption:=Form1.Label3.Caption+'+'+currtostr(y[i+1]*strtocu
rr(Form1.StringGrid4.Cells[i,1]))+'y'+inttostr(i+1);
end;
end.
Приложение Б (обязательное)
Макеты экранных форм
/>
Рисунок Б.1 – Исходныеданные
/>
Рисунок Б.2 – Результатыпрограммы