Введение
Под термином «программирование» понимают выбор программных действий для решения задачи.
Математическое программирование представляет собой математическую дисциплину, занимающуюся изучением экстремальных задач и разработкой методов их решения. В зависимости от свойств функций раздел математического программирования можно рассматривать как ряд самостоятельных дисциплин. Задачи математического программирования делятся на задачи линейного и нелинейного программирования.
Задачи нелинейного программирования возникают в естественных и физических науках, техники, экономики, в сфере деловых отношений и в науке управления государством. Преобразование реальной задачи в задачу нелинейного программирования в значительной мере является искусством, направляемым теорией. Теория точно указывает, какая из многих возможных формулировок задачи решается наиболее эффективно, а какая не может быть решена вовсе [1].
Прежде всего, задачи математического программирования делятся на линейного и нелинейного программирования. При этом если все функции f и линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функции нелинейная, то соответствующая задача является задачей нелинейного программирования.
Наиболее изученным разделом математического программирования является линейное программирование. Для решения задач линейного программирования разработан целый ряд эффективных методов, алгоритмов и программ [2].
Анализ линейного программирования имеет статическое оптимальное решение, по этому, как только изменяются исходные условия, полученное решение теряет свою актуальность. Анализ чувствительности задачи линейного программирования как раз и связан с исследованием возможных изменений полученного оптимального решения в результате изменений исходных данных задачи. Анализ чувствительности – это процесс, который реализуется после того, как получено оптимальное решение [1].
Данная курсовая работа посвящена общему методу решения задач линейного программирования, известному как симплекс-метод. Процесс решения любой задачи линейного программирования симплекс-методом имеет итерационный характер: однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор, пока не будет найдено оптимальное решение. Информация, которую можно получить с использованием симплекс-метода, не ограничивается оптимальным решением. Этот метод позволяет дать экономическую интерпретацию решения.
1. Теоретическая часть
1.1 Общая и основная задачи линейного программирования
Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции
n
L = ∑ cj
xj
(1.1)
j
=1
при условиях
n
∑ aij
xj
≤ bi
(i=1,k) (1.2)
j=1
n
∑ aij
xj
= 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 | 0 | … | 0 | … | 0 | a1
m +1 |
… | a1
k |
… | a1n
|
| 2 | P2
|
C2
|
b2
|
0 | 1 | … | 0 | … | 0 | a2m+1
|
… | a2k
|
… | a2n
|
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| r | Pr
|
Cr
|
br
|
0 | 0 | … | 1 | … | 0 | arm+1
|
… | ark
|
… | arn
|
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| m | Pm
|
Cm
|
bm
|
0 | 0 | … | 0 | … | 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) Δj
<0 для некоторого j и все соответствующие этому индексу величиныaij
<0 для ;
3) Δj
<0 для некоторых индексов j, и для каждого такого j по крайней мере одно из чисел aij
>0.
В первом случае на основании признака оптимальности исходный опорный план является оптимальным. Во втором случае целевая функция не ограничена сверху на множестве планов, а в третьем случае можно перейти от исходного плана к новому опорному плану, при котором значение целевой функции увеличится. Этот переход от нового опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением в него нового вектора, исходя из максимальной абсолютной величины отрицательных чисел Δj
. Если таких чисел несколько, то в базис вводится вектор, имеющий тот же индекс, что и максимум из чисел cj
, где Δj
<0.
Пусть , остальные Δ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 | 0 | 2 | 460 |
| 3 | мотоцикл | 1 | 4 | 0 | 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 < n; bi
≥ 0, i= 1,3; задача записана в форме основной задачи линейного программирования. Имеется исходный опорный план X =(0,0,0,0,430,460,420). Далее заполняется первая симплексная таблица (таблица 3):
Таблица 3
Симплекс-таблица (1-ая итерация)
| i | Базис | ||||||||
| 1 | 0 | 430 | 1 | 1 | 1
|
1 | 0 | 0 | |
| 2 |
|
0
|
460
|
3
|
0
|
2
|
0
|
1
|
0
|
| 3 | 0 | 420 | 1 | 4 | 0
|
0 | 0 | 1 | |
| m+1 | 0 | -3 | -2 | -5 | 0 | 0 | 0 |
В (m+1)-ой строке находится максимальная по абсолютной величине оценка ∆j
=∆3
= - 8. Таким образом, столбец Р3
является генеральным. Среди элементов ai
1
находится такой, который соответствует минимальному значению bi
/ ai
1
. Это элемент a21
. Таким образом, 2-ая строка является генеральной. Все элементы bi
и aij
пересчитываются соответственно по формулам (1.6) и (1.7). Новые данные заносятся в таблицу 4.
Таблица 4
Симплекс-таблица (2-ая итерация)
| i | Базис | 3 | 2 | 5 | 0 | 0 | 0 | ||
| 1 | 0 | 220 | -1/2 | 1
|
0 | 1 | -1/2 | 0 | |
| 2 | 5
|
230
|
3/2
|
0
|
0
|
0
|
1/2
|
0
|
|
| 3 | 0 | 420 | 1 | 4
|
0 | 0 | 0 | 1 | |
| m+1 | 1150 | 9/2 | -2
|
0 | 0 | 5/2 | 0 |
Новый опорный план: X =(0,0,230,220,0,420). Не все оценки ∆j
≥ 0 . Находятся генеральные строка и столбец. Это столбец Р2
и 2-я строка. Все элементы bi
и aij
пересчитываются соответственно по формулам (1.6) и (1.7). Новые данные заносятся в таблицу 5.
Таблица 5
Симплекс-таблица (3-ая итерация)
| i | Базис | 3 | 2 | 5 | 0 | 0 | 0 | ||
| 1 | 0 | 230 | -3/4 | 0 | 0 | 1 | -1/2
td>
-1/4 |
| |
| 2 | 5 | 230 | 3/2 | 0 | 1 | 0 | 1/2 | 0 | |
| 3 | 2 | 105 | 1/4 | 1 | 0 | 0 | 0 | 1/4 | |
| m+1 | 1360 | 5 | 0 | 0 | 0 | 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.
Приложение А
Листинг программы
unitUnit1;
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;
procedure FormCreate(Sender: TObject);
procedure N2Click(Sender: TObject);
procedure N3Click(Sender: TObject);
procedure tab1;
procedure tabrez;
procedure vich;
procedure StringGrid1SelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect: Boolean);
procedure StringGrid2SelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect: Boolean);
procedure N4Click(Sender: TObject);
procedure N11Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure StringGrid4SelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect: Boolean);
private
{ Private declarations }
public
{ Public declarations }
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}
procedure TForm1.vich;
var i,j,l,k,o:integer;
lg:currency;
begin
for i:=1 to nm do m1[i,1]:=0;
for i:=1 to nm do m1[i,2]:=0;
for i:=1 to mm do bz[i,1]:=0;
for i:=1 to mm do bz[i,2]:=0;
for j:=1 to mm-1 do
for i:=2 to nm-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 m do
for i:=1 to n do
if (m1[i,1]=1) and (j=m1[i,2]) then
begin
bz[1,j]:=i;
end;
for j:=1 to m do
bz[2,j]:=ma[trunc(bz[1,j]),1];
for i:=1 to n do ma[i,2]:=0;
for i:=1 to n do
begin
for j:=1 to m do
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 n do
if min>ma[i,2] then begin min:=ma[i,2]; k:=i+1 end;
min2:=0;
for j:=1 to m do
if mas[k,j]>0 then begin l:=1; min2:=mas[1,j]/mas[k,j]; o:=j end;
if min2=0 then begin b:=1;ShowMessage('Решенийнет'); Form1.Free end
else begin
for j:=1 to m do
if mas[k,j]>0 then
if min2>(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 m do
for i:=1 to n+1 do
begin
if j>o then mas2[i,j]:=mas[i,j];
if j=o then mas2[i,j]:=mas[i,j]/razr;
if j<o then mas2[i,j]:=((mas[i,j]*mas[k,o])-(mas[i,o]*mas[k,j]))/razr;
end;
for j:=1 to m do
mas2[1,j]:=abs(mas2[1,j]);
// ShowMessage(currtostr(razr)+' '+inttostr(k)+' '+inttostr(o));
end;
procedure TForm1.tabrez;
var i,j:integer;
l1:currency;
begin
Form1.StringGrid4.Visible:=True;
Form1.StringGrid3.Visible:=True;
Form1.Label2.Visible:=True;
for j:=1 to mm-2 do
for i:=3 to nm-1 do
Form1.StringGrid3.Cells[i,j]:=currtostr(mas[i-2,j]);
// for i:=1 to n do
// Form1.StringGrid3.Cells[i+3,m+1]:=inttostr(ma[i]);
for j:=1 to m do
Form1.StringGrid3.Cells[1,j]:='P'+inttostr(trunc(bz[1,j]));
for j:=1 to m do
Form1.StringGrid3.Cells[2,j]:=currtostr(bz[2,j]);
l1:=0;
for j:=1 to m do
l1:=l1+mas[1,j]*bz[2,j];
Form1.StringGrid3.Cells[3,m+1]:=currtostr(l1);
for i:=1 to n do
Form1.StringGrid3.Cells[i+3,m+1]:=currtostr(ma[i,2]);
end;
procedure TForm1.tab1;
var i,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 to n*2 do
begin
if (i mod 2 =1) then
begin
Form1.StringGrid2.Cells[i,j]:='X'+inttostr((i div 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 m do
begin
for i:= 0 to n*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;
procedure TForm1.FormCreate(Sender: TObject);
var i,j:integer;
begin
end;
procedure TForm1.N2Click(Sender: TObject);
begin
ns:=InputBox('Число переменных','Введите чесло переменных','4');
n:=strtoint(ns);
Form1.tab1;
end;
procedure TForm1.N3Click(Sender: TObject);
begin
ms:=InputBox('Числофункций','Введитечеслофункций','3');
m:=strtoint(ms);
Form1.tab1;
end;
procedure TForm1.StringGrid1SelectCell(Sender: TObject; ACol,
ARow: Integer; var CanSelect: Boolean);
begin
if ((ACol mod 2 =0)and(ACol<(2*n))) or (ACol=(2*n+1)) then
begin
Form1.StringGrid1.Cells[ACol,ARow]:=InputBox('Число','Введитечесло
при X'+inttostr((AColdiv 2)+1)+' для функции '+inttostr(ARow+1),'0');
if ((ACol mod 2 =0)and(ACol<(2*n)))then mas[(ACol div
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;
procedure TForm1.StringGrid2SelectCell(Sender: TObject; ACol,
ARow: Integer; var CanSelect: Boolean);
begin
if ((ACol mod 2 =0)and(ACol<(2*n))) {or (ACol=(2*n+1))} then
begin
Form1.StringGrid2.Cells[ACol,ARow]:=InputBox('Число','Введитечесло
при Х'+inttostr((AColdiv 2)+1)+' для целевой функции ','0');
// if ((ACol mod 2 =0)and(ACol<(2*n)))then ma[(ACol div
2)+2,1]:=strtoint(Form1.StringGrid2.Cells[ACol,0]);
end;
end;
procedure TForm1.N4Click(Sender: TObject);
var i,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 to m-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 to mm-2 do
Form1.StringGrid3.Cells[0,j]:=inttostr(j)+'.)';
for i:=1 to n do
for j:=0 to m do
mas[i+1,j+1]:=strtoint(Form1.StringGrid1.Cells[(i-1)*2,j]);
for j:=1 to m do
mas[1,j]:=strtoint(Form1.StringGrid1.Cells[2*n+1,j-1]);
for i:=1 to n do
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 then begin ShowMessage('Решенийнет'); goto 10 end;
Form1.vich;
Form1.tabrez;
for i:=1 to n+1 do
for j:=1 to m do
mas[i,j]:=mas2[i,j];
for i:=1 to n do
if ma[i,2]>0 then b:=1 else b:=0;
end;
l:=1;
for i:=n-m+4 to 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 m do
Form1.Label2.Caption:=Form1.Label2.Caption+' ; '+currtostr(y[j]);
Form1.Label2.Caption:=Form1.Label2.Caption+' )';
10:// ShowMessage('Далее');
// Form1.tabrez;
end;
procedure TForm1.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;
procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
end;
procedure TForm1.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 to m-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 – Результаты программы