Обзор научно-технической литературы
Линейное программирование
Целочисленное линейное программирование - метод ветвей и границ
Алгоритм
Решение задач оптимизации при помощи средства «Поиск решения» в Microsoft Excel
Постановка задачи планирования производства в общем случае
Решение поставленной задачи планирования производства
Проверка признака допустимости и оптимальности базиса
Схема программы
Навигация
Линейное программирование
Решения задачи планирования производства симплекс методом
82416
знаков
8
таблиц
19
изображений
1.3 Линейное программирование
Линейное программирование — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации.
1.4 Математическая формулировка задачи линейного программирования
Нужно определить максимум линейной целевой функции (линейной формы)
при условиях
при 
.
Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя ее во всех остальных равенствах и неравенствах (а также в функции f).
Такую задачу называют "основной" или "стандартной" в линейном программировании.
1.5 Постановка задачи целочисленного программирования
По смыслу значительной части экономических задач, относятся к задачам линейного программирования, компоненты решения должны выражаться в целых числах, т.е. быть целочисленными. К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при загрузке оборудования, число судов при распределениях по линиям, число турбин в энергосистеме, число вычислительных машин в управляющем комплексе и многие другие.
Задача линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x1,x2,...,xn), при котором линейная функция
(1)
принимает максимальное или минимальное значение при ограничениях
=bi, i=1, 2…,m. (2)
хj ³ 0, j=1, 2,...,n.(3)
xj — целые числа (4)
2. Обзор основных алгоритмов решения задач ЛП
2.1 Целочисленное линейное программирование - метод отсечений Гомори
Целочисленное линейное программирование (сокращенно ЦЛП) занимается задачами линейного программирования с целочисленными переменными, общая задача формулируется следующим образом: найти max{сх|Ах ≤ b; х - целочисленный}. ЦЛП может рассматриваться так же, как поиск точки решетки, принадлежащей многограннику или как решение системы линейных уравнений с целыми неотрицательными переменными. Иными словами, в ЦЛП рассматриваются совместные ограничения неотрицательность и целочисленность.
2.1.1 Отсечения
С помощью отсечений выделяют целочисленные части полиэдров. Метод отсечений был разработан в конце 1950-х годов Гомори для решения целочисленных линейных программ с помощью симплекс-метода. Метод отсечений оказался полезным и с теоретической точки зрения он дает возможность описать целочисленную оболочку полиэдра.
Далее описывается метод отсечений Гомори, дающий алгоритм решения задач целочисленного линейного программирования. Данный метод, который также носит название метода отсекающих плоскостей, предназначен для решения ЦЗЛП (целочисленной задачи линейного программирования) в канонической форме.
Описываемая ниже версия алгоритма предназначена для решения полностью целочисленных задач, т.е. таких, у которых все параметры aij, cj, bi – целые.
2.1.2 Описание алгоритма
Приведем обобщенную схему алгоритма Гомори. Структурно он делится на так называемые большие итерации. Каждая большая итерация содержит этапы:
1.Сначала задача решается методами линейного программирования (малые итерации), обычно симплекс-методом, и анализируется результат, если результатом являются целые числа, то на этом решение заканчивается, а если дробные, то производят следующие операции:
2. В оптимальном плане (симплекс-таблице) выбирают строку, в которой целая часть дробного(!) свободного члена (P0) принимает наибольшее значение.
3.Построение для найденной компоненты условия отсечения.
Исходя из уравнения по данной строке xr=P0r - ar,1*x1 - … - ar,n*xn в систему ограничений добавляем неравенство, в котором коэффициенты будут дробными частями коэффициентов данного уравнения:
{P0r} –{ar,1}*x1 - … -{ar,n}*xn ≤ 0.
Переводим к каноническому виду добавляя новую переменную xn+1, получим:
{P0r} –{ ar,1}*x1 - … - {ar,n}*xn+xn+1= 0
И соответственно добавляем в симплекс-таблицу новый базисный вектор по новой переменной xn+1.
4.Переход на начало следующей большой итерации.
Замечание:
При добавлении в симплекс-таблицу нового базисного вектора по новой переменной xn+1 мы получаем недопустимое (отрицательное) решение. Для того, чтобы избавиться от недопустимого решения выбираем столбец замещения так, чтобы строкой замещения стала новая добавленная строка по переменной xn+1. Продолжаем пересчет симплекс-таблицы. Если снова получаем дробное решение, то еще вводим дополнительный базисный вектор, и так до получения целочисленного решения. Но следует заметить, что если область допустимых решений очень мала, то она может и не содержать целых значений, это необходимо проверить графически. Если область допустимых решений не содержит целочисленного решения, то в применении метода Гомори нет необходимости, целого решения не будет!
Похожие работы
... положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение. Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой ...
... определение базисных решений соответст- вует идентификации экстремальных точек , осуществляемой при геометрическом представлении пространства решений . Таким об- разом , максимальное число итераций при использовании симплекс- метода равно максимальному числу базисных решений задачи ЛП , представленной в стандартной форме . Это означает , что количество итерационных процедур симплекс-метода не ...
... - метод для решения задач линейного программирования. Задачи курсовой заботы: 1. привести теоретический материал; 2. на примерах рассмотреть симплекс метод; 3. представить данную курсовую работу в виде презентации. Математическое программирование Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи ...
... предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации. Формулировка задачи линейного программирования Нужно максимизировать при условиях при i = 1, 2, 3, . . ., m.. Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от ...
0 комментариев