Курсовая работа: Применение линейного программирования для решения экономических задач (оптимизация прибыли)

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

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

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

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

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

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

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

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

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

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

Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов, производственно-транспортных и других задач). [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)

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

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

Сущность задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму. Более сложные постановки ведут к задачам целочисленного программирования.

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления  в n пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через  тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через  – запасы груза в i-м пункте отправления, через  – потребности в грузе в j–м пункте назначения, а через  – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции (формула 2.7) при определенных ограничениях (формула 2.8) и условиях неотрицательности (формула 2.9).

Страницы: 1, 2, 3, 4, 5, 6, 7