Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Федеральное агентство по образованию РФ
Федеральное государственное образовательное учреждение
Среднего профессионального образования
Барнаульский строительный колледж
Курсовая работа.
По дисциплине: «Математические методы»
На тему: «Решение задач линейного программирования симплекс методом»
Выполнил: Нунгесер М.В.
Специальность: ПОВТ
Группа: 0881
Преподаватель: Клепикова Н.Н.
Барнаул 2010
Содержание:
Введение
Линейное программирование
Симплекс метод
Постановка задачи
Разработка алгоритма
Решение задачи
Программная реализация на языке Delphi
Приложение
Заключение
Список используемой литературы
В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства. Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования. В конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач – симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.
Решение задач математического программирования при помощи симплекс-метода традиционными способами требует затрат большого количества времени. В связи с бурным развитием компьютерной техники в последние десятилетия естественно было ожидать, что вычислительная мощность современных ЭВМ будет применена для решения указанного круга задач.
Линейное программирование - математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно -линейное программирование.
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
Математическая формулировка задачи линейного программирования
Нужно определить максимум линейной целевой функции (линейной формы)
при условиях
Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя её во всех остальных равенствах и неравенствах (а также в функции f).
Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного итеративного процесса, необходимо улучшающего значение целевой функции на каждом шаге.
Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1, ..., Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1, ..., Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1.
Данная формальная модель задачи линейного программирования обычно задается в форме, так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода:
Симплекс-таблица
|
1 |
X1 |
X2 |
... |
Xm |
Xm+1 |
... |
Xn |
|
|
X0 |
A0,0 |
0 |
0 |
... |
0 |
A0,m+1 |
... |
A0,n |
|
X1 |
A1,0 |
1 |
0 |
... |
0 |
A1,m+1 |
... |
A1,n |
|
X2 |
A2,0 |
0 |
1 |
... |
0 |
A2,m+1 |
... |
A2,n |
|
... |
... |
... |
... |
... |
... |
... |
... |
... |
|
Xm |
Am,0 |
0 |
0 |
... |
1 |
Am,m+1 |
... |
Am,n |
Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1, ..., Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm+1, ..., Xn - свободные переменные задачи.
На начальном шаге алгоритма симплекс-метода должно быть выбрано базисное допустимое решение (X1, ..., Xm) >= 0 при Xj = 0 (j = m+1, ..., n), следовательно, все свободные члены ограничений Ai,0 >= 0 (i = 1, ..., m). Когда это условие выполнено, симплекс-таблица называется прямо-допустимой, так как в этом случае базисные переменные, равные Ai,0, определяют допустимое решение прямой задачи линейного программирования. Если все коэффициенты целевой функции A0,j >= 0 (j = 1, ..., m), то симплекс-таблица называется двойственно-допустимой, поскольку соответствующее решение является допустимым для двойственной задачи линейного программирования.
Если симплекс-таблица является одновременно прямо и двойственно допустимой, т.е. одновременно все Ai,0 >= 0 и A0,j >= 0, то решение оптимально.
Действительно, поскольку допустимыми являются лишь неотрицательные значения управляемых параметров, то изменение целевой функции за счет вариации свободных переменных, через которые она выражена, возможно только в сторону увеличения, т.e. будет ухудшаться. Если среди ее коэффициентов имеются A0,j < 0, то значение целевой функции еще можно уменьшить (т.e. улучшить), увеличивая значение любой свободной переменной Xj с отрицательным коэффициентом A0,j при побочном уменьшении базисных переменных, чтобы оставались справедливы ограничения задачи. Теоретически можно использовать любую свободную переменную Xj с A0,j < 0, но на практике обычно действуют в соответствии со стратегией наискорейшего спуска, выбирая минимальный элемент A0,p < 0 из всех отрицательных A0,j < 0:
A0,p = min A0,j < 0.
j
Столбец p симплекс-таблицы, соответствующий выбранному коэффициенту A0,p < 0, называется ведущим столбцом. Свободная переменная ведущего столбца должна быть введена в базис вместо одной из текущих базисных переменных. Очевидно, из базиса следует исключить такую переменную Xq, которая раньше других обращается в нуль при увеличении переменной Xp ведущего столбца.
Её индекс легко определить, если среди положительных элементов ведущего столбца p найти элемент, минимизирующий отношение (Ai,0 / Ai,p):
Aq,0 Ai,0
------ = min ------ , i = 1,...,m.
Aq,p i Ai,p
Элемент Aq,p называется ведущим элементом, cтрока q симплекс-таблицы, содержащая ведущий элемент, называется, соответственно, ведущей строкой. Переменная ведущей строки Xq заменяется в базисе переменной ведущего столбца Xp и становится свободной переменной с значением 0, в то время как новая базисная переменная Xp достигнет максимально возможного значения, равного: max Xp = ( Aq,0 / Aq,p).
После указанного взаимообразного обмена переменными Xp и Xq между наборами свободных и базисных переменных нужно модифицировать исходную каноническую модель задачи путем приведения ее к диагональной форме относительно нового множества базисных переменных. Для указанного преобразования можно формально использовать процедуру исключения Гаусса, которая, как известно, состоит из двух элементарных операций, применяемых к системе алгебраических уравнений ( в данном случае ограничений - равенств):
Исключения Гаусса позволяют привести систему уравнений к диагональной форме относительно желаемого множества переменных. В данном случае исключение Гаусса применяется так, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента Aq,p, стали нулевыми, а ведущий элемент стал равным единице:
Ai,p = 0, если i не равно q
и
Ai,p = 1, если i = q.
Указанные шаги симплекс-метода повторяются, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой. Если положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение.
Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой перебор базисных допустимых решений. Однако, трудные для симплекс метода задачи на практике встречаются крайне редко, что объясняет широкое распространение и большую популярность данного метода линейного программирования по сравнению с другими подходами.
На звероферме могут выращиваться норки, выдры и нутрии. Для обеспечения нормальных условий их выращивания используется 3 вида кормов. Количество корма каждого вида, которое должны получать зверьки в среднем приведено в таблице:
|
Количество единиц корма, которое ежедневно должны получать |
||||
|
Вид корма |
Норка |
Выдра |
Нутрия |
Общее количество корма |
|
I |
4 |
2 |
5 |
190 |
|
II |
5 |
3 |
4 |
320 |
|
III |
7 |
9 |
5 |
454 |
|
Прибыль от реализации одной шкурки, руб. |
150 |
320 |
350 |
В таблице указано общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки зверька.
Признаком оптимальности решения является наличие в векторе решений только отрицательных или нулевых коэффициентов при всех ограничениях.
Ответ записывается следующим образом:
- Каждому отрицательному коэффициенту в векторе решения ставится в соответствие нулевой коэффициент для соответствующей переменной в ответе.
- Для каждого нулевого коэффициента в векторе решения ставится в соответствие значение свободного члена из строки, содержащей единицу в столбце данной переменной.
- Фиктивные переменные в ответе не учитываются.
Ведущим может быть назначен любой столбец, удовлетворяющий одному из условий:
1) Первый столбец, содержащий положительный элемент в векторе решений.
2) Столбец, содержащий наибольший положительный элемент в строке решения.
3) Если столбец удовлетворяет условию max(Cj min bj/aij) при решении на max, и min(Cj min bj/aij) при решении задач на min.
Cj – коэффициент целевой функции в столбце j, aij – коэффициент в столбце j и строке i.
Определим максимальное значение целевой функции F(X) = 3500 x1 +3200 x2 +1500 x3 при следующих условиях ограничений.
4 x1 + 2 x2 + 5 x3 <=190
5 x1 + 3 x2 + 4 x3 <=320
7 x1 + 9 x2 + 5 x3 <=454
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.
4x1 + 2x2 + 5x3 + 1x4 + 0x5 + 0x6 = 190
5x1 + 3x2 + 4x3 + 0x4 + 1x5 + 0x6 = 320
7x1 + 9x2 + 5x3 + 0x4 + 0x5 + 1x6 = 454
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x4 , x5 , x6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,190,320,454)
Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы.
Переходим к основному алгоритму симплекс-метода.
|
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
св. чл. |
|
4 |
2 |
5 |
1 |
0 |
0 |
190 |
|
5 |
3 |
4 |
0 |
1 |
0 |
320 |
|
7 |
9 |
5 |
0 |
0 |
1 |
454 |
|
-3500 |
-3200 |
-1500 |
0 |
0 |
0 |
0 |
Итерация №0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения D i по строкам как частное от деления
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей
Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x1
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=4
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (4), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
|
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
св. чл. |
|
1 |
1/2 |
5/4 |
1/4 |
0 |
0 |
190/4 |
|
5 |
3 |
4 |
0 |
1 |
0 |
320 |
|
7 |
9 |
5 |
0 |
0 |
1 |
454 |
|
3500 |
3200 |
1500 |
0 |
0 |
0 |
|
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
св. чл. |
|
1 |
1/2 |
5/4 |
1/4 |
0 |
0 |
190/4 |
|
0 |
1/2 |
-9/4 |
-5/4 |
1 |
0 |
165/2 |
|
0 |
11/2 |
-15/4 |
-7/4 |
0 |
1 |
243/2 |
|
0 |
-1450 |
2875 |
875 |
0 |
0 |
Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x2, так как наибольший коэффициент по модулю.
Вычислим значения D i по строкам как частное от деления и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей
Разрешающий элемент равен 5.5 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x2
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=5.5
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (5.5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
Конец итераций: найден оптимальный план
Окончательный вариант симплекс-таблицы:
|
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
св. чл. |
|
1 |
0 |
159/100 |
41/100 |
0 |
-9/100 |
729/20 |
|
0 |
0 |
-191/100 |
-109/100 |
1 |
-9/100 |
1429/20 |
|
0 |
1 |
-15/22 |
-7/22 |
0 |
9/50 |
243/11 |
|
0 |
0 |
1886.36 |
413.64 |
0 |
263.64 |
Оптимальный план можно записать так:
x1 = 729/20=36.45
x5 =1429/20= 71.45
x2 =243/11= 22.09
F(X) = 3500*36.45 + 3200*22.09 = 198281.82
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls;
type
TForm1 = class(TForm)
Label1: TLabel;
Label2: TLabel;
Edit2: TEdit;
Exit: TButton;
Button_Next: TButton;
Edit1: TEdit;
Button_Prev: TButton;
ScrollBox1: TScrollBox;
Conditions: TGroupBox;
Label3: TLabel;
Extrem: TComboBox;
Memo1: TMemo;
procedure ExitClick(Sender: TObject);
procedure Button_NextClick(Sender: TObject);
procedure Button_PrevClick(Sender: TObject);
procedure FormCreate(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
const
mm = 100; nn = 100;
var
Form1: TForm1;
table_changed,done,solve,is_ok,kanon,need_basis,need_i_basis,is_basis,written: boolean;
m,n,y,i_basis,i0,j0,step,iter: integer;{m - элементов , n - ограничений}
pole: array [1..nn, 1..mm] of TEdit; {поля для ввода}
podpis: array [0..nn, 0..mm] of TLabel; {подписи полей}
znak: array [1..nn] of TComboBox; {знаки сравнения ограничений}
matrix: array [1..nn, 1..mm] of double; {массив для рассчетов}
all_basis: array [1..nn] of integer;{номера базисных переменных}
f: text;{файловая переменная для отчета}
tochnost: double;
implementation
{$R *.dfm}
procedure Init;
{инициализация: ввод размеров системы}
Begin
form1.Button_Prev.Enabled:=false;
form1.Edit1.Enabled:=true;
form1.Edit2.Enabled:=true;
form1.Extrem.Enabled:=true;
form1.ScrollBox1.DestroyComponents;{расчищаем место под табличку}
table_changed:=true;
tochnost:=0.000000001;
assign(f, 'report.htm');
end;
procedure Step1;
{шаг первый: создание таблички и ввод значений}
var
i,j: integer;
nadpis: string;
begin
form1.Memo1.ReadOnly:=false;
form1.Memo1.Lines.Clear;
form1.Memo1.ReadOnly:=true;
form1.Extrem.Enabled:=true;
if table_changed=true then {если меняли количество эл-тов или ограничений,}
begin {то создаем новую табличку}
table_changed:=false;
m:=strtoint(form1.Edit1.Text);{считываем количество переменных}
n:=strtoi
nt(form1.Edit2.Text);{и ограничений}
form1.Edit1.Enabled:=false;{блокируем поля для их ввода}
form1.Edit2.Enabled:=false;
i:=0; {используем нулевую строку массива подписей для заголовков}
for j:=1 to 3 do {подписываем что is что}
begin
podpis[i,j]:=TLabel.Create(Form1.ScrollBox1);
podpis[i,j].parent:=form1.ScrollBox1;
podpis[i,j].Left:=5;
podpis[i,j].Top:=32*(j-1); {расстояние между надписями}
case j of
1: nadpis:='Целевая функция:';
2: nadpis:='F(x)=';
3: nadpis:='Система ограничений:';
end;
podpis[i,j].Caption:=nadpis;
end;
i:=n+1; {используем последнюю строку массива полей для целевой ф-ции}
for j:=1 to m+1 do
begin
pole[i,j]:=TEdit.Create(Form1.ScrollBox1);
pole[i,j].parent:=form1.ScrollBox1;
pole[i,j].Height:=20;
pole[i,j].Width:=40;
pole[i,j].Left:=80*(j-1)+30;
pole[i,j].Top:=30;
pole[i,j].Text:='0';
if j<=m then
begin
podpis[i,j]:=TLabel.Create(Form1.ScrollBox1);
podpis[i,j].parent:=form1.ScrollBox1;
podpis[i,j].Height:=20;
podpis[i,j].Width:=20;
podpis[i,j].Left:=pole[i,j].Left+pole[i,j].Width+2;
podpis[i,j].Top:=pole[i,j].Top+2;
podpis[i,j].Caption:='X['+inttostr(j)+']';
if j<>m+1 then podpis[i,j].Caption:=podpis[i,j].Caption+' +';
{если поле не последнее, то дописываем плюсик}
end;
end;
for i:=1 to n do {поля для ввода ограничений}
for j:=1 to m+1 do
begin
pole[i,j]:=TEdit.Create(Form1.ScrollBox1);
pole[i,j].parent:=form1.ScrollBox1;
pole[i,j].Height:=20;
pole[i,j].Width:=40;
pole[i,j].Left:=80*(j-1)+5; {расстояние между соседними + отступ от края}
pole[i,j].Top:=40*(i-1)+100;
pole[i,j].Text:='0';
if j<=m then
begin
podpis[i,j]:=TLabel.Create(Form1.ScrollBox1);
podpis[i,j].parent:=form1.ScrollBox1;
podpis[i,j].Height:=20;
podpis[i,j].Width:=20;
podpis[i,j].Left:=pole[i,j].Left+pole[i,j].Width+2;
podpis[i,j].Top:=pole[i,j].Top+2;
podpis[i,j].Caption:='X['+inttostr(j)+']';
if j<>m then podpis[i,j].Caption:=podpis[i,j].Caption+' +'
{если поле не последнее, то дописываем плюсик; иначе пишем знак}
else begin
znak[i]:=TComboBox.Create(Form1.ScrollBox1);
znak[i].parent:=form1.ScrollBox1;
znak[i].Height:=20;
znak[i].Width:=40;
znak[i].Left:=podpis[i,j].Left+podpis[i,j].Width+25;
znak[i].Top:=pole[i,j].Top;
znak[i].Items.Insert( 0,'> ');
znak[i].Items.Insert( 1,'>=');
znak[i].Items.Insert( 2,' =');
znak[i].Items.Insert( 3,'<=');
znak[i].Items.Insert( 4,'< ');
znak[i].ItemIndex:=1;
end;
end else pole[i,j].Left:=pole[i,j].Left+70; //поля для правой части
//ограничений
end;
end else {если табличку создавать не надо, то разблокируем поля}
begin
for i:=1 to n+1 do
for j:=1 to m+1 do
begin
pole[i,j].Enabled:=true;
if i<=n then znak[i].Enabled:=true;
end;
end;
end;
{/////////////////}
procedure write_system(strok,stolb: integer);
{записывает массив в виде уравнений}
var
i,j: integer;
begin
write(f,'<P>F(x) = ');
for j:=1 to stolb do
begin
write(f,matrix[strok,j]:0:3);
if j<stolb then
begin
write(f,'x<sub>',j,'</sub>');
if (kanon=true) and (j=stolb-1) then write(f,' = ') else
if (matrix[strok,j+1]>=0) then write(f,' + ') else write(f,' ');
end;
end;
writeln(f,'</P>');
writeln(f,'<P>При ограничениях:</P><P>');
for i:=1 to strok-1 do
begin
for j:=1 to stolb do
BEGIN
write(f,matrix[i,j]:0:3);
if j<stolb then write(f,'x<sub>',j,'</sub> ');
if j=stolb-1 then
if kanon=false then write(f,' ',znak[i].text,' ')
else write(f,' = ');
if (matrix[i,j+1]>=0) and (j<stolb-1) then write(f,'+');
end;
writeln(f,'<br>');
end;
writeln(f,'</P>');
end;
{/////////////////}
procedure zapisat(strok,stolb: integer; v_strok,v_stolb:integer);
{записывает массив в виде таблички}
var
i,j:integer;
begin
writeln(f,'<TABLE BORDER BORDERCOLOR=black CELLSPACING=0 CELLPADDING=5>');
for i:=0 to strok do
begin
writeln(f,'<TR>');
for j:=1 to stolb+1 do
begin
write(f,'<TD ');
if i=0 then
begin
if (i_basis<>0) and (j>m+y-i_basis) and (j<=m+y) then
write(f,'BGCOLOR=yellow ')
else
write(f,'BGCOLOR=green ');
end
else
if (i=v_strok) or (j=v_stolb) then write(f,'BGCOLOR=silver ') else
if (i=strok) or (j=stolb) then
if (j<>stolb+1) then write(f,'BGCOLOR=olive ');
write(f,'align=');
if (i=0) and (j<stolb) then write(f,'center>X<sub>',j,'<sub>') else
if (i=0) and (j=stolb) then write(f,'center>св. чл.') else
if (i=0) and (j=stolb+1) then write(f,'center>базис') else
if (j=stolb+1) then
if i<>n+1 then write(f,'center>X<sub>',all_basis[i],'</sub>') else
write(f,'center> ')
else
write(f,'right>',matrix[i,j]:1:3);
writeln(f,'</TD>');
end;
writeln(f,'</TR>');
end;
writeln(f,'</TABLE>');
end;
{/////////////////}
procedure findved;
{ищет ведущий элемент}
var
i,j,k: integer;
temp: double;
begin
done:=false;
solve:=false;
is_ok:=true;
temp:=100000;
i0:=0;
j0:=0;
i:=n+1;
for j:=1 to m+y do
if (i0=0) or (j0=0) then
if matrix[i,j]>0 then
begin
j0:=j;
for k:=1 to n do
if (matrix[k,j]>0) then
if (matrix[k,m+y+1]/matrix[k,j]<temp) then
begin
temp:=matrix[k,m+y+1]/matrix[k,j];
i0:=k;
end;
end;
if (j0=0) and (i0=0) then
for j:=1 to m do
if matrix[n+1,j]=0 then
for i:=1 to n do
if (matrix[i,j]<>0) and (matrix[i,j]<>1) then
begin
is_ok:=false;
j0:=j;
end;
if is_ok=false then
begin
temp:=100000;
for k:=1 to n do
if (matrix[k,j0]>0) then
if (matrix[k,m+y+1]/matrix[k,j0]<temp) then
begin
temp:=matrix[k,m+y+1]/matrix[k,j0];
i0:=k;
end;
end;
if (j0=0) and (i0=0) then
begin
writeln(f, '<P>Конец вычислений</P>');
done:=true;
solve:=true;
end
else if (j0<>0) and (i0=0) then
begin
writeln(f, '<P>Не удается решить систему</P>');
done:=true;
solve:=false;
end
else
if iter<>0 then
begin
writeln(f,'<P><b>Итерация ',iter,'</b></P>');
writeln(f, '<P>Найдем ведущий элемент:</P>');
zapisat(n+1,m+y+1,i0,j0);
writeln(f,'<P>Ведущий столбец: ',j0,'<br>Ведущая строка: ',i0,'</P>');
write(f,'<P>В строке ',i0,': базис ');
writeln(f,'X<sub>',all_basis[i0],'</sub> заменяем на X<sub>',j0,'</sub></P>');
all_basis[i0]:=j0;
end;
end;
{/////////////////}
procedure okr;
{округляет мелкие погрешности}
var
i,j: integer;
begin
for i:=1 to n+1 do
for j:=1 to m+y+1 do
if abs(matrix[i,j]-round(matrix[i,j]))< tochnost then
matrix[i,j]:=round(matrix[i,j]);
end;
{/////////////////}
procedure preobr;
{преобразует массив относительно ведущего элемента}
var
i,j,k,l,t: integer;
temp: double;
begin
if done=false then
begin
write(f, '<P>Пересчет:</P>');
temp:=matrix[i0,j0];
for j:=1 to m+y+1 do matrix[i0,j]:=matrix[i0,j]/temp;
for i:=1 to n+1 do
begin
temp:=matrix[i,j0];
for j:=1 to m+y+1 do
if (i<>i0) then
matrix[i,j]:=matrix[i,j]-matrix[i0,j]*temp;
end;
okr;
zapisat(n+1,m+y+1,-1,-1);
{/////////////////////////убираем искусственный базис/////////////////////}
if i_basis>0 then {если он есть }
begin
t:=0;
for j:=m+y-i_basis+1 to m+y do {от первого исскусственного элемеента до конца}
begin
need_i_basis:=false;{предполагаем, что элемент не нужен (*)}
for i:=1 to n do {просматриваем столбец}
if all_basis[i]=j then{и если элемент в базисе}
need_i_basis:=true;{тогда он все-таки нужен}
if need_i_basis=false then t:=j;
{если наши предположения (*) подтвердились, то запомним этот элемент}
end;
if t<>0 then
begin
for k:=1 to n+1 do {во всех строках}
begin
for l:=t to m+y do {от текущего столбца до последнего}
matrix[k,l]:=matrix[k,l+1];{заменяем элемент на соседний}
matrix[k,m+y+1]:=0;{а последний убираем}
end;
{столбец удален! надо это запомнить}
y:=y-1;
i_basis:=i_basis-1;
if i_basis>0 then {если остались еще искусственные переменные,}
for l:=m+y-i_basis+1 to m+y do{то от первой из них до последней}
for i:=1 to n do {просматриваем строки в столбце}
if matrix[i,l]=1 then all_basis[i]:=l; {туда, где 1, заносим в базис}
writeln(f,'<P>Искусственная переменная исключена из базиса<br>');
writeln(f,'и может быть удалена из таблицы.');
writeln(f,'</P>');
zapisat(n+1,m+y+1,-1,-1);
end;
end;
{///////////////закончили убирать искусственный базис////////////////////}
end;
end;
{/////////////////}
procedure otvet;
{выводит ответ}
var
i,j: integer;
begin
writeln(f,'<P><b>ОТВЕТ:</b></P>');
form1.Memo1.ReadOnly:=false;
form1.Memo1.Lines.Clear;
form1.Memo1.Lines.Add('ОТВЕТ:');
form1.Memo1.Lines.Add('');
if (solve=true) and (i_basis=0) then
write(f,'F(');
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+'F(';
if form1.Extrem.ItemIndex=0 then
begin
write(f,'max) = ',0-matrix[n+1,m+y+1]:0:3);
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+'max) = ';
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+floattostr(0-matrix[n+1,m+y+1]);
end
else
begin
write(f,'min) = ',matrix[n+1,m+y+1]:0:3);
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+'min) = ';
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+floattostr(matrix[n+1,m+y+1]);
end;
writeln(f,'<br>при значениях:<br>');
form1.Memo1.Lines.Add('');
form1.Memo1.Lines.Add('');
form1.Memo1.Lines.Add('при значениях:');
form1.Memo1.Lines.Add('');
for j:=1 to m do
begin
writeln(f,'x<sub>',j,'</sub> = ');
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+'X[';
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+inttostr(j);
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+'] = ';
written:=false;
for i:=1 to n do
if all_basis[i]=j then
begin
writeln(f,matrix[i,m+y+1]:0:3,'<br>');
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+floattostr(matrix[i,m+y+1]);
form1.Memo1.Lines.Add('');
form1.Memo1.Lines.Add('');
written:=true;
end;
if written=false then
begin
writeln(f,'0.000 <br>');
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+'0';
form1.Memo1.Lines.Add('');
form1.Memo1.Lines.Add('');
end;
end;
end else
begin
writeln(f,'<P>Решение не найдено.(</P>');
form1.Memo1.Lines.Text:=form1.Memo1.Lines.Text+'Решение не найдено.';
end;
form1.Memo1.ReadOnly:=true;
end;
{/////////////////}
procedure Step2;
{шаг второй: решение задачи и формирование отчета}
var
i,j: integer;
k: integer;
begin
for i:=1 to n+1 do
for j:=1 to m+1 do
begin
matrix[i,j]:=strtofloat(pole[i,j].Text); {Вводим значения в массив}
pole[i,j].Enabled:=false; {Блокируем поля}
if i<=n then znak[i].Enabled:=false;{блокируем знаки}
end;
form1.Extrem.Enabled:=false;
{////////////////////////////////////////////////////////////////////////////}
{ имеем матрицу [ n+1, m+1 ] }
rewrite(f);
writeln(f,'<HTML>');
writeln(f,'<HEAD>');
writeln(f,'<TITLE>Отчет</TITLE>');
writeln(f,'</HEAD>');
writeln(f,'<BODY>');
writeln(f,'<H1>Отчет</H1>');
write(f,'<P><b>Необходимо ');
if form1.Extrem.ItemIndex=0 then write(f,'макс') else write(f,'мин');
writeln(f,'имизировать целевую функцию:</b></P>');
kanon:=false;{еще не в канонической форме}
write_system(n+1,m+1);{Выведем ее в отчет}
{приведем ее к каноническому виду}
writeln(f,'<P><b>Приведем к каноническому виду:</b></P>');
y:=0;{количество дополнительных переменных}
need_basis:=false;
for i:=1 to n do
if znak[i].ItemIndex<>2 then {если ограничение не является равенством}
begin
y:=y+1; {вводим дополнительную переменную, для этого:}
for k:=1 to n+1 do begin {во всех ограничениях и в ЦФ}
{перед правой частью добавляем столбец}
matrix[k,m+y+1]:=matrix[k,m+y];
matrix[k,m+y]:=0;{состоящий из нулей}
end;
{а в текущем ограничении, если знак был > или >=}
if (znak[i].ItemIndex=0) or (znak[i].ItemIndex=1) then
begin
matrix[i,m+y]:=-1;{записываем -1}
need_basis:=true;
end
else {иначе, т.е. в случае < или <=}
matrix[i,m+y]:=1; {записываем 1}
end
else need_basis:=true;
{ЦФ приравнивается к нулю, а свободный член переносится в правую часть:}
matrix[n+1,m+y+1]:=0-matrix[n+1,m+y+1];
{правые части ограничений должны быть неотрицательны, проверим это:}
for i:=1 to n do {для всех ограничений}
if matrix[i,m+y+1]<0 then {если правая часть отрицательна,}
{то отнимаем всю строку от нуля}
for j:=1 to m+y+1 do matrix[i,j]:=(0-matrix[i,j]);
kanon:=true;{система приведена к каноническому виду}
{выведем ее в отчет}
write_system(n+1,m+y+1);
{если ф-ция на минимум, то нужно поменять знаки в последней строке}
if form1.Extrem.ItemIndex=1 then
for j:=1 to m+y+1 do matrix[n+1,j]:=0-matrix[n+1,j];
{////////////////////////////////////////////////////////////////////////////}
{////////////////////////// Тут надо ввести базис ///////////////////////////}
i_basis:=0;
for i:=1 to n do {то во всех ограничениях}
begin
is_basis:=false;
for j:=1 to m+y do
if (matrix[i,j]=1) then
if (is_basis=false) then
begin
all_basis[i]:=j;
is_basis:=true;
for k:=1 to n do
if k<>i then
if (matrix[k,j]<>0) then
if (is_basis=true) then
begin
is_basis:=false;
all_basis[i]:=0;
end;
end;
if is_basis=false then
begin
i_basis:=i_basis+1;
y:=y+1;
for k:=1 to n+1 do
begin {во всех ограничениях и в ЦФ}
{перед правой частью добавляем столбец}
matrix[k,m+y+1]:=matrix[k,m+y];
matrix[k,m+y]:=0;{состоящий из нулей}
end;
matrix[i,m+y]:=1;
all_basis[i]:=m+y;
end;
end;
{//////////////// Закончили ввод искусственного базиса //////////////////////}
{////////////////////////////////////////////////////////////////////////////}
{////////////////////////////////////////////////////////////////////////////}
{//////////////// теперь надо от него избавиться ////////////////////////////}
if i_basis>0 then
begin
write(f, '<H2>Необходимо ввести искусственный базис</H2>');
zapisat(n+1,m+y+1,-1,-1);
writeln(f, '<P>Искусственный базис введен.<br>');
writeln(f, 'Избавившись от него, получим первое допустимое решение</P>');
iter:=0;
repeat
inc(iter);
findved;
preobr;
until (i_basis=0) or (iter=20) or (done=true);
if i_basis=0 then
begin
writeln(f,'<P>Искусственный базис выведен полностью.<br>');
writeln(f,'Получено первое допустимое решение!</P>');
end
else
begin
writeln(f,'<P>Не удалось вывести искусственный базис.<br>');
writeln(f,'Решение не найдено.</P>');
end;
end;
{//////////////////////// попытки избавленя окончены ////////////////////////}
{////////////////////////////////////////////////////////////////////////////}
{/////////////////////////////// SIMPLEX START /////////////////////////////}
if i_basis=0 then
begin
iter:=0;
findved;
if done=false then
begin
writeln(f,'<H2>Применяем симплекс метод</H2>');
repeat
inc(iter);
findved;
preobr;
until (done=true) or (iter=20);
end;
end;
otvet;
{/////////////////////////////// SIMPLEX END ///////////////////////////////}
writeln(f,'</BODY>');
writeln(f,'</HTML>');
CloseFile(f);
{////////////////////////////////////////////////////////////////////////////}
end;
{////////////////////////////////////////////////////////////////////////////}
{///////// все, что ниже, относится к переходам между шагами ////////////////}
{////////////////////////////////////////////////////////////////////////////}
procedure TForm1.ExitClick(Sender: TObject);
begin
Close();
end;
procedure TForm1.Button_NextClick(Sender: TObject);
begin
step:=step+1;
Form1.Button_Prev.Enabled:=true;
case step of
1:Step1;
2:begin
Step2;
Form1.Button_Next.Enabled:=false;
end;
else step:=step-1;
end;
form1.Caption:='Симплекс метод - шаг '+inttostr(step);
end;
procedure TForm1.Button_PrevClick(Sender: TObject);
begin
step:=step-1;
Form1.Button_Next.Enabled:=true;
case step of
0:begin
Init;
Form1.Button_Prev.Enabled:=false;
end;
1:Step1;
else step:=step+1;
end;
form1.Caption:='Симплекс метод - шаг '+inttostr(step);
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
Init;
end;
В данной курсовой работе было рассмотрено решение задач линейного программирования симплекс методом. Задача была решена симплекс методом, так же задача была решена графически (построен график). Для представленной задачи была составлена программа на языке Delphi, программа находит значения целевой функции при условии максимизации значения.
Таким образом, вычислительная техника в настоящее время находит широкое применение, как в общей математике, так и в одном из её разделов – математических методах.
1. Зайченко Ю.П., Шумилова С.А. Исследование операций.
2. Лищенко «Линейное и нелинейное программирование», М. 2003
3. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М.2000
4. Орлов А.И. Теория принятия решений. Учебное пособие. - М.: Издательство "Март", 2004
5. Интернет