Математический метод решения задач с экономическим содержанием

Муниципальное бюджетное образовательное учреждение  «Школа №45»

с углубленным изучением отдельных предметов

Приокского района г. Н. Новгорода

Научное общество учащихся

Математический метод решения задач с экономическим содержанием

Выполнил: Труфанов Сергей,

ученик 10 а класса

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

Демидовская А.М.

Содержание

1. Введение……………………………………………………………………2
2. Глава1.
3. Способы решения задач методом линейного программирования……..3

1. Линейное программирование………………………………………....3
2. Три способа решения задач методом линейного программирования……………………………………….....................4
3. Симплексный метод решения задач линейного программирования.5

4. Глава 2.Решение задач.…………….........................................................6

3.1 Пример решения задачи симплекс методом …...………………......6

3.2 Методы решения транспортных задач ……..…………………........9

3.4 Полное решение транспортной         задачи .........................…………..14

5. Заключение………………………………………………………………..17
6. Список использованной литературы…………………………………….18

1. Введение

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

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

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

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

Целью работы является: познакомиться с МЛП и его практическим использованием. Для этого были поставлены следующие задачи:

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

2. Глава 1.Способы решения задач методом линейного программирования

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

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

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

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

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

Первый способ - простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа  2Х1  + 5Х2   ≤ 10, то, очевидно,  0 ≤ Х1  ≤ 10/2 = 5 и 0 ≤ Х2  ≤ 10/5 = 2. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной.

Второй способ - направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)

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

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

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

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

3. Глава 2.Решение задач

3.1 Пример решения задачи симплекс методом

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

Дано:

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

F = 6x1+5x2+9x3

при следующих ограничениях:

x1 ≥ 0    x2 ≥ 0    x3 ≥ 0    

Решение:

S1 ≥ 0, S2 ≥ 0, S3 ≥ 0. Введенные переменные S1, S2, S3, называются балансовыми переменными.

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

Следовательно, рано или поздно, ответ будет получен.

Как осуществляется переход от одного базиса к другому?

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

Выбран столбец.

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

Выбрана строка.

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

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

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

x1 = 0   x2 = 0   x3 = 0  

S1 = 25   S2 = 20   S3 = 18          => F = 0

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

Нахождение наибольшего значения функции F

Шаг 1)

Приравниваем свободные переменные нулю, устно находим значения базисных переменных. (см. таблицу)

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

x1 = 0   x2 = 0   S3 = 0  

x3 = 6   S1 = 7   S2 = 8          => F - 54 = 0   => F = 54

Шаг 2)

Приравниваем свободные переменные нулю, устно находим значения базисных переменных. (см. таблицу)

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

x1 = 0   S2 = 0   S3 = 0  

x2 = 4/3   x3 = 6   S1 = 13/3          => F - 182/3 = 0   => F = 182/3

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

Ответ: x1 = 0   x2 = 4/3   x3 = 6  Fmax = 182/3

3.2 Методы решения транспортных задач

Метод минимальной стоимости

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел Ai или Bi. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Составим с помощью этого метода опорный план уже рассмотренной задачи. Запишем ее условие в таблицу (таблица 2). Выбираем в таблице наименьшую стоимость (это стоимость, помещенная в клетке A1 B4), так как A1 = B4 , 50 единиц груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец.

В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клетке A2 B1 и в клетке A3 B5. Заполняем любую из них, например A2 B1 . Имеем 100 < 125, следовательно, записываем в нее 100 и исключаем из рассмотрения столбец B1. В клетку A3 B5 записываем 100 ед. и исключаем из рассмотрения строку A3. В оставшейся таблице стоимостей снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены.

Таблица 2

План не содержит циклов и состоит из семи положительных перевозок, следовательно, является вырожденным опорным планом. Определим его стоимость: Z = 50*1 + 100*2 + 25*7 + 100*2 + 75*8 + 50*12 + 25*13 = 2150 (единиц). Стоимость плана перевозок значительно меньше, следовательно, он ближе к оптимальному.

Метод двойного предпочтения

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

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

Пример:

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

3.3  Полное решение транспортной задачи

Колхоз имеет возможность приобрести не более 19 трехтонных автомашин и не более 17 пятитонных. Отпускная цена трехтонного грузовика - 4000 руб., пятитонного - 5000 руб. Колхоз может выделить для приобретения автомашин 141 тысяч рублей. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной? Задачу решить графическими и аналитическими методами.

Решение:

Составим математическую модель задачи. Пусть x1 – количество трехтонных автомашин, x2 – количество пятитонных автомашин. По условию 0 ≤ x1≤ 19, 0 ≤ x2 ≤ 17. На приобретение грузовиков необходима сумма 4000 x1  + 5000 x2, при этом по условию она не должна превосходить 141 000, т.е. 4000x1 + 5000x2 ≤ 141000. Теперь введем целевую функцию – грузоподъемность автомашин, которая составляет 3x1+ 5x2.

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

f = 3x1 + 5x2 → max

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

4000x1+ 5000x2 ≤ 141000 (*),

0 ≤ x1 ≤ 19, 0 ≤ x2 ≤ 17 (**).

Решим эту задачу симплекс-методом. Приведем задачу к каноническому виду, введя 3 дополнительные переменные x3, x4, x5:

f = 3x1+ 5x2 +0x3 + 0x4+0x5→ max

4000x1+ 5000x2 + x3 = 141000,

x1 +x4 = 19, x2 + x5 = 17, x1≥ 0, x2≥0.

В качестве опорного плана выберем x0=(0, 0, 141000, 19, 17). Составим симплекс-таблицу.

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

В последнем плане строка f не содержит отрицательных значений, план x1 = 14, x2 = 17 оптимален, целевая функция принимает значение 127 (тонн). Теперь решим эту же задачу графическим методом. Построим область допустимых решений задачи, ограниченную прям Множество точек, определяемых неравенствами (*), (**) – многоугольник АВСДО, в одной из вершин которого достигается максимум функции. Построим линию уровня 3x1 + 5x2 = 0 и вектор градиента (3, 5). Будем передвигать линию уровня, пока не выйдем из многоугольника, что произойдет в точке В с координатами (14, 17).

В этой точке функция принимает максимальное значение 127. Чтобы достичь этого значения грузоподъемности, нужно приобрести 14 трехтонных грузовиков и 17 пятитонных: 4000 x1+ 5000 x2 = 141000, (I) x1 = 19, (II) x2 = 17. (III)

4. Заключение

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

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

Вывод

В данной работе я разобрал:

1. Что такое линейное программирование;
2. Какие существуют методы линейного программирования
3. Как методы линейного программирования применяются при решении задач

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

1. http://math.immf.ru/lections/302.html
2. http://www.grandars.ru/student/vysshaya-matematika/simpleksnyy-metod.html
3. http://www.aup.ru/books/m156/5.htm
4. http://www.grandars.ru/student/vysshaya-matematika/opornoe-reshenie-transportnoy-zadachi.html
5. Учебник вшэ методы оптимальных решений
6. Козлов В.Н. Колесников Д.Н. Сиднев А.Г. Решение задач математического программирования. СПб.: СПбГТУ, 1992
7. Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. – М.: Советское радио, 1969.