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

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

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

Московский государственный институт путей сообщения

Юридический институт

Кафедра «Информационно-математические технологии и информационное право»

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

по дисциплине «Методы оптимальных решений»

на тему: «Применение линейного программирования для решения оптимизационных задач»

Выполнила: студентка Минаева Екатерина

Руководитель: Моргунов Роман Борисович

Москва 2015



ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКОЕ ОПИСАНИЕ МЕТОДА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

1.1 Общая характеристика линейного программирования

1.2 Методы решения ЗЛП

1.3 Транспортная задача в Excel

ГЛАВА 2. ПРИМЕНЕНИЕ И ИСПОЛЬЗОВАНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

2.1 Решение ЗЛП графическим методом

2.2 Проверка оптимального решения в среде MS Excel с использованием программной надстройки «Поиск решения»

2.3 Решение ТЗЛП в среде MS Excel с использованием программной надстройки «Поиск решения»

ЗАКЛЮЧЕНИЕ

СПИСОК ИСТОЧНИКОВ И ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ



ВВЕДЕНИЕ

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

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

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

· Рассмотреть теоретико-методологическое описание метода ЛП для решения задач оптимизации

· Решить задачи оптимизации графическим методом

· Проверить оптимальное решение в среде MS Excel с использованием программной надстройки «Поиск решения»

· Решить ТЗЛП в среде MS Excel с использованием программной надстройки «Поиск решения»

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

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



ГЛАВА 1. ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКОЕ ОПИСАНИЕ МЕТОДА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

1.1 Общая характеристика линейного программирования

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

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

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

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

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

· рационального использования сырья и материалов;

· задачи оптимального раскроя;

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

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

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

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

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

ЗЛП записывается в общем виде так:

При ограничениях:

Здесь x_j -неизвестные, a_ij -заданные постоянные величины. Ограничения могут быть заданы уравнениями.

Наиболее часто встречаются задачи в виде: имеется n ресурсов при m ограничениях. Нужно определить объемы этих ресурсов, при которых целевая функция будет достигать максимума (минимума), т. е. найти оптимальное распределение ограниченных ресурсов. При этом имеются естественные ограничения x_j > 0.

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



При ограничениях:

Для составления математической модели ЗЛП необходимо:

1)обозначить переменные;

2)составить целевую функцию;

3)записать систему ограничений в соответствии с целью задачи;

4)записать систему ограничений с учетом имеющихся в условии задачи показателей.

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

1.2 Методы решения ЗЛП

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

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

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

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

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

Алгоритм решения ЗЛП графическим методом:

1. Формализация условия в терминах математического программирования

2. Построение ОДР

3. Выбор оптимальной точки на границе

4. Определение координаты этой точки

5. Нахождение значения оптимальной функции

Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n - m = 2.

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

При ограничениях вида:

Допустим, что система (2) при условии (3) совместна. Каждое из неравенств из систем (2) и (3) определяет полуплоскость с граничными прямыми:

Линейная функция (1) при фиксированных значениях Z является уравнением прямой линии:

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

Найти точку многоугольника решений, в которой прямая с₁х₁+с₂х₂=const опорная и функция Z при этом достигает минимума. Значения Z=c₁x₁+c₂x₂ уменьшаются в направлении вектора N=(-c₁,-c₂), поэтому прямую Z=0 передвигаем параллельно самой себе в направлении вектора N.

Если многоугольник решений ограничен (см. риc.1), то прямая дважды становится опорной по отношению к многоугольнику решений (в точках B и E), причём минимальное значение принимает в точке E. Координаты точки E(x₁,x₂) находим, решая систему уравнений прямых DE и EF.

Рис.1. Пример графического решения ЗЛП с 6 условиями

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

Случай 1. Прямая с₁x₁+c₂x₂=const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу.

Случай 2. Прямая, передвигаясь, всё же становится опорной относительно многоугольника решений. Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху. Для решения оптимизационных задач в среде MS Excel используется инструмент «Поиск решения» (пункт меню «Данные Поиск решения»). Для решения задачи необходимо выполнить следующие этапы:

ь Внести исходные данные;

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

ь Внести в определенную ячейку формулу для расчета целевой функции;

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

В результате получается следующее:

ь Вызвать надстройку «Поиск решения» и, определив для нее основные параметры, определить решение:

После того, как будут заполнены все основные формы, нажимаем кнопку «Выполнить», после чего появится диалоговое окно «Результаты поиска решений». Решение задачи выглядит следующим образом:

1.Для повторного решения задачи оптимизации следует удалить содержимое ячеек с элементами решения и сбросить полученные результаты (клавиша «Delete»).

2.Фрагмент рабочего листа MS Excel с результатами решения задачи оптимизации сохраняется и переносится в документ MS Word (например, с помощью команд «Ctrl&PrintScreen» в среде MS Excel и «Вставить» в документе MS Word или с помощью команд «Копировать» и «Вставить», расположенных на панели инструментов во всех приложениях пакета MS Office)

1.3 Транспортная задача в среде Excel

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

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

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

Транспортная задача (классическая) -- задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для решения таких задач Excel имеет специальный инструмент «Поиск решения». Надстройка «Поиск решения» в Microsoft Excel позволяет напрямую находить оптимальное решение транспортной задачи.

Для добавления надстройки «Поиск решения», если на вкладке «Данные» этого пункта нет перейдите: Файл -- Параметры. Слева выберите меню «Надстройки». В основной части выделите «Поиск решения». Затем ниже, нажмите «Перейти». В открывшемся окне отметьте пункт «Поиск решения» и нажмите «Ok». Во вкладке «Данные» появился соответствующий одноименный пункт.

Рассмотрим общее условие транспортной задачи:

Найти m*n неотрицательных чисел X_ij- объем перевозок от i-ого поставщика к j-ому потребителю, минимизирующих транспортные затраты по перевозке однородных грузов поставщиков с мощностями (запасами) А₁,А₂…Ам к потребителям с потребностями В₁,В₂…Вn, если известны матрица издержек С_ij - издержки перевозки единицы груза от i-ого поставщика к j-ому потребителю.

Рассмотрим математическую постановку транспортной задачи:

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



Ограничения

для i=1,2….m

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

для j=1,2….n

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



ГЛАВА 2. ПРИМЕНЕНИЕ И ИСПОЛЬЗОВАНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

2.1 Решение ЗЛП графическим методом

Для сохранения здоровья и работоспособности человек должен в сутки потреблять не менее 63 усл.ед. белков, не менее 147 усл.ед. жиров и не менее 126 усл.ед. углеводов. Для простоты допустим, что имеется всего два вида продуктов П₁ и П₂ ; стоимость единицы каждого из них равна соответственно 12 и 9 ден.ед. Содержание названных питательных веществ в различных продуктах неодинаково. Предположим, что в единице продукта П₁ содержится 9 усл.ед. белков, 7 усл.ед. жиров 9 усл.ед. углеводов; а в единице продукта П₂ содержится соответственно 3, 21, 10 усл.ед. тех же питательных веществ.

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

Приступим к решению данной задачи с помощью графического метода.

1. Пусть х₁ - количество продукта 1-го вида, х₂ -количество продукта 2-го вида, а f -затраты на приобретение продуктов.

Целевая функция, выражающая совокупные затраты на приобретение продуктов, будет иметь следующий вид: f = 12x₁+9x₂ => min

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

9х₁+3х₂ >=63 - для белков

7х₁+21х₂>=147 - для жиров

9х₁+10х₂>=126 - для углеводов

Кроме того, по смыслу задачи х₁ >=0, х₂>=0

2) Для построения области допустимых решений строим в системе координат соответствующие данным ограничениям-неравенствам граничные прямые (см. рис.2).

1) 9х₁+3х₂ =63 2) 7х₁+21х₂=147 3) 9х₁+10х₂=126

х₁=0; х₂=21 х₁=0; х₂=7 х₁=0; х₂=12,6

х₂=0;х₁=7 х₂=0; х₁=21 х₂=0; х₁=14

Рис. 2. Прямые в системе координат, соответствующие данным ограничениям-неравенствам

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

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

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



Рис. 3. Область допустимых значений

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

Для того чтобы найти координаты второй точки, мы возьмем производную от целевой функции и она будет равна: df/dx₁=12; df/dx₂=9

Перпендикулярно к построенному вектору проводим линию уровня f=0 (см. рис.4).



Рис.4. Вектор - градиент

Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. Прямая F(x) = const пересекает область в точке А. Так как точка А получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых.

4) Найдем координаты этой точки и для этого решим систему уравнения.

9x₁+3x₂=63; *(-1) -9х₁-3х₂=-63; 7х₂=63

9х₁+10х₂=126. 9x₁+10x₂=126. х₂=9

Далее мы подставим х₂ в любое из уравнений системы:

9х₁+3*9=63

9х₁=63-27

9х₁=36

х₁=4

Мы нашли координаты точки А и они равны: х₁=4; х₂=9

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

F(x) = 12*4+9*9=129

Таким образом, для того, чтобы затраты на рацион были минимальны необходимо приобретать 4 усл.ед. продукта 1-го вида и 9 усл.ед. 2-го. При этом затраты будут минимальны, и составят 129 условных денежных единиц.

2.2 Проверка оптимального решения в среде MS Excel с использованием программной надстройки «Поиск решения»

В данном пункте мы проверим правильность решения ЗЛП графическим методом. Для этого мы воспользуемся средой MS Excel.

1)Создадим область переменных. Ячейки В2:В3 будут играть роль переменных (пока они пусты)

2)В ячейку А6 введем формулу целевой функции (см. рис.5; приложение Б)

Рис. 5. Формула вычисления значений ЦФ



3)Создадим область ограничений. В ячейках А10:А12 будем вычислять левые части ограничений в системе, а в ячейках В10:В12 введем правые части ограничений системы (см. рис.6)

Рис.6. Левые и правые части ограничения

4)Вызовем окно диалога «Поиск решения». Устанавливаем целевую ячейку А6 (там где вычисляется значение целевой функции). Указываем направление оптимизации - минимизация (по условию)

В поле изменяя ячейки указываем ячейки переменных В2:В3 ( рис.7; приложение А)

5) Далее мы добавим ограничения. Для начала мы укажем неотрицательность переменных (см. рис.8)



Рис.8. Неотрицательность переменных

6) Далее мы добавляем остальные ограничения.

Рис. 9.Остальные ограничения

Так же выбираем метод решения: Поиск решения линейных задач симплекс-методом.

После добавления всех параметров мы нажимаем на «Найти решение». Оформим полученный результат и получим следующее (рис.10; приложение Б)

Таким образом, оптимальное решение, полученное с помощью графического метода, совпадает с решением, полученным в среде MS Excel с помощью программной надстройки «Поиск решения».



2.3 Решение ТЗЛП в среде MS Excel с использованием программной надстройки «Поиск решения»

Нам дана следующая транспортная задача:

Дано 5 производителей А1, А2, А3, А4, А5, мощность (запасы) которых соответственно равны: 20, 45, 25, 30,20.

И четыре потребителя В1, В2, В3, В4, потребность которых в продукте составляет соответственно: 45, 50, 20, 25.

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

Таблица 1 Матрица издержек Сij - издержки перевозки единицы груза от i-ого поставщика к j-ому потребителю

12	9	10	4
4	7	7	6
7	11	5	8
9	6	9	9
10	11	6	5

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

Таблица 2 Полное условие транспортной задачи

Поставщик	Потребитель	Запас
	В1	В2	В3	В4
А1	12	9	10	4	20
А2	4	7	7	6	45
А3	7	11	5	8	25
А4	9	6	9	9	30
А5	10	11	6	5	20
Потребность	45	50	20	25



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

Перейдем к решению транспортной задачи в среде Excel.

1) Перенесем полное условие транспортной задачи в Excel (см. рис.11).

Рис. 11. Полное условие ТЗ в Excel

2) Далее мы составляем вторую такую же таблицу, но данными заполнять ее не будем (см. рис.12).

Рис. 12 Оформление ТЗЛП



3) В ячейке Н1 введем формулу: СУММAПРОИЗВ(В3:E7;B12:E16) (рис.13)

Рис. 13 Целевая функция

4) В ячейку F12 введите формулу СУММ(B12:E12) и растяните её до F16(рис.14)

Рис. 14 Применение формулы для запасов



5) В ячейку B17 введите формулу СУММ(B12:B16) и скопируйте ее в диапазон от B17 до E17(рис.15)

Рис.15 Применение формулы для потребности

6) Для решения задачи на панели вкладок выберите вкладку «Данные», а затем «Поиск решения». Оптимизируем целевую функцию, по условию задачи ЦФ минимизируем. Также обозначим ограничения для нашей задачи, ограничения будут следующие:

1) $B$12:$E$16 = целое

2) $B$12:$E$16 >=0

3) $B$17:$E$17= $B$8:$E$8

4) $B$12:$F$16 = $F$3:$F$7 (см. рис.16)



Рис.16 «Поиск решения»

Таким образом, в диапазоне B12:E16 Мы получим результат решения транспортной задачи (т.е. значение в ячейке соответствует количеству груза перевезенного от i-ого поставщика к j-ому потребителю).

В диапазоне F12:F16 количество груза, которое необходимо вывезти от поставщиков.

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

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

Оформим полученный результат и получим следующее (см. рис 17)



Рис.17 Ответ

Таким образом, Из 1-го склада необходимо груз направить в 2-й магазин (15), в 4-й магазин (5)

Из 2-го склада необходимо груз направить в 1-й магазин (40), в 2-й магазин (5)

Из 3-го склада необходимо груз направить в 1-й магазин (5), в 3-й магазин (20)

Из 4-го склада необходимо весь груз направить в 2-й магазин

Из 5-го склада необходимо весь груз направить в 4-й магазин

На 5-ом складе остался невостребованным груз в количестве 5 ед.

При этом затраты равны 765 ед.



ЗАКЛЮЧЕНИЕ

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

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

В рамках данной работы была решена одна из задач линейного программирования. В результате применения процедуры графического метода было получено оптимальное решение поставленной задачи, в соответствии с которым, чтобы затраты на рацион были минимальны необходимо приобретать 4 усл.ед. продукта 1-го вида и 9 усл.ед. 2-го. При этом затраты будут минимальны, и составят 129 условных денежных единиц Проверка результатов решения задачи в среде MS Excel показала аналогичное решение данной задачи оптимизации.

Также при выполнении данной работы на примере была рассмотрена транспортная задача линейного программирования. В результате решения было получено оптимальное решение поставленной задачи, в соответствии с которым, из 1-го склада необходимо груз направить в 2-й магазин (15), в 4-й магазин (5)

Из 2-го склада необходимо груз направить в 1-й магазин (40), в 2-й магазин (5)

Из 3-го склада необходимо груз направить в 1-й магазин (5), в 3-й магазин (20)

Из 4-го склада необходимо весь груз направить в 2-й магазин

Из 5-го склада необходимо весь груз направить в 4-й магазин

На 5-ом складе остался невостребованным груз в количестве 5 ед.

При этом затраты равны 765 ед.

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



СПИСОК ИСТОЧНИКОВ И ЛИТЕРАТУРЫ

1. Акулич И.Л. Математические методы и компьютерные технологии решения оптимизационных задач / И.Л. Акулич, В.Ф. Стрельчонок.- Рига: МИСис, 2000.- 100с.

2. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. Вузов / И.Л. Акулич. - М.: Высшая школа, 1986. -С.150

3. Ашманов С.А. Линейное программирование / С.А. Ашманов. - М.: Наука, 1981. - 356с.

4. Барсов А.С. Что такое линейное программирование / А.С. Барсов. - М.: Государственное издательство физико-математической литературы, 1959. - 105с.

5. Боборыкин В.А. Математические методы решения транспортных задач / В.А. Бобрыкин.- Л.: СЗПИ, 1986.-С.146

6. Бородакий Ю.В. Линейное программирование в современных задачах оптимизации / Ю.В. Бородакий. - М.: МИФИ, 2008. - 564с.

7. Данциг Д. Линейное программирование, его обобщение и применение / Д. Данциг. - М.: Прогресс, 1966. - 450с.

8. Еремин И.И. Введение в теорию линейного и выпуклого программирования / И.И. Еремин, Н.Н. Астафьев. - М.; Наука, 1976. - 150с.

9. Карманов В.Г. Математическое программирование / В.Г. Карманов. - М.; Наука, 1986г.-98с.

10. Киселева Э.В. Математическое программирование (линейное программирование) / Э.В. Киселева, С.И. Соловьева. - Новосибирск: НГАСУ, 2002. - 256с.

11. Кремер Н.Ш. Исследование операций в экономике/ Н.Ш. Кремер. -- М.: Юнити,2000. -- 400 с.

12. Кузнецов Ю.Н. Математическое программирование / Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко.- М.: Высшая школа, 1980. - 450с.

13. Моисеев Н.Н. Методы оптимизации / Н.Н. Моисеев, Ю.П. Иванов, Е.М. Столярова. - М.; Наука, 1978г. 187с.

14. Палий И.А. Линейное программирование. Учебное пособие / И.А. Палий. - М.: Наука, 2008.- 350с.

15. Руденко А.И. Экономика предприятия/А.И. Руденко, Учебник для экономических вузов.- Минск, 2005. -248с.

16. Смирнов В.А. Лекции - Линейное программирование с примерами решения задач / В.А. Смирнов. - М.: Наука, 2002. - 500с.

17. Тарасова Н.В., Организации и планирование производства/ Н.В. Тарасова, Ларионова И.А., Алексахин А.В. Методические указания. М.:МИСиС -2001г. 300с.

18. Юдин Д.Б. Линейное программирование (теория, методы, приложения) / Д.Б. Юдин, Н.Г. Гольштейн. - М.: Наука, 1969. - 300с.



ПРИЛОЖЕНИЯ

Приложение А

Рис. 7. Параметры поиска решения



Приложение Б

Рис.10. Полученные ответы

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