Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

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

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

1. если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот;

2. коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи;

3. свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи;

4. матрица ограничений двойственной задачи получается путем транспортирования матрицы ограничений прямой задачи;

5. знаки неравенств в ограничениях изменяются на противоположные;

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

Виды математических моделей двойственных задач могут быть представлены в таблице (табл. 1.1).

Таблица 1.1

Виды математических моделей двойственных задач

Таким образом, прежде чем записать двойственную задачу для данной исходной, систему ограничений исходной задачи необходимо привести к соответствующему виду. [3, с.114-115]

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

(1.10)

Если прямая (а значит, и двойственная) задача разрешима, то в каждой паре двойственных условий одно является свободным, а другое закрепленным. Любое из условий называется свободным, если оно выполняется как строгое неравенство хотябы для одного оптимального вектора. Условие называется закрепленным, если оно выполняется как равенство для всех оптимальных векторов.

Двойственную задачу выгоднее решать, чем прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений. [2, c 70-71]

Симплексный метод позволяет наряду с получением решения прямой задачи получать и решение двойственной задачи. Этот результат и лежит в основе двойственного симплексного метода решения задачи. Суть метода состоит в таком последовательном переборе угловых точек допустимого множества Q₀ двойственной задачи, при котором значение целевой функции возрастает, т. е. в применении симплексного метода к решению двойственной задачи. Будем предполагать, что задача невырождена, т. е. каждой угловой точке множества Q₀ соответствует квадратная невырожденная система уравнений размерности m, матрицу которую и называют двойственным базисом прямой задачи. Вместе с тем двойственный симплекс–метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными).

Отыскание решения задачи двойственным симплекс-методом включает в себя следующие этапы:

1. Находят псевдоплан задачи.

2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.

3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р₀ и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)–и строки к соответствующим отрицательным элементам разрешающей строки.

4. Находят новый псевдоплан и повторяют все действия начиная со второго этапа.

Двойственный симплексный метод называют также методом последовательного уточнения оценок, поскольку угловые точки задачи, возникающие при итерациях, можно рассматривать как приближенные значения точной оценки у*, т. е. как приближенные оценки влияния условий задачи на величину минимума целевой функции. [2, c.87-92]

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

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

Метод решения таких задач, предложенный Гомори, основан на симплексном методе и состоит в следующем. Симплексным методом находится оптимальный план задачи без учета условия целочисленности. Если оптимальный план целочисленный, то вычисления заканчивают; если же оптимальный план содержит хотя бы одну дробную компоненту X_i, то накладывают дополнительное ограничение, учитывающее целочисленность компонент плана, и вычисления симплексным методом продолжают до тех пор, пока либо будет найден целочисленный оптимальный план, либо доказано, что задача не имеет целочисленных оптимальных планов. [3 c.122-123]

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

2. Области применения и ограничения использования линейного программирования для решения экономических задач

Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов, производственно-транспортных и других задач). [2, c.92]

Рассмотрим постановку задачи о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексом j . Товары будем обозначать . Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингредиентами . Пусть их число равно m; припишем им индекс i . Они ограничены, и их количества равны соответственно условных единиц. Таким образом, - вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т. д. Примем в качестве такой меры, например, цену реализации , т. е. — вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов называют технологической и обозначают буквой А. Имеем . Обозначим через план производства, показывающий, какие виды товаров нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах. Так как - цена реализации единицы j-й продукции, цена реализованных единиц будет равна , а общий объем реализации примет вид (формула 2.1). Это — целевая функция, которую нужно максимизировать.

(2.1)

Так как - расход i-го ресурса на производство единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить единиц (формула 2.2).

(2.2)

Чтобы искомый план был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объёмы выпуска продукции .

В модель задачи о наилучшем использовании ресурсов входят: целевая функция (формула 2.3), система ограничений (формула 2.4) и условия неотрицательности (формула 2.5)

(2.3)

(2.4)

(2.5)

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

Характеристики

Список файлов курсовой работы