Математическое программирование: Линейное программирование. Постановка задач, методы решения



 

 

 

Кафедра управления качеством, техники и технологий


 

 

КУРСОВАЯ РАБОТА

по дисциплине «Системный анализ»

на тему:

«Математическое программирование: Линейное программирование. Постановка задач, методы решения»

 

Работу выполнил:

студент группы УЗ-03

 

Работу проверил:

                                                                                                                                                   

 

Дата сдачи

 

 

Дата защиты

 

 

Оценка

 

 

 

2010


СОДЕРЖАНИЕ

 

Введение

4

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

7

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

11

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

14

3.1. Графический метод решения ЗЛП

14

3.1.1. Методика решения ЗЛП графическим методом

17

3.1.2. Применение графического метода решения ЗЛП на практике

18

3.2. Симплексный метод решения ЗЛП

22

Заключение

29

Список использованных источников

31


Обозначения и сокращения

 

 

ЛП

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

ЗЛП

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

ЦФ

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

ОДР

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

 


Введение

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

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

• при наличии математической определенности и количественной ограниченности между изучаемыми переменными величинами и факторами;

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

• в случае совмещения математической логики с пониманием сущности изучаемых явлений.

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

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

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

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

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

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

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

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

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

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

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


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

 

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

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

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

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

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

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

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

* математические модели очень большого числа экономических задач линейны относительно искомых переменных;

* эти типы задач в настоящее время наиболее изучены;

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

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

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

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

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


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

 

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

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

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

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

Имеются какие-то переменные х = (х1 , х2 , … хn ) и функция этих переменных f(x) = f (х1 , х2 , … хn ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что
а) функция f(x) является линейной функцией переменных х1, х2, … хn
б) область G определяется системой линейных равенств или неравенств.

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

        максимум или минимум целевой функции (критерий оптимальности);

        систему ограничений в форме линейных уравнений и неравенств;

        требование неотрицательности переменных.

Рассмотрим пример постановки ЗЛП.

Пусть имеется два станка (S1 , S2), на каждом из которых можно производить два вида продукции (P1, P2). Станок S1 производит единицу продукции P1 за 1 час, а единицу продукции P2 - за 2 часа. Станок S2 затрачивает на единицу продукции P1 - 2 часа, а на единицу продукции P2 - 1 час. Станок S1 может работать в сутки не более 10 ч., а станок S2 - не более 8 ч. Стоимость единицы продукции P1 составляет C1 руб., а стоимость единицы продукции P2 - C2 руб.

Требуется определить такие объемы выпуска продукции P1 и P2 на станок, чтобы выручка от реализации производственной продукции была максимальной.

Вид ресурса

Число единиц ресурса, затрачиваемое на изготовление единицы продукции

Запас ресурса

P1

P2

S1

1

2

10

S2

2

1

8

Прибыль за единицу продукции

C1

C2

...


 

Составим математическую модель задачи:

Обозначим через х1 и х2 количества продукции P1 и P2, которое планируется произвести на каждом отдельном станке. Стоимость произведенной продукции

F = c1х1 + c2 х2. Мы должны назначить х1 и х2 так, чтобы величина F была максимальной. Переменные х1, х2 не могут принимать произвольных значений. Их значения ограничены условиями производства, а именно тем, что станки могут работать ограниченное время. На изготовление продукции P1 станок S1 тратит 1x1 часов, а на изготовление продукции P2 – 2x2 часов. Поскольку время работы станка S1 не превосходит 10 ч, то величины х1 и х2 должны удовлетворять неравенству

x1 + 2x2≤ 10.

Аналогично можно получить неравенство для станка S2: 2x1 + x2 ≤ 8.

Кроме того, величины х1 , х2 не могут быть отрицательными: x1 ≥ 0, x2 ≥ 0, по смыслу задачи.

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

                (2.1)

x1≥0, x2≥0                    (2.2)

F=c1x1+c2x2→max      (2.3)

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

Х = (х1, х2), удовлетворяющий системе (2.1) и условию (2.2), при котором функция (2.3) принимает максимальное значение.

Решения, удовлетворяющие системе ограничений (2.1) и требованиям неотрицательности (2.2), являются допустимыми, а решения, удовлетворяющие одновременно и требованию (2.3) оптимальными.


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

 

3.1. Графический метод решения ЗЛП

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

Графическое решение ЗЛП с двумя переменными и системой ограничений в виде линейных неравенств состоит из 2-х этапов:

1. Построение на плоскости множества решений системы линейных неравенств, являющегося выпуклым многогранным множеством.

2. Выбор в построенном множестве точки х*=(х1*, х2*), доставляющей целевой функции требуемое экстремальное (max или min) значение.

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

Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид

                                        (3.1)

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

 

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

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

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

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

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

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

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

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

Рисунок 3.1. Геометрическая интерпретация ограничений и ЦФ задачи.


3.1.1. Методика решения ЗЛП графическим методом

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

II.     Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (3.1). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства. Если  неравенство истинное, то    надо заштриховать полуплоскость, содержащую данную точку;               иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку. Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте. Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.

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

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

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

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

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

 

3.1.2. Применение графического метода решения ЗЛП на практике

Рассмотрим задачу: Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии  60 изделий, второй линии  80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели  10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определить оптимальные суточные объемы производства первой и второй моделей на основе графического метода решения задачи.

Математическое программирование: Линейное программирование. Постановка задач, методы решения