Линейное программирование

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

Федеральное государственное бюджетное образовательное

учреждение высшего образования

Ингушский государственный университет

Физико-математический факультет

Кафедра математики

Курсовая работа

Линейное программирование

Выполнил:

Ажигов С.М.

Магас 2016



Содержание

Введение

I. Теоретический раздел

1.1 Линейное программирование

1.2 Формулировка задачи

1.3 Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования

1.4 Математические основы решения задачи линейного программирования графическим способом

1.4.1 Математический аппарат

2. Теоретическое введение

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

2.2 Методы решения задач линейного программирования

2.2.1 Симплекс метод

2.2.2 Геометрический метод

2.3 Двойственная задача

2.4 Транспортная задача

II. Практический раздел

Заключение

Список литературы



Введение

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

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

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

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

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

2) Разобрать алгоритм решения ЗЛП геометрическим методом.

3) Решить поставленные задачи, используя рассмотренный метод решения задач линейного программирования.



I. Теоретический раздел

1.1 Линейное программирование

линейный программирование математический графический

Что же такое линейное программирование? Это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

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

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

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

- рационального использования сырья и материалов; задачи оптимизации раскроя;

- оптимизации производственной программы предприятий;

- оптимального размещения и концентрации производства;

- составления оптимального плана перевозок, работы транспорта;

- управления производственными запасами;

- и многие другие, принадлежащие сфере оптимального планирования.

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

Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.

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

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

1.2 Формулировка задачи

Даны линейная функция

Z=С₁ х₁ +С₂ х₂ +...+С_N x_N (1.1)

и система линейных ограничений

a₁₁ x₁ + a₂₂ x₂ +... + a_1N Х_N = b₁

a₂₁ x₁ + a₂₂ x₂ +... + a_2N Х_N = b₂

...............

a_i1 x₁ + a_i2 x₂ +... + a_iN Х_N = b_i (1.2) ...............

a_M1 x₁ + a_M2 x₂ +... + a_MN Х_N = b_M

x_j 0 (j = 1, 2, ..., n) (1.3)

где а_ij, b_j и С_j - заданные постоянные величины.

Найти такие неотрицательные значения х₁, х₂, ..., х_n, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1) минимальное значение.

Общая задача имеет несколько форм записи.

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях

А₁ х₁ + А₂ x₂ +... + А_N x_N = А_о, X₀ (1.4)



где С = (с₁, с₂, ..., с_N ); Х = (х₁, х₂, ..., х_N ); СХ - скалярное произведение; векторы A₁ = A₂ =, ..., A_N состоят соответственно из коэффициентов при неизвестных и свободных членах.

Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А₀ Х₀, где С = (с₁, с₂, ..., с_N ) - матрица-cтрока; А = (а_ij ) - матрица системы; Х =(x_ij )- матрица-столбец, А₀ = (а_i ) матрица-столбец

Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = С_j х_j при ограничениях

0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х₁, х₂, ..., х_N ), удовлетворяющий условиям (1.2) и (1.3).

0пределение 2. План Х = (х₁, х₂, ..., х_N ) называется опорным, если векторы А (i = 1, 2, ..., N), входящие в разложение (1.4) с положительными коэффициентами х, являются линейно независимыми.

Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

0пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным.

0пределение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.

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

1.3 Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования

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

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

Частными случаями линейных пространств являются вещественная прямая, плоскость, геометрическое трехмерное пространство.

Вектор л₁ a¹ + л₂ a² + …+ л_m a^m называется линейной комбинацией векторов а¹ а², ..., а^m с коэффициентами л₁, л_2, л_m,

Система векторов линейного пространства а¹ а², ..., а^m называется линейно зависимой, если существуют такие числа л₁, л_2, л_m не равные одновременно нулю, что их линейная комбинация л₁ a¹ + л₂ a² + …+ л_m a^m равняется нулевому вектору (вектору, все компоненты которого равны нулю). В противном случае систему а¹, а², ..., а^m называют линейно независимой, т. е. линейная комбинация данных векторов может быть равна нулевому вектору только при нулевых коэффициентах л₁, л_2, …, л_m

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

Линейное пространство обычно обозначают как Rⁿ, где n -- его размерность.

Любое подмножество данного линейного пространства, которое само обладает свойствами линейного пространства, называется линейным подпространством. Множество Н, получаемое сдвигом некоторого линейного подпространства L€ Rⁿ на вектор a€ Rⁿ: H=L+a, называется аффинным множеством (пространством). Если фундаментальным свойством любого линейного пространства или подпространства является принадлежность ему нулевого вектора, то для аффинного множества это не всегда так. На плоскости примером подпространства является прямая, проходящая через начало координат, а аффинного множества -- любая прямая на плоскости. Характеристическим свойством аффинного множества является принадлежность ему любой прямой, соединяющей две любые его точки. Размерность аффинного множества совпадает с размерностью того линейного подпространства, сдвигом которого оно получено.

Если рассматривается некоторое линейное пространство Rⁿ, то принадлежащие ему аффинные множества размерности 1 называются прямыми, а размерности (n-1)--гиперплоскостями. Так, обычная плоскость является гиперплоскостью для трехмерного геометрического пространства R³, а прямая -- гиперплоскостью для плоскости R². Всякая гиперплоскость делит линейное пространство на два полупространства.

Множество V векторов (точек) линейного пространства Rⁿ называется выпуклым, если оно содержит отрезок прямой, соединяющей две его любые точки, или, другими словами, из того, что a€V и b€V, следует, что х = (1- л) х а+ л х b€ V, где 0 ? л? 1.

Линейная комбинация векторов а¹, а²... а^m называется выпуклой, если л_i ?0, i€1:m и

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

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

Точка v выпуклого множества V называется его угловой (крайней) точкой, если она не является внутренней точкой ни для какого отрезка, концы которого принадлежат множеству V. Угловые точки выпуклого многогранника являются его вершинами, а сам он -- выпуклой оболочкой своих вершин.

Множество К называется конусом с вершиной в точке x₀, если x₀ € К, и из того, что некоторая точка х принадлежит К ( х € К ), следует, что в К содержится и луч, начинающийся в х₀ и проходящий через х, т. е.

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

1.4 Математические основы решения задачи линейного программирования графическим способом

1.4.1 Математический аппарат

Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = 3.

Наиболее наглядна эта интерпретация для случая n = 2, т.е. для случая двух переменных x₁ и x₂. Пусть нам задана задача линейного программирования в стандартной форме

Возьмём на плоскости декартову систему координат и каждой паре чисел (x₁, x₂ )поставим в соответствие точку на этой плоскости.

Обратим прежде всего внимание на ограничения x₁ ?0 и x₂ ? 0. Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида a₁ x₁ + a₂ x₂ ? b. Сначала рассмотрим область, соответствующую равенству a₁ x₁ + a₂ x₂ = b. Как Вы, конечно, знаете, это прямая линия. Строить её проще всего по двум точкам.

Пусть b ? 0. Если взять x₁ = 0, то получится x₂ = b/a₂. Если взять x₂ = 0, то получится x₁ = b/a₁. Таким образом, на прямой лежат две точки (0, b/a₂ ) и (b/a₁, 0). Дальше через эти две точки можно по линейке провести прямую линию (рисунок 2).

Если же b=0, то на прямой лежит точка (0, 0). Чтобы найти другую точку, можно взять любое отличное от нуля значениеx₁ и вычислить соответствующее ему значение x₂.

Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части a₁ x₁ + a₂ x₂ < b, а в другой наоборот a₁ x₁ + a₂ x₂ > b. Узнать, в какой полуплоскости, какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0, 0).



2. Теоретическое введение

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

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

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

можно представить в виде системы двух неравенств (см. рис.2.1)

ЦФ при фиксированном значенииопределяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

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

Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

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

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

2.1.1 Симплекс метод

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1, ..., Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1, ..., Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1:

X0 + A0, m+1*Xm+1 +... + A0, n*Xn = A0, 0

X1 + A1, m+1*Xm+1 +... + A1, n*Xn = A1, 0

................

Xi + Ai, m+1*Xm+1 +... + Ai, n*Xn = Ai, 0

................

Xm + Am, m+1*Xm+1 +... + Am, n*Xn = Am, 0

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

Симплекс-таблица

	1	X1	X2	...	Xm	Xm+1	...	Xn
X0	A0, 0	0	0	...	0	A0, m+1	...	A0, n
X1	A1, 0	1	0	...	0	A1, m+1	...	A1, n
X2	A2, 0	0	1	...	0	A2, m+1	...	A2, n
...	...	...	...	...	...	...	...	...
Xm	Am, 0	0	0	...	1	Am, m+1	...	Am, n

Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1, ..., Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm+1, ..., Xn - свободные переменные задачи.

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

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

2.1.2 Методика решения задач ЛП графическим методом

I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.2). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

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

IV. Если ОДР не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V. Построить вектор =(, который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ - против направлениявектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

VII. Определить координаты точки max (min) ЦФ . и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

2.1.3 Геометрический метод

Применяется для задач с двумя переменными. Метод решения состоит в следующем:

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



a11 x1 + a11 x2 + …… + a11 xn = b1,

a21 x1 + a22 x2 + …… + a2n xn = b2,

…………………………………………

am1 x1 + am2 x2 + …… + amn xn = bm.

Находим множество всех точек х1, х2, удовлетворяющим всем неравенствам. Такое множество называется областью допустимых решений. Строим вектор и перемещаем линию уровня, который задается уравнением: с1х1+с2х2 = const в направлении вектора до последней точки пересечения с ОДР. Эта точка и дает решение задачи Lmax = значению L в этой точки

2.2 Двойственная задача

Общая схема построения двойственной задачи.

Если задана общая задача ЛП:

где D определяется системой уравнений и неравенств:

… …. …

… … …

,

то двойственной по отношению к ней называется общая задача ЛП:



где D* определяется системой уравнений и неравенств:

… … …

… … …

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

3. Матрица ограничений задачи А транспонируется.

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

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

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



((D*)*, (f*)*)?(D, f),

Основные теоремы:

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

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

Теорема 3 (об оценках). Значение переменных в оптимальном решении двойственной задачи представляет собой оценки влияния свободных членов bi в системе ограничения прямой задачи на величину целевой функции f(x*)

2.3 Транспортная задача

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

Имеется ряд пунктов производства с объемами производства в единицу времени (месяц, квартал), равными соответственно и пункты потребления потребляющие за тот же промежуток времени соответственно продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех пунктах-поставщиках равна сумме объемов потребления на всех пунктах-получателях:

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

Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:



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

и каждый поставщик отгружает весь произведенный им продукт:

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

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы -- пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем -- значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi, j=0), называют свободными, а ненулевые -- занятыми (xi, j>0).

	В1	В2	……	Вn	Всего
	C1, 1	C1, 2	……	C1, n	а1
A1	C2, 1	C2, 2	……	C2, n	а2
A2	….	….	….	….
….	…	…	…	….	….
Am	Cm, 1	Cm, 2	……	Cm, n	аm
	b1	b2		bn

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

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

Производственно-транспортная задача

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

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



II. Практический раздел

Задача №1

Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице 1.1.

Вид сырья	Нормы расхода сырья на одно изделие, кг А В	Общее количество сырья, кг
I	12 4	300
II	4 4	120
III	3 12	252
Прибыль от реализации одного изделия, ден. ед	30 40	?

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

Решение.

Обозначим через х₁ и х₂ количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (12 х₁ +4х₂ ) единиц ресурса I, (4х₁ +4х₂ ) единиц ресурса II, (3х₁ +12х₂ ) единиц ресурса III. Так как, потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

12х₁ +4х₂ ? 300; Размещено на http://www.allbest.ru/

3х₁ + х₂ ? 75; Размещено на http://www.allbest.ru/

4х₁ +4х₂ ? 120; х₁ + х₂ ? 30;

3х₁ +12х₂ ? 252. х₁ +4х₂ ? 84.

По смыслу задачи переменные

х₁ ? 0, х₂ ?0. (1, 1)



Конечную цель решаемой задачи - получение максимальной прибыли при реализации продукции - выразим как функцию двух переменных х₁ и х₂.

Суммарная прибыль А составит 30х₁ от реализации продукции А и 40х ₂ от реализации продукции В, то есть:

F = 30х₁ +40х _2. (1, 2)

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Проведем оси: на горизонтальной будут указываться значения переменной х₁, а на вертикальной -- х₂.Далее рассмотрим условие неотрицательности переменных: x₁ ? 0 и х₂ ? 0. Эти два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте (т.е выше оси x₁ и правее оси х₂ ).

Чтобы учесть оставшиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получится система уравнений прямых:

3х₁ + х₂ = 75;

х₁ + х₂ = 30;

х₁ +4х₂ = 84.

а затем на плоскости провести эти прямые.

Например, неравенство 3х₁ + х₂ ? 75 заменяется уравнением прямой 3х₁ + х₂ = 75. Чтобы провести эту линию, надо найти две различные точки, лежащие на этой прямой Можно положить х₁ = 0, тогда х₂ = 75/1 = 75.. Аналогично для х₂ = 0 находим x₁ = 75/3 = 25. Итак, наша прямая проходит через две точки (0, 75) и (25;0). Аналогично найдём остальные точки и запишем их в таблицу 1.2.

Заштрихованная область, изображённая на рисунке, является областью допустимых значений функции F. Т.к. целевая функция F стремиться к max, то идя по направлению вектора n, получим точку B с оптимальным решением. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:

3х₁ + х₂ ? 75, Размещено на http://www.allbest.ru/

х₁ = 19, 64, Размещено на http://www.allbest.ru/

х₁ + 4х₂ ? 84, х₂ = 16, 09., т. е. B(16, 09; 19, 64)

максимальное значение линейной функции равно:

F_max = 30*16, 09 + 40*19, 64 = 1232, 80.

Итак, F_max = 1232, 80 при оптимальном решении х₁ = 16, 09, х₂ = 19, 64, т. е. максимальная прибыль в 1232, 80 ден. ед. может быть достигнута при производстве 16, 09 единиц продукции А и 19, 64 единиц продукции В.

Ответ: F_max = 1232, 80.

Задача № 2

Для изготовления двух видов продукции Р₁ и Р₂ используют три вида сырья: S₁, S₂, S₃. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.1.

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

Решение.

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

2х₁ + 5х₂ ? 20

8х₁ + 5х₂ ? 40

5х₁ + 6х₂ ? 30



которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превысит имеющихся запасов. Если продукция Р₁ не выпускается, то х₁ =0; в противном случае x₁ = 0. То же самое получаем и для продукции Р₂. Таким образом, на неизвестные х₁ и х₂должно быть наложено ограничение неотрицательности: х₁ ? 0, х₂ ? 0.

Конечную цель решаемой задачи - получение максимальной прибыли при реализации продукции - выразим как функцию двух переменных х₁ и х₂. Реализация х₁ единиц продукции Р₁ и х₂ единиц продукции Р₂ дает соответственно 50х₁ и 40х₂ руб. прибыли, суммарная прибыль Z = 50х₁ + 40х₂ (руб.)

Условиями не оговорена неделимость единица продукции, поэтому х₁ и х₂ (план выпуска продукции) могут быть и дробными числами.

Требуется найти такие х₁ и х₂, при которых функция Z достинает максимум, т.е. найти максимальное значение линейной функции Z = 50х₁ + 40х₂ при ограничениях

2х₁ + 5х₂ ? 20

8х₁ + 5х₂ ? 40

5х₁ + 6х₂ ? 30

х₁ ? 0, х₂ ? 0.

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Построим в программе Excelтаблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).

Заштрихованная область, изображённая на рисунке, является областью допустимых значений функции Z. Т.к. целевая функция Z стремиться к max, то идя по направлению вектора n, получим точку C с оптимальным решением. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:

8х₁ + 5х₂ ? 40 х₁ = 3, 91, Размещено на http://www.allbest.ru/

5х₁ + 6х₂ ? 30, х₂ = 1, 74., т. е. C(3, 91; 1, 74)

максимальное значение линейной функции равно:

Z_max = 50*3, 91 + 40*1, 74 = 265, 10.

Итак, Z_max = 265, 10 при оптимальном решении х₁ = 3, 91, х₂ = 1, 74, т. е. максимальная прибыль в 1232, 80 ден. ед. может быть достигнута при производстве 3, 91единиц продукции P₁ и 1, 74 единиц продукции P₂.

Ответ: Z_max = 265, 10.

Задача № 3

Имеется два вида корма. A и B, содержащие вещества(витамины) S₁, S₂, S₃. Содержание числа единиц питательных веществ в одном кг каждого вида корма и необходимый минимум самих питательных веществ даны в таблице:

Решение:

Пусть х₁ и х₂ - количество кормоввида А и В соответственно. В одном килограмме каждого вида корма содержится (3х₁ + х₂ ) единиц питательного вещества S₁, (x₁ + 2x₂ ) - S₂ и (x₁ + 6x₂ ) - S₃. Так количество питательных веществ не должно быть меньше необходимого минимума, то запишем следующую систему неравенств:

3х₁ + х₂ ? 8,

x₁ + 2x₂ ? 9,

x₁ + 6x₂ ? 12,

x₁, x₂ ? 0.



Минимальную стоимость витаминов за 1 кг корма, выразим следующей функцией:

F = 4x₁ + 6x₂ => min.

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).

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

x₁ + 2x₂ = 9, x₁ = 7, 50,

x₁ + 6x₂ = 12, x₂ = 0, 75.

Минимальное значение линейной функции равно:

F_min = 4*7.5 + 6*0.75 = 34.50.

Итак, F_min = 34.50 при оптимальном решении х₁ = 7.50, х₂ = 0.75.

Ответ: F_min = 34, 50.

Задача № 4

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

Определить план выпуска изделий, максимизирующий прибыль.

Решение.

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

0, 4х₁ + 0, 2х₂ ? 820,

0, 2x₁ + 0, 1x₂ ? 430,

0, 1x₁ + 0, 1x₂ ? 310,

x₁, x₂ ? 0.

Максимальная прибыль от реализации свитеров и кофточек выразим следующей функцией:

F = 7, 8x₁ + 5, 6x₂ => max.

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).

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

0, 4x₁ + 0, 2x₂ = 820, x₁ = 1000,

0, 1x₁ + 0, 1x₂ = 310, x₂ = 2100.



Максимальное значение линейной функции равно:

F_max = 7.8*1000 + 5.6*2100 = 19560.

Итак, F_max = 19560 при оптимальном решении х₁ = 1000, х₂ = 2100.

Ответ: F_max = 19560.

Задача № 5

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

Решение:

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

2х₁ + 3х₂ ? 180,

4x₁ + 1x₂ ? 240,

6x₁ + 7x₂ ? 426,

x₁, x₂ ? 0.

Максимальная прибыль от реализации шкурок выразим следующей функцией:

F = 16x₁ + 12x₂ => max.

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).

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

x₂ = 0, x₁ = 60,

4x₁ + x₂ = 240, x₂ = 0.

Максимальное значение линейной функции равно:

F_max = 16*60 + 12*0 = 960.

Итак, F_max = 960 при оптимальном решении х₁ = 60, х₂ = 0.

Ответ: F_max = 960.



Заключение

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

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

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

3) И также, возможен случай, когда неравенства противоречат друг другу, и допустимая область пуста, то есть данная задача не будет иметь решений.

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

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



Список литературы

1. Коротков М., Гаврилов М. «Основы линейного программирования», 2003 г.

2. Филькин Г.В., «Линейное программирование» (лекции), Шахты, 2007г.

3. Воротницкий Ю.И. «Исследование операций».

4. Теха Х. «Введение в исследование операций», Издательский дом «Вильямс», 2001 г..

5. Давыдов Э.Г. «Исследование операций», 1990 г..

6. Дегтярев Ю.И. «Исследование операций», 1986 г..

7. Алабин Б.К. «Методы исследования операций» (курс лекций).

8. Лищенко «Линейное и нелинейное программирование», М. 2003 г..

9. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М. 2000 г..

10. Мину М. Математическое программирование. Теория и алгоритмы. М. 2004 г.

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