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

Смоленский  гуманитарный университет

Факультет компьютерных технологий, экономики и дизайна

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

 

 

 

 

 

 

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

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

ВАРИАНТ №_32__

 

 

 

 

 

 

Исполнитель:               

^{(Ф.И.О.студента)}   

Студент группы                 

^{(группа, подпись студента)}  

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

^{(Ф.И.О.руководителя, подпись)}  

Зав.кафедрой:  

^{(Ф.И.О.зав.кафедрой, подпись)}  

Дата допуска:       

 

 

 

 

 

 

Смоленск

2013

 

 

Содержание

 

Введение	3
1 Общая постановка  задачи линейного программирования	5
2 Примеры экономических задач, приводящихся к задачам ЛП	9
3 Геометрический метод решение задач ЛП	16
4 Симплексный метод решения задач ЛП	21
5 Теоремы двойственности и их использование в задачах ЛП	26
6 Транспортная задача и её решение методом потенциалов	35
7 Решение задач ЛП  с использованием программ «Excel»	41
Заключение	45
Список используемой литературы	46

 

Введение

 

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

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

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

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

 

1 Общая постановка задачи  линейного программирования

 

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

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

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

С каждым технологическим  способом связан интерес человека, занятого планированием. Две противоположные  постановки проблемы планирования:

а) при заданном наличии  ресурсов произвести как можно больше продукции;

б) произвести заданное количество продуктов при наименьшем расходе ресурсов.

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

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

Сформулируем общую задачу линейного программирования (ЗЛП). Дана система m линейных уравнений и неравенств с n переменными:

                                 a₁₁x₁ + a₁₂x₂ + . . . + a_1nx_n ≤ b₁,

                                 a₂₁x₁ + a₂₂x₂ + . . . + a_2nx_n ≤ b₂,

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

                                 a_k1x₁ + a_k2x₂ + . . . + a_knx_n ≤ b_k,                                    (1)

                                 a_k+1,₁x₁ + a_k+1,₂x₂ + . . . + a_k+1,_nx_n = b_k+1,

                                 a_k+2,₁x₁ + a_k+2,2x₂ + . . . + a_k+2,nx_n = b_k+2,

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

                                 a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤ b_m

 

и линейная функция:

                                   F = c₁x₁ + c₂x₂ + . . . + c_nx_n                                       (2)

 

Необходимо найти такое решение  системы X = (x₁, x₂, . . . , x_j, . . . , x_n), где  

                                         x_j ≥ 0 (j = 1, 2, . . . , n),                                       (3)

 

при котором линейная функция F (2) принимает оптимальное (т.е. максимальное или минимальное) значение.

Система (1) называется системой ограничений, а функция F — линейной функцией, линейной формой, целевой функцией или функцией цели.

Оптимальным решением (или  оптимальным планом) задачи линейного программирования называется решение X = (x₁, x₂, . . . , x_j, . . . , x_n) системы ограничений (1), удовлетворяющее условию неотрицательности (3), при котором линейная функция (2) принимает оптимальное (максимальное или минимальное) значение.

Термины «решение» и  «план» — синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй — о содержательной стороне (экономической интерпретации).

Основные формы ЗЛП:

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

2. Каноническая — система  ограничений состоит только из уравнений, условие неотрицательности наложено на все переменные.

3. Общая — наличие  различных типов ограничений,  условие неотрицательности может быть наложено не на все переменные.

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

а) менять знак неравенства. Для этого достаточно умножить обе  части неравенства на −1. Например, неравенство x1 − 2x2 ≥ 3 эквивалентно неравенству −x1 + 2x2 ≤ −3.

б) перевести неравество в уравнение. Это достигается путем введения дополнительной неотрицательной переменной. Например, неравенству x1 + 3x2 ≤ 4 соответствует уравнение x1 + 3x2 + x3 = 4, а неравенству 2x1 + x2 ≥ 3 соответствует уравнение 2x1 + x2 − x3 = 3.

в) наложить условие неотрицательности на переменную, которая его не имеет. Так, любое число x может быть представлено в виде разности двух неотрицательных чисел u и v: x = u − v, где x € R, u ≥ 0, v ≥ 0.

 

 

2 Примеры экономических задач, приводящихся к задачам ЛП

 

Рассмотрим некоторые классические задачи, традиционно относящиеся к задачам линейного программирования.

Задача  составления рациона (задача о диете, задача о смесях).

На птицеферме употребляются  два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II - 2 рубля.

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

Представим условие  задачи в таблице 1.

 

Таблица 1 - Исходные данные задачи о смесях

Питательные вещества	Содержание веществ в единице  массы корма, ед.		Требуемое количество в смеси, ед.
	корм I	корм II
А	1	4	1
В	1	2	4
С	1	-	1
Цена единицы массы корма, р.	2	4

 

Cформулируем задачу линейного программирования.

Обозначим: x₁ - количество корма I в дневном рационе птицы, x₂ - количество корма II в дневном рационе птицы.

Формулировка ЗЛП: 

Целевая функция: F(x) = 3x₁ + 2x₂ → min;                                     (4) 

Ограничения:                    x₁ + 4x₂ ≥ 1,