Решение задачи линейного программирования симплекс-методом

Размещено на http://www.allbest.ru

ВВЕДЕНИЕ

симплекс программирование задача

Целью данной курсовой работы является решение конкретной задачи линейного программирования симплекс-методом. Во всех таких задачах требуется найти максимум или минимум линейной функции при условии, что её переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные уравнения, так и линейные неравенства. Каждая из этих задач является частным случаем общей задачи линейного программирования.

Симплекс-метод, известный также в нашей литературе под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов.

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит:

- умение находить начальный опорный план;

- наличие признака оптимальности опорного плана;

-умение переходить к не худшему опорному плану.

Симплекс метод - это характерный пример итерационных вычислений, используемых при решении большинства оптимизационных задач. В вычислительной схеме симплекс-метода реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки (обычно начало координат), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.

1.ОБЩАЯ ЧАСТЬ

1.1 Симплексный метод

Из переменных задачи выбирается начальный базис из 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 <&nbsp0:

A0,p = min A0,j < 0.

Столбец 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) = 0 c последующей заменой уравнения E2(X) = 0 уравнением E1(X) + E2(X) = 0.

Исключения Гаусса позволяют привести систему уравнений к диагональной форме относительно желаемого множества переменных. В данном случае исключение Гаусса применяется так, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента Aq,p, стали нулевыми, а ведущий элемент стал равным единице:

Ai,p = 0, если i не равно q и Ai,p = 1, если i = q.

Указанные шаги симплекс-метода повторяются, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой. Если положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение.

Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой перебор базисных допустимых решений. Однако, трудные для симплекс метода задачи на практике встречаются крайне редко, что объясняет широкое распространение и большую популярность данного метода линейного программирования по сравнению с другими подходами.

1.2 Постановка задач линейного программирования .Условия ЗЛП

Для производства столов и шкафов мебельная фабрика использует необходимые ресурсы. Нормы затрат ресурсов на одно изделие данного вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида приведены в следующей таблице:



Ресурсы	Нормы затрат ресурсов на одно изделие	Общее количество ресурсов
	Стол	Шкаф
Древесина (м3) I вида II вида Трудоемкость (человеко-ч.)	0,2 0,1 1,2	0,1 0,3 1,5	40 60 371,4
Прибыль от реализации одного изделия ($)	6	8

Определить, сколько столов и шкафов фабрике следует изготовить, чтобы прибыль от их реализации была максимальной.

1.3 Составление математической модели ЗЛП

Переменные

За X1 обозначим количество ед. продукции - стол

За X2 обозначим количество ед. продукции - шкаф

Целью задачи является:

Определить план выпуска продукции из условия максимизации его стоимости.

Определите ценность каждого ресурса (двойственные оценки) и его приоритет при решении задачи увеличения запаса ресурсов.

Определите суммарную стоимостную оценку ресурсов, используемых при производстве единицы каждого изделия. Выпуск какой продукции нерентабелен?

На сколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?

Определить, как изменится общая стоимость продукции и план выпуска при увеличении запасов сырья на 18 единиц;

Определить целесообразность включения в план изделия четвертого вида на изготовление, которого расходуется по две единицы каждого вида ресурсов ценой 70 ед.

Целевая функция:

Т.к цена единицы продукта 1 вида составляет 10, то для нахождения прибыли реализации ед. продукции 1 вида в кол-ве X1 составит 10X1.

Цена единицы продукта 2 вида составляет 14, то для нахождения прибыли реализации ед. продукции 2 вида в кол-ве X2 составит 14X2.

Аналогично для нахождение прибыли единицы продукции 3 вида составит 12X3

Поэтому целевая функции записывается в виде суммы дохода от продажи ед. продукции каждого вида:

F(x)=10X1+14X2+12X3->max

Ограничения:

При трудозатрате на изготовление ед. продукции каждого вида (значение приведены в таблице) первое ограничение примет вид:

При использование сырья для изготовление ед. каждого вида (значение приведены в таблице) второе ограничении примет вид:

При использование оборудование для изготовление ед. каждого вида (значение приведены в таблице) второе ограничении примет вид:

Условия не отрицательности позволяет ввести нижнею границу для выполнение расчетов, т.е X1>=0,X2>=0,X3>=0

Математическая модель ЗЛП в координатной форме записи:

F(x)=40X1+60X2+80X3->max

X1>=0,X2>=0,X3>=0

1.4 Решение ЗЛП средствами MS Exсel

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.

Определим максимальное значение целевой функции F(X) = 6x1+8x2 при следующих условиях - ограничений.

0.2x1+0.1x2<=40

0.1x1+0.3x2<=60

0.2x1+1.5x2<=371.4

0.2x1 + 0.1x2 + 1x3 + 0x4 + 0x5 = 40

0.1x1 + 0.3x2 + 0x3 + 1x4 + 0x5 = 60

0.2x1 + 1.5x2 + 0x3 + 0x4 + 1x5 = 371.4

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =	0,2 0,1 1 0 0 0,1 0,3 0 1 0 0,2 1,5 0 0 1

Решим систему уравнений относительно базисных переменных:

x3, x4, x5,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,40,60,371.4)

Базис	В	x1	x2	x3	x4	x5
x3	40	0.2	0.1	1	0	0
x4	60	0.1	0.3	0	1	0
x5	371.4	0.2	1.5	0	0	1
F(X0)	0	-6	-8	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai2

и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (0.3) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	min
x3	40	0.2	0.1	1	0	0	400
x4	60	0.1	0.3	0	1	0	200
x5	371.4	0.2	1.5	0	0	1	247.6
F(X1)	0	-6	-8	0	0	0	0

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5
x3	20	0.17	0	1	-0.33	0
x2	200	0.33	1	0	3.33	0
x5	71.4	-0.3	0	0	-5	1
F(X1)	1600	-3.33	0	0	26.67	0

Итерация №1.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты. В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее.

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (0.17) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	min
x3	20	0.17	0	1	-0.33	0	120
x2	200	0.33	1	0	3.33	0	600
x5	71.4	-0.3	0	0	-5	1	-
F(X2)	1600	-3.33	0	0	26.67	0	0

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5
x1	120	1	0	6	-2	0
x2	160	0	1	-2	4	0
x5	107.4	0	0	1.8	-5.6	1
F(X2)	2000	0	0	20	20	0

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:



Базис	В	x1	x2	x3	x4	x5
x1	120	1	0	6	-2	0
x2	160	0	1	-2	4	0
x5	107.4	0	0	1.8	-5.6	1
F(X3)	2000	0	0	20	20	0

Оптимальный план можно записать так: 

x1 = 120

x2 = 160

x5 = 107.4

F(X) = 6*120 + 8*160 = 2000

Для того чтобы решить задачу ЛП в табличном редакторе Microsoft Excel, необходимо выполнить следующие действия.

Ввести условие задачи:

 создать экранную форму для ввода условия задачи:

переменных,

целевой функции (ЦФ),

ограничений,

граничных условий;

 ввести исходные данные в экранную форму:

коэффициенты ЦФ,

коэффициенты при переменных в ограничениях,

правые части ограничений;

 ввести зависимости из математической модели в экранную форму:

формулу для расчета ЦФ,

формулы для расчета значений левых частей ограничений;

 задать ЦФ (в окне "Поиск решения"):

целевую ячейку,

направление оптимизации ЦФ;

 ввести ограничения и граничные условия (в окне "Поиск решения"):

ячейки со значениями переменных,

граничные условия для допустимых значений переменных,

соотношения между правыми и левыми частями ограничений.

Решить задачу:

 установить параметры решения задачи (в окне "Поиск решения");

 запустить задачу на решение (в окне "Поиск решения");

 выбрать формат вывода решения (в окне "Результаты поиска решения").

Рисунок 1 - Решение средствами MS Excel

2.СПЕЦИАЛЬНАЯ ЧАСТЬ

2.1 Среда программирования

Почему именно Delphi? В Delphi сделать первый шаг очень просто, она интуитивно понятна. Конечно, небольшому числу разработчиков по долгу службы нужны глубокие специфические знания, которые приходят со временем. А начинающим Delphi позволяет начать создавать программы сразу, не углубляясь в изучение внутренностей операционной системы, и даже собственной среды разработки. Поэтому программист может сразу сосредоточиться на логике работы будущей программы.

Delphi - это нечто иное, нежели Pascal, это совершенно другой качественный этап среды программирования. С помощью Delphi создаются приложения для операционной системы Windows, но помимо этого с помощью дополнительных средств можно написать, например, программы и для Linux. Среда Delphi легко расширяется установкой дополнительных модулей. Пользовательский интерфейс также хорошо настраиваемый - каждый организует рабочее пространство так, как ему будет удобно.

Delphi -- результат развития языка Турбо Паскаль, который, в свою очередь, развился из языка Паскаль. Delphi оказал огромное влияние на создание концепции языка C# для платформы .NET. Многие его элементы и концептуальные решения вошли в состав С#. Одной из причин называют переход Андерса Хейлсберга, одного из ведущих разработчиков Дельфи, из компании Borland Ltd. в Microsoft Corp.

Версия 1 была предназначена для разработки под 16-ти разрядную платформу Win16;

Версии со второй компилируют программы под 32-х разрядную платформу Win32;

Вместе с 6-й версией Delphi вышла совместимая с ним по языку и библиотекам среда Kylix, предназначенная для компиляции программ под операционную систему Linux;

Версия 8 способна генерировать байт-код исключительно для платформы .NET. Это первая среда, ориентированная на разработку мультиязычных приложений (лишь для платформы .NET);

Последующие версии (обозначаемые годами выхода, а не порядковыми номерами, как это было ранее) могут создавать как приложения Win32, так и байт-код для платформы .NET;

Delphi for .NET -- среда разработки Delphi, а так же язык Delphi (Object Pascal), ориентированные на разработку приложений для .NET.
Delphi - прекрасная система визуального объектно-ориентированного проектирования, одинаково радующая и новичков в программировании, и профессионалов. Начинающим Delphi позволяет сразу, с небольшими затратами времени и сил создавать прикладные программы, которые внешне неотличимы от программ, созданных профессионалами. А для опытного программиста Delphi открывает неограниченные возможности для создания сколь угодно сложных программ любого типа, в том числе, распределённых приложений, работающих с любыми базами данных.

2.2 Проектирование ЗЛП

Рисунок 2 - Главное меню моей программы

Рисунок 3 - Справка о программе

Рисунок 4 - Справка о разработчике

ЗАКЛЮЧЕНИЕ

Целью курсового проекта было решение задач линейного программирования симплекс-методом, составление алгоритма, составление программы по алгоритму и вывод результата на экран.

Для представленной задачи была разработано приложение на языке Delphi. Симплекс-метод является вычислительной процедурой представленной в алгебраической форме. Он непосредственно применяется к общей задаче линейного программирования в стандартной форме.

Он основан на пересчёте коэффициентов в системе уравнений и целевой функции при перемене мест свободной и базисной переменных можно формализовать и свести к преобразованию симплекс-таблицы.

В данном проекте был составлен оптимальный план выпуска продукции каждого вида, обеспечивающий максимальную прибыль.

СПИСОК ЛИТЕРАТУРЫ

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. Пособие для студ. Вузов. - М.: Высш. Шк., 1986.

2 Ашманов С.А., Линейное программирование. М.: Наука 1981

3. Банди Б. Основы линейного программирования /пер. с англ. Под ред. В.А. Волынского. - М.: Радио и связь, 1989.

4. Зайченко Ю.П., Шумилова С.А. Исследование операций.

5. Лищенко «Линейное и нелинейное программирование», М. 2003

6. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М.2000

7. Орлов А.И. Теория принятия решений. Учебное пособие. - М.: Издательство "Март", 2004

8. Интернет

9. Кузнецов А.В., Холод Н.И., Математическое программирование. Мн.: Высшая школа 1984

СПИСОК СОКРАЩЕНИЙ

ЗЛП - задача линейного программирования

ЛП - линейное программирование

Pn - условный вектор

ОДР - область допустимых решений

Т.Д - так далее

Т.Е - то есть

Т.К - так как

КП - курсовой проект

ПЗ - пояснительная записка

Размещено на www.allbest.

...