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

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

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего профессионального образования

Тобольская государственная социально-педагогическая академия им. Д.И. Менделеева

Кафедра математического анализа

Выпускная квалификационная работа

Тема:

Элементы линейного программирования

Студентки 4 курса ФМО

Мачитовой Анастасии Николаевны

Научный руководитель:

к.п.н., доцент Ярков В.Г.

Тобольск - 2010



СОДЕРЖАНИЕ

Введение

Глава 1. Основная задача линейного программирования

§1. Формулировка основной задачи линейного программирования

§2. Геометрическая интерпретация основной задачи

линейного программирования

§3. Симплекс - метод решения основной задачи

линейного программирования

§4. Примеры решения основной задачи линейного программирования

Глава 2. Прикладные задачи линейного программирования

§1. Транспортная задача

§2. Задача о назначениях

§3. Примеры решения прикладных задач линейного программирования

Заключение

Список использованной литературы



ВВЕДЕНИЕ

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

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно. С развитием вычислительной техники развивались и совершенствовались математические методы принятия решений. Сформировался раздел прикладной математики, который называется математическим программированием.

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

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

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

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

Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л.В. Канторовичем в работе «Математические методы организации и планирования производства» [10]. Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач -- симплекс-метод [12].

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

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

Все вышесказанное доказывает актуальность выбранной темы исследования.

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

Задачами выпускной квалификационной работы являются:

1) изучение теоретических аспектов линейного программирования - определений, свойств, основных типов задач;

2) изучение математических методов решения основных типов задач линейного программирования;

3) решение методами линейного программирования практических примеров прикладного содержания.

Объектом исследования является математическое программирование. Предметом исследования являются элементы линейного программирования.

Для решения поставленных в работе задач использовались следующие методы исследования:

- изучение теории линейного программирования, работа с литературой;

- решение практических примеров;

- оформление работы на компьютере.

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

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

Во второй главе рассмотрены важные примеры прикладных задач линейного программирования - транспортная задача и задача о назначениях. Изучены различные методы решения таких задач, приведены примеры.

Список работы содержит 12 наименований. Объем работы составляет 57 страниц машинописного текста.



ГЛАВА 1. ОСНОВНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

§1. Формулировка основной задачи линейного программирования

Основная задача линейного программирования состоит в следующем. Задана система

(1)

m линейных алгебраических уравнений с n неизвестными и линейная форма

(2)

относительно этих же производных.

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

Определение 1. Система (1) называется системой ограничений данной задачи.

Замечание 1. В ряде задач неизвестные должны удовлетворять не только равенствам, но и неравенствам. Эти неравенства также называются ограничениями задачи.

Определение 2. Всякое решение, удовлетворяющее системе (1), назовем допустимым или опорным.

Определение 3. Допустимое решение системы (1), минимизирующее форму F, назовем оптимальным.

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

Обратимся теперь к изучению системы ограничений (1). Задача имеет смысл лишь в том случае, когда система (1) совместна, т. е. когда (согласно теореме Кронекера - Капелли) ранги основной и расширенной матриц системы совпадают. Как известно из линейной алгебры, этот общий ранг r не может превосходить числа n неизвестных. При r=n решение системы (1) единственно и находится, например, по теореме Крамера. Если это решение допустимо то оно, очевидно, и является оптимальным (так как никаких других решений нет). Если же среди чисел имеется хотя бы одно отрицательное, то задача не имеет решения. В самом деле, оптимального решения не существует потому, что оно по самому определению должно быть неотрицательным, а единственное имеющееся решение таковым не является.

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

Покажем, как это сделать.

1) Очевидно, что форма F достигает наибольшей величины при тех же самых значениях неизвестных, при которых форма достигает наименьшей величины. Следовательно, максимизация формы F равносильна минимизации формы Тем самым задача максимизации сводится к задаче минимизации.

Замечание 4. Ясно, что наибольшее значение формы F равно наименьшему значению формы , взятому с обратным знаком.

2) Допустим теперь, что среди ограничений задачи имеется некоторое неравенство. Его всегда можно записать в виде

(3)

Введем новую, так называемую добавочную, неизвестную, связанную с неизвестными уравнением

(4)

Очевидно, что условие неотрицательности величины эквивалентно выполнимости неравенства (3). Иными словами, если система неотрицательных значений переменных удовлетворяет уравнению (4), то система удовлетворяет неравенству (3). И обратно, если величины неотрицательны и удовлетворяют неравенству (3), то величина найденная из уравнения (4), окажется неотрицательной.

Итак, ограничение - неравенство (3) эквивалентно ограничению - равенству (4). Следовательно, ценою введения в задачу добавочных неизвестных удается все ограничения - неравенства заменить ограничениями - равенствами. При этом число добавочных неизвестных равно числу ограничений - неравенств в исходной задаче.

При решении системы ограничений могут возникнуть следующие случаи:

1) Система ограничений несовместна, поэтому отыскать опорное решение невозможно (рис. 1).

2) Система ограничений имеет неограниченное множество решений (рис. 2).

3) Система ограничений имеет ограниченное, замкнутое множество решений (рис. 3).

4) Система ограничений имеет бесчисленное незамкнутое множество решений (рис. 4).

рис. 1 рис. 2 рис. 3 рис. 4

§2. Геометрическая интерпретация основной задачи линейного программирования

Рассмотрим задачу ЛП в стандартной форме записи:

(1)

при ограничениях

(2)

Рассмотрим эту задачу на плоскости, т.е. при п = 2. Пусть система неравенств (2) совместна (имеет хотя бы одно решение):

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

Если в системе ограничений (2) n = 3, то неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого a_i1х₁ + а_i2х₂ + а_i3х₁ = b_i, а условия не отрицательности -- полупространства с граничными плоскостями соответственно x_i = 0 (i = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений.

Пусть в системе (2) п>3, тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью а_i1х₁ + а_i2х₂ + … + а_inх_n = b_i i = 1,2,…, m, а условия неотрицательности -- полупространства с граничными гиперплоскостями x_j = 0, j = 1,2,…, n.

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

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

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

Выберем произвольное значение целевой функции . Получим . Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (1) параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения). Найдём частные производные целевой функции по и

(4)

(5)



Частная производная (4) ((5)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, и -- скорости возрастания соответственно вдоль осей и . Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор -- указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор перпендикулярен к прямым семейства

Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения.

С учетом системы ограничений строим область допустимых решений

Строим вектор наискорейшего возрастания целевой функции -- вектор градиентного направления.

Проводим произвольную линию уровня

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

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



§3. Симплекс - метод решения основной задачи линейного программирования

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в умении находить начальный опорный план; наличии признака оптимальности опорного плана; умении переходить к не худшему опорному плану.

Пусть ЗЛП представлена системой ограничений в каноническом виде:

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

Пусть система ограничений имеет вид

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

,

которая имеет предпочтительный вид

.

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю .

Пусть далее система ограничений имеет вид

Сведём её к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему

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

Пусть исходная ЗЛП имеет вид

(1)

(2)

(3)

причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

(4)

(5)

, , (6)

Задача (4)-(6) имеет предпочтительный план. Её начальный опорный план имеет вид

Если некоторые из уравнений (2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема 1. Если в оптимальном плане

(7)

М-задачи (4)-(6) все искусственные переменные , то план является оптимальным планом исходной задачи (1)-(3).

Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М-задачу, которая имеет начальный опорный план

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

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

Теорема 2. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

Признаки оптимальности

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

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

§4. Примеры решения основной задачи линейного программирования

1. Среди неотрицательных решений системы неравенств:

найти такое, при котором линейная форма достигает наименьшего значения.

Решение. Систему неравенств путем введения дополнительных переменных сводим к системе уравнений:



и подвергаем тождественным преобразованиям:

Одним из неотрицательных решений системы неравенств является решение Выразим теперь линейную форму через неосновные переменные:

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

2. Для пошива одного изделия требуется выкроить из ткани 6 деталей. На швейной фабрике были разработаны два варианта раскройки ткани. В таблице (расположенной ниже) приведены характеристики вариантов раскроя 10 м² ткани комплектность, т.е. количество деталей определенного вида, которые необходимы для пошива одного изделия. Ежемесячный запас ткани для пошива изделий данного типа составляет 405 м². В ближайший вечер планируется сшить 90 изделий.

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

Таблица 1

Характеристики вариантов раскроя отрезков ткани по 10м

Вариант раскроя	Количество деталей, шт./отрез	Отходы, м2/отрез
	1	2	3	4	5	6
1	60	0	90	40	70	90	0,5
2	80	35	20	78	15	0	0,35
Комплектность, шт./изделие	1	2	2	2	2	2

В данной задаче искомые величины явно не указаны, но сказано, что должен быть выполнен ежемесячный план по пошиву 90 изделий. Для пошива 90 изделий в месяц требуется раскроить строго определенное количество деталей. Крой производится из отрезков ткани по 10 м² двумя различными способами, которое позволяют получить различное число деталей. Поскольку заранее неизвестно, сколько ткани будет раскраиваться первым способом и сколько - вторым, то в качестве искомых величин можно задать количество отрезков ткани по 10м², раскроенных каждым из способов:

- количество отрезков ткани по 10м², раскроенных первым способом в течении месяца, [отрез./мес.];

- количество отрезков ткани по 10м², раскроенных первым способом в течение месяца, [отрез./мес.];

Целевая функция:

Целью решения задачи является выполнение плана при минимальном количестве отходов. Поскольку количество изделий строго запланировано (90 шт./мес.), то этот параметр не описывает ЦФ, а относится к ограничению, невыполнение которого означает, что задача не решена. А критерием эффективности выполнение плана служит параметр «количество отходов», который необходимо свести к минимуму. Поскольку при раскрое одного отреза (10м²) ткани по 1-му варианту получается 0,5м² отходов, а по 2-му варианту - 0,35м² (см. таблицу 1), то общее количество отходов при крое целевая функция имеет вид:

[]

Ограничения:

Количество раскроев ткани различными способами ограничивается следующими условиями:

· Должен быть выполнен план по пошиву изделий, другими словами, общее количество выкроенных деталей должно быть таким, чтобы из него можно было пошить 90 изделий в месяц, а именно: 1-го вида должно быть как минимум 90 и деталей остальных видов - как минимум по 180 (см. комплектность в табл.1).

· Расход ткани не должен превышать месячного запаса на складе;

· Количество отрезков раскроенной ткани не может быть отрицательным.

Ограничение по плану пошива пальто имеют следующую содержательную форму записи.

(Общее количество деталей №1 выкроенных по всем вариантам)(90 штук);

(Общее количество деталей №2 выкроенных по всем вариантам)(180 штук);

(Общее количество деталей №6 выкроенных по всем вариантам)(180 штук);

Математически эти ограничения записываются в виде:

Ограничение по расходу ткани имеет следующие формы записи:

Содержательную:

(общее количество ткани, раскроенной за месяц)(405м²)

Математическую:

Не отрицательность количества раскроенных отрезков задается в виде:

Таким образов, математическая модель задачи имеет вид:

,

3. Задача о планировании производства

Постановка задачи. Предприятие производит изделия трёх видов: U₁, U₂, U₃. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не мене b₁ единиц изделия U₁, не мене b₂ единиц изделия U₂ и не мене b₃ единиц изделия U₃. План может быть перевыполнен, но в определённых границах; условия спроса ограничивают количества произведённых единиц каждого типа: не более соответственно единиц. На изготовление изделий идёт какое-то сырьё; всего имеется четыре вида сырья: s₁, s₂, s₃, s₄, причём запасы ограничены числами единиц каждого вида сырья. Теперь надо узнать какое количество сырья каждого вида идёт на изготовление каждого вида изделий. Обозначим a_ij количество единиц сырья вида s_i (I= 1, 2, 3, 4), потребное на изготовление одной единицы изделия U_j (j= 1, 2, 3). Первый индекс у числа a_ij - вид изделия, второй - вид сырья. Значения a_ij сведены в таблицу (матрицу).

Сырье	Изделия
	U1	U2	U3
S1 S2 S3 S4	a11 a12 a13 a14	a21 a22 a23 a24	a31 a32 a33 a34

При реализации одно изделие U₁ приносит предприятию прибыль c₁, U₂ - прибыль c₂, U₃ - прибыль c₃. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.

Математическая модель. Элементами решения будут x₁, x₂, x₃ - количества единиц изделий U₁, U₂, U₃, которые мы произведём. Обязательность выполнения планового задания запишется в виде трёх ограничений - неравенств: x₁b₁, x₂b₂, x₃b₃.

Отсутствие изделий продукции (затоваривания) даёт нам ещё три ограничения - неравенства: x₁, x₂, x₃.

Целевая функция:

=c₁x₁+c₂x₂+c₃x₃>.

Система ограничений:



4. Задача о рациональном питании (задача о пищевом рационе)

Постановка задачи. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П₁, П₂, П₃, П₄; стоимость единицы каждого продукта равна соответственно С₁, С₂, С₃, С₄. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков - не менее b_i единиц; углеводов - не менее b₂ единиц; жиров - не менее b₃ единиц. Для продуктов П₁, П₂, П₃, П₄ содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице, где a_ij (i=1,2,3,4; j=1,2,3) - какие - то определённые числа; первый индекс указывает номер продукта, второй - номер элемента (белки, углеводы, жиры).

продукт	элементы
	белки	углеводы	жиры
П1 П2 П3 П4	A11 A21 A31 A41	A12 A22 A32 A42	A13 A23 A33 A43

Требуется составить такой пищевой рацион (т.е. назначить количества продуктов П₁, П₂, П₃, П₄, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.

Математическая модель. Обозначим x₁, x₂, x₃, x₄ количества продуктов П₁, П₂, П₃, П₄, входящих в рацион. Показатель эффективности, который требуется минимизировать, - стоимость рациона (обозначим её L): она линейно зависит от элементов решения x₁, x₂, x₃, x₄.

Целевая функция:



Система ограничений:

Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения x₁, x₂, x₃, x₄.

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных x₁, x₂, x₃, x₄ чтобы они удовлетворяли ограничениям - неравенствам и одновременно обращали в минимум линейную функцию этих переменных:

линейный симплекс прикладной экономический



ГЛАВА 2. ПРИКЛАДНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

§1. Транспортная задача

Имеется m поставщиков определенного вида продукции, назовем их

А, А, …, А, запасы которых составляют , ,…, единиц соответственно. Эта продукция используется n потребителями В, В,…, В. Объемы потребностей заданы , ,…, единиц соответственно. Стоимость перевозки единицы продукции от - го поставщика к - му потребителю известна для всех , и для всех , и равна .

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

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

Найти наименьшее значение линейной функции:

(1)

при условиях:

, (2)

(3)

. (4)

Определение 1. Задача (1) - (4) называется транспортной задачей по критерию стоимости.

Равенства (2) гарантируют полный вывоз продукции их всех пунктов производства. Равенства (3) обеспечивают полное удовлетворение спроса всех пунктов потребления. Условия (4) означают, что перевозки от потребителей к поставщикам исключены. Линейная функция (1) определяет величину транспортных издержек.

Набор величин , удовлетворяющих условиям (1) - (4) называется планом транспортной задачи. Переменные удобно нумеровать с помощью двух индексов, поэтому план целесообразно записывать в виде матрицы.

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

Совокупность величин , как и планы транспортной задачи удобно записывать в виде матрицы:

которую принято называть матрицей транспортных издержек.

Необходимым и достаточным условием разрешимости транспортной задачи является равенство:

(5)

При выполнении условия (5) модель транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.

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

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

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

Если опорном плане число отличных от нуля переменных равно в точности , то план является невырожденным, а если меньше - то вырожденным.

Условие транспортной задачи записывают в виде таблицы.

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

Для определения исходного опорного плана существует несколько методов. Два из них - метод северо-западного угла и метод минимального элемента рассматриваются ниже.

Поставщики	Потребители	Запасы
	B	B		B
A1
А2
A3
Потребности

Метод северо-западного угла

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

Определим левый верхний элемент матрицы , положив

Возможны два случая:

1) т.е. . Заполняем 1 - ю строку, начиная со 2 - го элемента, нулями.

2) т.е. . Заполняем 1 - й столбец, начиная со 2 - го элемента, нулями.

На этом заканчивается первый шаг метода. Допустим, что уже проделано шагов; опишем следующий - й шаг. Вычисляем левый верхний элемент матрицы из числа еще не определенных.

Пусть этим элементом будет . Полагаем где .

Если (случай 1 - й), то заполняем - ю строку матрицы, начиная с -го элемента, нулями. Если , то заполняем нулями - й столбец, начиная с - й строки. При этом

.

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

Метод минимального элемента

Шаг 1. Определяем минимальный элемент матрицы транспортных издержек . Если им оказался , то полагаем .

Возможны два случая:

1) ;

2) .

В первом случае определяем элементы -й строки матрицы , полагая ; во втором - элементы -го столбца этой матрицы: .

Шаг 2. Пусть - матрица, полученная из вычеркиванием либо -й строки (случай 1), либо -го столбца (случай 2).

Положим

Очевидно, что общее число строк и столбцов матрицы на единицу меньше числа строк и столбцов матрицы . Второй шаг состоит в проведении уже описанных операций применительно к матрице и величинам . В результате этого шага заполняется еще одна линия (строка или столбец) матрицы . Затем шаг 3 и т.д. Процесс продолжается до полного заполнения матрицы .

Метод минимального элемента всегда приводит к опорному плану исследуемой задачи. Число шагов, необходимых для построения плана транспортной задачи равно .

Применим метод минимального элемента к транспортной задаче, исходные данные которой были приведены в табл. 1.2.

На первом шаге минимальный тариф соответствует коммуникациям (3,3), (3,4), (3,5) и равен 2. Определяем , вычеркиваем столбец. На втором шаге получаем , вычеркиваем строку. Процесс продолжается до выполнения условий (2) - (3). Номер шага, как и в методе северо-западного угла, проставлен в скобках над значениями перевозок . Поэтому нетрудно восстановить процесс последовательного заполнения таблицы 1.3.

Таблица 1.4

10		6		5		10		8
	3(8)		13(5)
8		9		5		6		7
	7(7)								10(6)
10		4		2		2		2
					16(1)		2(2)
9		5		12		4		6
			0(4)				11(3)

Итак,; остальные переменные равны нулю.

Транспортные издержки построенного плана составляют 314 единиц стоимости.

В дальнейшем нам понадобиться критерий оптимальности плана транспортной задачи.

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

для (6)

, если (7)

Числа и называются потенциалами соответствующих поставщиков и потребителей.

Метод потенциалов.

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

Рассмотрим отдельную итерацию метода, ограничившись вначале невырожденным случаем. Итак, допустим, что уже проведено итераций метода потенциалов и в результате получен опорный план . Разберем подробно очередную -ю итерацию.

Этап 1. Вычисляются потенциалы и с их помощью производится проверка плана на оптимальность. Потенциалы , , и определяется из системы уравнений

+ (8)

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

Придадим неизвестной произвольное значение, например, положим . Допустим, что поставщик А снабжает в соответствии с планом пункты В В В. Тогда каждой базисной неизвестной отвечает в системе (8) определенное уравнение:

.

Из этих уравнений определим все . Далее аналогичным способом определим для тех А, которые снабжают один из пунктов В

. Например, если А снабжает пункт В то

,

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

Можно показать, что подобным маршрутом могут быть соединены любые два пункта рассматриваемой задачи и притом единственным образом. Следовательно, при заданном величины , определяются однозначно для всех пунктов транспортной задачи. Нетрудно усмотреть, что если бы мы задались произвольными значением любой из величин или , то получившиеся в результате числа отличались бы от , , вычисленных в предложении =0, на некоторую постоянную. Отсюда, в частности, следует, что величина + определяется однозначно для любых

Далее составляется матрица:

(9)

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

Этап 2. Улучшение плана. Определяем разрешающую коммуникацию из условия:

Переходим к построению цикла пересчета, замыкающегося на элементе (очевидно =0). Базисные перевозки из цикла пересчета образуют цепочку вида:

(10)

Построив цепочку можно сформировать новый план Положим:

(11)

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

(12)

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

(13)

Поскольку при невырожденной ситуации , то из отношения (13) вытекает, что .

§2. Задача о назначениях

Пусть требуется выполнить различных работ и имеется механизмов (машин) для их выполнения, причем каждый механизм может использоваться на любой работе. Производительность каждого механизма на различных работах, вообще говоря, различна. Задача заключается в таком распределении механизмов по работам, при котором суммарная производительность максимальна. Обозначим через производительность го механизма на й работе. Для построения математической модели сопоставим каждому из возможных вариантов распределения машин по работам набор значений неизвестных , относительно которых условимся, что = 1, если й механизм, назначается на ю работу , и = 0, если й механизм назначается не на ю работу. Для любого варианта среди чисел должно быть точно единиц, причем должны выполняться условия:

, (каждый механизм назначается на одну работу);

, (на каждую работу назначен один механизм).

Суммарная производительность в приданом варианте назначения машин на работы выразится суммой:

Таким образом, математическая модель рассматриваемой задачи будет такой:

max (1)

(2)

(3)

Условия (4) выводят задачу о назначениях из класса задач линейного программирования, так как они не линейны. Задачи, в которых на переменные налагаются такие условия, называются задачами с булевыми переменными. Известно, что в транспортной задаче при целочисленных исходных данных всегда можно найти целочисленные оптимальные планы, поэтому в задаче о назначениях условия (4) можно заменить условиями неотрицательности:

(5)

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

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

min ц(Y) = бв (6)

бв (7)

где неизвестные числа (потенциалы) б и в объединены в вектор Y = (бб…, бв, в,…, в).

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

Теорема 1. для того, чтобы вариант назначения был оптимальным, необходимо и достаточно существование чисел бб…, бв, в,…, в, таких, что:

бв (8)

бв, для () из базиса (9)

Метод потенциалов

Значения переменных можно расставить произвольно, например, методом максимального элемента или методом Фогеля. Для вычисления потенциалов необходимо, чтобы число базисных переменных было равно . Поэтому в число базисных переменных введем базисных нулей. Последние должны быть расставлены так, чтобы базисные элементы матрицы X не образовывали циклов.

Вычисляются потенциалы, затем для небазисных пар индексов

Определяются оценки по формуле:



г бвс.

Если все оценки неотрицательны (г), то процесс окончен: =1 соответствуют оптимальному варианту назначения. Если имеются отрицательные оценки (г < 0), необходимо выбрать разрешающую клетку (пусть она соответствует наименьшей отрицательной оценке), построить цикл пересчета, поставить в разрешающую клетку знак +, присвоить ей номер () и в дальнейшем разрешающую клетку считать четной вершиной, определить величину с и внести изменения в цикле: переменные которые находятся в нечетных вершинах, уменьшить на величину с, а переменные в четных вершинах увеличить на эту же величину.

Венгерский метод.

Пусть С =

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

Определение. Две матрицы C и D назовем здесь эквивалентными, если одна из них получается из другой прибавлением к элементам каждой строки одного и того же числа (для разных строк эти числа могут быть разными) и прибавлением к элементам каждого столбца одного и того же числа (для разных столбцов эти числа могут быть различны)

Алгоритм венгерского метода.

Предварительный этап.

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

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

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

Основной этап.

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

Если число отмеченных звездочкой нулей равно , то процесс окончен: места, занимаемые нулями со звездочкой, соответствуют переменным равным 1, в оптимальном варианте назначения.

Если нулей со звездочкой меньше , то

П.2. помечаем знаком «+» сверху столбцы матрицы, в которых есть , и считаем эти столбцы занятыми.

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

Если в матрице нет незанятых нулей, то переходим к пункту 5.

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

П.3. Столбец, в котором находится , лежащий в той же строке, что и только что отмеченный штрихом нуль, считаем снова незанятым и знак «+» сверху снимаем. Строку, в которой находится наш объявляем занятой и помечаем знаком «+» справа. Возвращаемся к третьему абзацу пункта 2.

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

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

П.5. находим минимальный элемент среди незанятых элементов матрицы (пусть он будет равен ) и вычитаем его из всех незанятых строк, а затем прибавляем ко всем занятым столбцам. Никакие пометки при этом не снимаются. Получается матрица, эквивалентная предыдущей, и содержащая незанятые нули. Возвращаемся к четвертому абзацу п.2.

Пример использования алгоритма (см. § 3)

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



§3. Примеры решения прикладных задач линейного программирования

1. Пусть матрицы данных (табл. 1.2) имеет следующий вид:

Таблица 1.2

Поставщики	Потребители	Запасы
	В	В	В	В	В
А1	10	6	5	10	8	16
А2	8	9	5	6	7	17
А3	10	4	2	2	2	18
А4	9	5	12	4	6	11
Потребности	10	13	16	13	10

В каждой клетке указаны стоимости перевозки единицы продукции (например, число 7 в клетке из второй строки и пятого столбца обозначает стоимость перевозки единицы продукции из пункта А в пункт В).

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

Таблица 1.3

10		6		5		10		8
	10		6
8		9		5		6		7
			7		10
10		4		2		2		2
					6		12
9		5		...

Подобные документы

• Симплекс метод в форме презентации

  Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
  
  курсовая работа [65,3 K], добавлен 30.11.2010
  

• Последовательность решения задач линейного программирования симплекс-методом

  Обыкновенные и модифицированные жордановы исключения. Последовательность решения задач линейного программирования симплекс-методом применительно к задаче максимизации: составлении опорного плана решения, различные преобразования в симплекс-таблице.
  
  курсовая работа [37,2 K], добавлен 01.05.2011
  

• Методы решения задач математического моделирования

  Основные понятия математического моделирования, характеристика этапов создания моделей задач планирования производства и транспортных задач; аналитический и программный подходы к их решению. Симплекс-метод решения задач линейного программирования.
  
  курсовая работа [2,2 M], добавлен 11.12.2011
  

• Векторное пространство. Решение задач линейного программирования графическим способом

  Общее понятие вектора и векторного пространства, их свойства и дополнительные структуры. Графический метод в решении задачи линейного программирования, его особенности и область применения. Примеры решения экономических задач графическим способом.
  
  курсовая работа [1,2 M], добавлен 14.11.2010
  

• Решение задач линейного программирования симплекс методом

  Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
  
  курсовая работа [197,1 K], добавлен 09.04.2013
  

• Теория информации. Статистический подход

  Статистический подход к измерению правовой информации. Графический метод решения задач линейного программирования. Методика решения задач линейного программирования графическим методом. Количество информации как мера неопределенности состояния системы.
  
  контрольная работа [79,4 K], добавлен 04.06.2010
  

• Метод линейного программирования

  Сущность линейного программирования. Изучение математических методов решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейной целевой функцией. Нахождение точек наибольшего или наименьшего значения функции.
  
  реферат [162,8 K], добавлен 20.05.2019
  

• Симплекс-метод

  Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
  
  контрольная работа [66,3 K], добавлен 06.04.2012
  

• Векторы, пространства, гиперплоскости, гиперповерхности

  Системы линейных уравнений и интерпретация их решений как пересечение гиперплоскостей в n-мерном координатном пространстве. Размерность и подпространства линейного пространства. Оптимизационные задачи линейного программирования. Суть симплекс-метода.
  
  курсовая работа [132,2 K], добавлен 10.01.2014
  

• Метод Гомори

  Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
  
  курсовая работа [67,5 K], добавлен 25.11.2011
  

• Определение целевой функции симплекс-методом

  Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
  
  курсовая работа [219,4 K], добавлен 17.04.2013
  

• Симплекс-метод

  Составление математической модели задачи. Определение всевозможных способов распила 5-метровых бревен на брусья 1,5, 2,4, 3,2 в отношении 1:2:3 так, чтобы минимизировать общую величину отходов. Решение задачи линейного программирования симплекс-методом.
  
  задача [26,1 K], добавлен 27.11.2015
  

• Методы нахождения безусловного и условного экстремума

  Развитие численных линейных методов решения задач линейного программирования. Знакомство с методами поиска целевой функции: равномерный симплекс, методы Коши, Ньютона, сопряжённого градиенты, квазиньютоновский метод. Алгоритмы нахождения экстремума.
  
  курсовая работа [716,1 K], добавлен 12.07.2012
  

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

  Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
  
  задача [656,1 K], добавлен 01.06.2016
  

• Максимумы, минимумы в геометрии

  Понятия максимума и минимума. Методы решения задач на нахождение наибольших и наименьших величин (без использования дифференцирования), применение их для решения геометрических задач. Использование замечательных неравенств. Элементарный метод решения.
  
  реферат [933,5 K], добавлен 10.08.2014
  

• Системы линейных неравенств

  Однородные системы линейных неравенств и выпуклые конусы. Применение симплекс-метода для отыскания опорного решения системы линейных неравенств, ее геометрический смысл. Основная задача линейного программирования. Теорема Минковского, ее доказательство.
  
  курсовая работа [807,2 K], добавлен 03.04.2015
  

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

  История зарождения и создания линейного программирования. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей. Методы составления начального опорного плана. Понятие потенциала и цикла. Задача, двойственная к транспортной.
  
  курсовая работа [166,7 K], добавлен 17.07.2002
  

• Задачи математического программирования

  Понятие и виды задач математического линейного и нелинейного программирования. Динамическое программирование, решение задачи средствами табличного процессора Excel. Задачи динамического программирования о выборе оптимального распределения инвестиций.
  
  курсовая работа [126,5 K], добавлен 21.05.2010
  

• Численные методы решения задач строительства автомобильных дорог

  Проектирование методов математического моделирования и оптимизации проектных решений. Использование кусочной интерполяции при решении задач строительства автомобильных дорог. Методы линейного программирования. Решение специальных транспортных задач.
  
  методичка [690,6 K], добавлен 26.01.2015
  

• Решение и постоптимальный анализ задачи линейного программирования

  Теоретические положения симплекс-метода и постоптимального анализа. Построение математической модели задачи. Нахождение ценностей ресурсов. Определение относительных и абсолютных диапазонов изменения уровней запасов дефицитных и недефицитных ресурсов.
  
  курсовая работа [86,7 K], добавлен 19.11.2010
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам