Реферат: Решение задач линейного программирования симплекс методом
Федеральное агентство по образованиюРФ
Федеральноегосударственное образовательное учреждение
Среднегопрофессионального образования
Барнаульскийстроительный колледж
Курсоваяработа.
Подисциплине: «Математические методы»
На тему:«Решение задач линейного программирования симплекс методом»
Выполнил: Нунгесер М.В.
Специальность: ПОВТ
Группа: 0881
Преподаватель: КлепиковаН.Н.
Барнаул 2010
Содержание:
Введение
Линейноепрограммирование
Симплекс метод
Постановка задачи
Разработка алгоритма
Решение задачи
Программная реализация на языке Delphi
Приложение
Заключение
Список используемой литературы
Введение
В последние годы вприкладной математике большое внимание уделяется новому классу задачоптимизации, заключающихся в нахождении в заданной области точек наибольшегоили наименьшего значения некоторой функции, зависящей от большого числапеременных. Это так называемые задачи математического программирования, возникающиев самых разнообразных областях человеческой деятельности и прежде всего вэкономических исследованиях, в практике планирования и организациипроизводства. Изучение этого круга задач и методов их решения привело ксозданию новой научной дисциплины, получившей позднее название линейногопрограммирования. В конце 40-х годов американским математиком Дж. Данцигом былразработан эффективный метод решения данного класса задач – симплекс-метод. Кзадачам, решаемых этим методом в рамках математического программированияотносятся такие типичные экономические задачи как «Определение наилучшегосостава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизациямежотраслевых потоков», « Задача о выборе производственной программы»,«Транспортная задача», «Задача размещения», «Модель Неймана расширяющейсяэкономики» и другие. Решение таких задач дает большие выгоды как народномухозяйству в целом, так и отдельным его отраслям.
Решение задачматематического программирования при помощи симплекс-метода традиционнымиспособами требует затрат большого количества времени. В связи с бурнымразвитием компьютерной техники в последние десятилетия естественно было ожидать,что вычислительная мощность современных ЭВМ будет применена для решенияуказанного круга задач.
Линейное программирование
Линейноепрограммирование — математическая дисциплина, посвящённая теории и методам решениязадач об экстремумах линейных функций на множествах n-мерного векторногопространства, задаваемых системами линейных уравнений и неравенств.
Линейное программированиеявляется частным случаем выпуклого программирования, которое в свою очередьявляется частным случаем математического программирования. Одновременнооно - основа нескольких методов решения задач целочисленного и нелинейногопрограммирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
Многие свойства задачлинейного программирования можно интерпретировать также как свойства многогранникови таким образом геометрически формулировать и доказывать их.
Математическаяформулировка задачи линейного программирования
Нужно определить максимумлинейной целевой функции (линейной формы)
/>
при условиях
/>/>
Иногда на xiтакже накладывается некоторый набор ограничений в виде равенств, но от нихможно избавиться, последовательно выражая одну переменную через другие иподставляя её во всех остальных равенствах и неравенствах (а также в функции f).
Такуюзадачу называют «основной» или «стандартной» в линейном программировании.Наиболее известным и широко применяемым на практике для решения общей задачилинейного программирования (ЛП) является симплекс метод.Симплекс методСимплекс метод — методлинейного программирования, который реализует рациональный перебор базисныхдопустимых решений, в виде конечного итеративного процесса, необходимоулучшающего значение целевой функции на каждом шаге.
Применениесимплекс-метода для задачи линейного программирования предполагаетпредварительное приведение ее формальной постановки к канонической форме с nнеотрицательными переменными: (X1, ..., Xn),где требуется минимизация линейной целевой функции при m линейныхограничениях типа равенств. Среди переменных задачи выбирается начальный базисиз m переменных, для определенности (X1, ..., Xm),которые должны иметь неотрицательные значения, когда остальные (n-m) свободныепеременные равны 0. Целевая функция и ограничения равенства преобразуются кдиагональной форме относительно базисных переменных, переменных, где каждая базиснаяпеременная входит только в одно уравнение с коэффициентом 1.
Данная формальная модельзадачи линейного программирования обычно задается в форме, так называемой />симплекс-таблицы, удобной для выполнения операцийсимплекс-метода:
Симплекс-таблица
1X1
X2
...Xm
Xm+1
...Xn
X0
A0,0
...A0,m+1
...A0,n
X1
A1,0
1 ...A1,m+1
...A1,n
X2
A2,0
1 ...A2,m+1
...A2,n
... ... ... ... ... ... ... ... ...Xm
Am,0
... 1Am,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между наборами свободных и базисных переменных нужно модифицировать исходную каноническуюмодель задачи путем приведения ее к диагональной форме относительно новогомножества базисных переменных. Для указанного преобразования можно формальноиспользовать процедуру исключения Гаусса, которая, как известно, состоитиз двух элементарных операций, применяемых к системе алгебраических уравнений (в данном случае ограничений — равенств):
· умножениеуравнения E1(X) = 0 на константу K1и замена уравнения E1(X) = 0 уравнением K1*E1(X) = 0;
· сложениеуравнений E1(X) = 0 и E2(X) = 0c последующей заменой уравнения E2(X) = 0уравнением E1(X) + E2(X) = 0.
ИсключенияГаусса позволяют привести систему уравнений к диагональной форме относительножелаемого множества переменных. В данном случае исключение Гаусса применяетсятак, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущегоэлемента 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) Каноническуюформу приводят к матричному виду.
4) Ищут первоедопустимое решение. Для этого матрица должна быть правильной. Матрица в ЗЛПназывается правильной, если она содержит минимум m правильных (базисных)столбцов, где m – число строк в матрице. Столбец в канонической ЗЛП называетсяправильным (базисным), если все его элементы равны нулю, кроме единственногоравного единице.
5) Если матрица неявляется правильной, то ее нужно сделать таковой с помощью искусственногобазиса. Для этого в матрицу нужно дописать столько базисных столбцов, чтобы ихобщее количество вместе с уже имеющимися базисными столбцами составляло m. После этого переходят к пункту 6.Если искусственный столбец выходит из базиса, то его удаляют из матрицы. Еслиудалены все искусственные столбцы, то получено первое допустимое решение. Еслиискусственные элементы не удается вывести из базиса, то система не имеетрешений.
6) Строятпоследовательность матриц. Нужно определить ведущий столбец, ведущую строку иведущий элемент. Элемент, соответствующий ведущей строке, удаляется из базиса,а на его место ставят элемент, соответствующий ведущему столбцу. Составляютуравнение пересчета матрицы, выполняют пересчет, а затем проверяют егорезультаты на оптимальность. Если решение не оптимально, то заново ограничиваютведущий элемент, ведущую строку и ведущий столбец.
Признаком оптимальностирешения является наличие в векторе решений только отрицательных или нулевыхкоэффициентов при всех ограничениях.
Ответ записываетсяследующим образом:
— Каждому отрицательномукоэффициенту в векторе решения ставится в соответствие нулевой коэффициент длясоответствующей переменной в ответе.
— Для каждого нулевогокоэффициента в векторе решения ставится в соответствие значение свободногочлена из строки, содержащей единицу в столбце данной переменной.
— Фиктивные переменные вответе не учитываются.
Ведущим может бытьназначен любой столбец, удовлетворяющий одному из условий:
1) Первый столбец,содержащий положительный элемент в векторе решений.
2) Столбец, содержащийнаибольший положительный элемент в строке решения.
3) Если столбецудовлетворяет условию max(Cj min bj/aij)при решении на max, и min(Cj min bj/aij)при решении задач на min.
Cj – коэффициент целевой функции встолбце j, aij – коэффициент в столбце j и строке i.
Решение задачиОпределиммаксимальное значение целевой функции F(X)= 3500 x1 +3200x2 +1500x3 приследующих условиях ограничений.
4x1 +2 x2 +5 x3 <=190
5x1 +3 x2 +4 x3 <=320
7x1 +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)этой системы уравнений имеет вид:
<p/>Базисныепеременные это переменные, которые входят только в одно уравнение системыограничений и притом с единичным коэффициентом.
Решимсистему уравнений относительно базисных переменных:
x4,x5,x6
Полагая,что свободные переменные равны 0, получим первый опорный план: X1= (0,0,0,190,320,454)
Посколькузадача решается на максимум, то ведущий столбец выбирают по максимальному отрицательномучислу и индексной строке. Все преобразования проводят до тех пор, пока неполучатся в индексной строке положительные элементы.
Переходимк основному алгоритму симплекс-метода.
X1
X2
X3
X4
X5
X6
св. чл.4
2 5 1 190 5 3 4 1 320 7 9 5 1 454 -3500 -3200 -1500Итерация №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 190/4 5 3 4 1 320 7 9 5 1 454 3500 3200 1500X1
X2
X3
X4
X5
X6
св. чл. 1 1/2 5/4 1/4 190/4 1/2 -9/4 -5/4 1 165/211/2
-15/4 -7/4 1 243/2 -1450 2875 875Итерация №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 159/100 41/100 -9/100 729/20 -191/100 -109/100 1 -9/100 1429/20 1 -15/22 -7/22 9/50 243/11 1886.36 413.64 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;
procedureExitClick(Sender: TObject);
procedureButton_NextClick(Sender: TObject);
procedureButton_PrevClick(Sender: TObject);
procedureFormCreate(Sender: TObject);
private
{ Privatedeclarations }
public
{ Publicdeclarations }
end;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 3do {подписываем что 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<=mthen
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)+']';
ifj<>m+1 then podpis[i,j].Caption:=podpis[i,j].Caption+' +';
{если поле не последнее, тодописываем плюсик}
end;
end;
for i:=1 to ndo {поля для ввода ограничений}
for j:=1 tom+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';
ifj<=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)+']';
ifj<>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 elsepole[i,j].Left:=pole[i,j].Left+70; //поля для правой части
//ограничений
end;
end else {если табличку создавать не надо, то разблокируемполя}
begin
for i:=1 ton+1 do
for j:=1 to m+1 do
begin
pole[i,j].Enabled:=true;
if i<=nthen znak[i].Enabled:=true;
end;
end;
end;
{/////////////////}
procedurewrite_system(strok,stolb: integer);
{записывает массив в видеуравнений}
var
i,j: integer;
begin
write(f,'<P>F(x)= ');
for j:=1 tostolb do
begin
write(f,matrix[strok,j]:0:3);
if j<stolbthen
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 tostolb do
BEGIN
write(f,matrix[i,j]:0:3);
ifj<stolb then write(f,'x<sub>',j,'</sub> ');
if j=stolb-1then
ifkanon=false then write(f,' ',znak[i].text,' ')
elsewrite(f,' = ');
if(matrix[i,j+1]>=0) and (j<stolb-1) then write(f,'+');
end;
writeln(f,'<br>');
end;
writeln(f,'</P>');
end;
{/////////////////}
procedurezapisat(strok,stolb: integer; v_strok,v_stolb:integer);
{записывает массив в видетаблички}
var
i,j:integer;
begin
writeln(f,'<TABLEBORDER BORDERCOLOR=black CELLSPACING=0 CELLPADDING=5>');
for i:=0 tostrok do
begin
writeln(f,'<TR>');
for j:=1 tostolb+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
ifi<>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;
{/////////////////}
procedurefindved;
{ищет ведущийэлемент}
var
i,j,k:integer;
temp: double;
begin
done:=false;
solve:=false;
is_ok:=true;
temp:=100000;
i0:=0;
j0:=0;
i:=n+1;
forj:=1 to m+y do
if (i0=0) or(j0=0) then
ifmatrix[i,j]>0 then
begin
j0:=j;
for k:=1 ton 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 mdo
ifmatrix[n+1,j]=0 then
for i:=1 ton do
if(matrix[i,j]<>0) and (matrix[i,j]<>1) then
begin
is_ok:=false;
j0:=j;
end;
if is_ok=falsethen
begin
temp:=100000;
for k:=1 to ndo
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
ifiter<>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 ton+1 do
for j:=1 tom+y+1 do
ifabs(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=falsethen
begin
write(f,'<P>Пересчет:</P>');
temp:=matrix[i0,j0];
for j:=1 tom+y+1 do matrix[i0,j]:=matrix[i0,j]/temp;
for i:=1 ton+1 do
begin
temp:=matrix[i,j0];
for j:=1 tom+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 thent:=j;
{если наши предположения (*)подтвердились, то запомним этот элемент}
end;
if t<>0then
begin
for k:=1 ton+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 thenall_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;
{/////////////////}
procedureotvet;
{выводитответ}
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(';
ifform1.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 mdo
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 ndo
ifall_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 ton+1 do
for j:=1 tom+1 do
begin
matrix[i,j]:=strtofloat(pole[i,j].Text);{Вводим значения в массив}
pole[i,j].Enabled:=false;{Блокируем поля}
if i<=nthen 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>Необходимо');
ifform1.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
ifznak[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
elseneed_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]<0then {если правая часть отрицательна,}
{то отнимаем всю строкуот нуля}
for j:=1 to m+y+1 domatrix[i,j]:=(0-matrix[i,j]);
kanon:=true;{системаприведена к каноническому виду}
{выведем ее в отчет}
write_system(n+1,m+y+1);
{если ф-ция на минимум,то нужно поменять знаки в последней строке}
ifform1.Extrem.ItemIndex=1 then
for j:=1 tom+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 tom+y do
if(matrix[i,j]=1) then
if(is_basis=false) then
begin
all_basis[i]:=j;
is_basis:=true;
for k:=1 ton do
ifk<>i then
if(matrix[k,j]<>0) then
if(is_basis=true) then
begin
is_basis:=false;
all_basis[i]:=0;
end;
end;
ifis_basis=false then
begin
i_basis:=i_basis+1;
y:=y+1;
for k:=1 ton+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=0then
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=0then
begin
iter:=0;
findved;
if done=falsethen
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;
{////////////////////////////////////////////////////////////////////////////}
{///////// все, что ниже, относится кпереходам между шагами ////////////////}
{////////////////////////////////////////////////////////////////////////////}
procedureTForm1.ExitClick(Sender: TObject);
begin
Close();
end;
procedureTForm1.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;
elsestep:=step-1;
end;
form1.Caption:='Симплексметод — шаг '+inttostr(step);
end;
procedureTForm1.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;
elsestep:=step+1;
end;
form1.Caption:='Симплексметод — шаг '+inttostr(step);
end;
procedureTForm1.FormCreate(Sender: TObject);
begin
Init;
end;
ЗаключениеВ даннойкурсовой работе было рассмотрено решение задач линейного программированиясимплекс методом. Задача была решена симплекс методом, так же задача быларешена графически (построен график). Для представленной задачи была составленапрограмма на языке Delphi, программанаходит значения целевой функции при условии максимизации значения.
Такимобразом, вычислительная техника в настоящее время находит широкое применение,как в общей математике, так и в одном из её разделов – математических методах.
Список используемой литературы
1. Зайченко Ю.П., Шумилова С.А.Исследование операций.
2. Лищенко «Линейное и нелинейноепрограммирование», М. 2003
3. А.Н. Карасев, Н.Ш. Кремер, Т.Н.Савельева «Математические методы в экономике», М.2000
4. Орлов А.И. Теория принятиярешений. Учебное пособие. — М.: Издательство «Март», 2004
5. Интернет