Программная реализация на языке Delphi
Содержание:
- Введение
- Линейное программирование
- Симплекс метод
- Постановка задачи
- Разработка алгоритма
- Решение задачи
- Программная реализация на языке Delphi
- Приложение
- Заключение
- Список используемой литературы
Введение
В последние
годы в прикладной математике большое
внимание уделяется новому классу задач
оптимизации, заключающихся в нахождении
в заданной области точек наибольшего
или наименьшего значения некоторой
функции, зависящей от большого числа
переменных. Это так называемые задачи
математического
Решение задач
математического
Линейное программирование
Линейное программирование - математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций на множествах 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 между наборами свободных и базисных переменных нужно модифицировать исходную каноническую модель задачи путем приведения ее к диагональной форме относительно нового множества базисных переменных. Для указанного преобразования можно формально использовать процедуру исключения Гаусса, которая, как известно, состоит из двух элементарных операций, применяемых к системе алгебраических уравнений ( в данном случае ограничений - равенств):
· умножение уравнения 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.
Исключения Гаусса
позволяют привести систему уравнений
к диагональной форме относительно
желаемого множества
Ai,p = 0, если i не равно q
и
Ai,p = 1, если i = q.
Указанные шаги
симплекс-метода повторяются, пока не
будет получена симплекс-таблица, которая
одновременно является прямо и двойственно
допустимой. Если положит в такой
симплекс-таблице текущие
Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 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) Ищут первое
допустимое решение. Для этого
матрица должна быть
5) Если матрица
не является правильной, то ее
нужно сделать таковой с
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 +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, включая элементы индексной строки, определяются по правилу прямоугольника.
- Программная структура бюджета США
- Программно-аппаратное оснащение таможенного поста
- Программно-аппаратные методы защиты информации
- Программное обеспечение
- Программное обеспечение
- Программное обеспечение
- Программное обеспечение
- Программируемые логические контроллеры
- Программируемые логические контроллеры
- Программная документация
- Программная защита информации
- Программная модель микропроцессора
- Программная реализация алгоритма Дейкстры
- Программная реализация метода Якоби