Специальные задачи линейного программирования

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

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

по специальности: «Программное обеспечение вычислительной техники»

на тему:

Омск, 2011

Содержание

Введение

Глава 1. Теоретическая часть

1.1 Основные понятия линейного программирования

1.2 Основные свойства транспортной задачи

1.3 Основные теоремы решение

Глава 2. Практическая часть

2.1 Построение первичного опорного плана

2.2 Построение системы потенциалов (для значений)

2.3 Проверка плана на оптимальность

2.4 Улучшение плана

Введение

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

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

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

Глава 1. Теоретическая основа линейного программирования

1.1 Основные понятия линейного программирования транспортной задачи

линейное программирование оптимизационная задача

Объектом изучения является решение задач линейного программирования. Транспортных задач. Построение первично опорного плана.

Постановка задачи

Классическая транспортная задача ЛП формулируется следующим образом.

Имеется m пунктов производства (поставщиков) и n пунктов

потребления (потребителей) однородного продукта. Заданы величины:

- объем производства (запас) i-го поставщика, i=1, m;

- объем потребления (спрос) j-го потребителя, i=1, n;

- стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.

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

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

Транспортная задача, в которой суммарные запасы и суммарные потребности

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

вводится фиктивный n+1 потребитель, потребности которого

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

вводится фиктивный m+1 поставщик, запасы которого

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

Прежде чем решать транспортную задачу, необходимо проверить, к какой модели она принадлежит, и если необходимо, то привести ее к закрытой модели.

1.2 Основные свойства транспортной задачи

Математические модели любых транспортных задач ЛП обладают общими чертами, а именно,

1) коэффициенты целевой функции неотрицательны (стоимости перевозок не могут быть отрицательными величинами);

2) коэффициенты правых частей ограничений неотрицательны (запасы и потребности продукта);

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

В силу этих особенностей транспортная задача обладает следующими свойствами.

1.3 Теорема 1. Базисное решение закрытой модели транспортной задачи содержит m+n-1 базисных компонентов.

Доказательство. Количество базисных компонент определяется число линейно-независимых ограничений задачи. В транспортной задаче не все m+n ограничений линейно-независимы. Действительно, сложив первые m ограничений и следующие n ограничений задачи, получим

Но в закрытой модели выполняется балансовое равенство

поэтому получаем, что нетривиальная линейная комбинация строк ограничений (линейная комбинация с ненулевыми коэффициентами) равна нулю. Это означает, что среди ограничений задачи есть линейно-зависимое ограничение. Следовательно, число линейно-независимых ограничений равно m+n-1 и базис задачи состоит из m+n-1 компонент. Теорема доказана.

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

Теорема 2. Оптимальный план закрытой модели транспортной задачи существует всегда.

Доказательство. Оптимальное решение задачи ЛП существует, если, во-первых, существует допустимое решение и, во-вторых, целевая функция ограничена на этом допустимом решении.

Покажем существование допустимого решения. Так как суммарные запасы совпадают с суммарными потребностями то всегда можно найти такой план перевозок, который будет допустимым решением (все запасы вывозятся и все потребности выполняются в силу балансового равенства).

Покажем ограниченность целевой функции. Так как

Следовательно, L ограничена снизу нулем для всех допустимых решений. Теорема доказана.

Глава 2. Практическая часть

2.1 Построение первоначального опорного плана

Базисное решение закрытой модели транспортной задачи

Данная модель является открытой, так как А>В в этом случае нам надо добавить столбец, в стоимость мы поставим 0, а в запасы нужно добавить не достающие значение. В нашем случае 50.

Будет иметь следующий вид:

Теперь расставим значения, начнем с наименьшей стоимости.

Проверка занятых клеток (m+n-1) если окажется что число занятых клеток меньше (m+n-1), то дополним их до (m+n-1) нулями. Теперь найдем сумму занятых клеток, S = значение*стоимость.

S=70+10+180+210+40=510 (Данный план не оптимален.)

2.2 Построение системы потенциалов (для значений)

Используя первое условие оптимального плана, найдем m+n чисел, так чтобы сумма потенциалов для занятых клеток была ровна стоимости.

0= большему числу занятых клеток.

2.3 Проверка плана на оптимальность

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

2.4 Улучшение плана

Рассмотрим все свободные клетки, где произошло нарушение оптимального плана, и выберем ту в которой разность (Ai+Bj)-Cij наибольшее поставим (+), затем для этой клетки согласно утверждению о циклах стоимости единицы цикла, отметим эти клетки по переменно.

Размещено на Allbest.ru