Математическое программирование

Содержание:

 

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

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Общая постановка  задачи линейного программирования (ЗЛП).

 

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

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

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

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

·  задача об оптимальном использовании ресурсов при производственном планировании;

·  задача о смесях (планирование состава продукции);

·  задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

·  транспортные задачи (анализ размещения предприятия, перемещение грузов).

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

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

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

·  многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

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

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

·  целевая функция:

= c1x1 + c2x2 + ... + cnxn → max(min);

(2.1)

·  ограничения:

a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1,  a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2, ...             am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm;

(2.2)

·  требование неотрицательности:

xj ≥ 0,

(2.3)

При этом a_ij, b_i, c_j (     ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (2.1) при  соблюдении ограничений (2.2) и (2.3).

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

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

ТРАНСПОРТНАЯ ЗАДАЧА [transportation problem] — одна из наиболее распространенных задач математического программирования (обычно — линейного). В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот). В простейшем виде, когда распределяется один вид продукта и потребителям безразлично, от кого из поставщиков его получать, задача формулируется следующим образом.

Имеется ряд пунктов производства A₁, A₂, ..., A_m с объемами производства в единицу времени (месяц, квартал), равными соответственно a₁, a₂, ..., a_m,, и пункты потребления B₁, B₂, ..., B_n, потребляющие за тот же промежуток времени, соответственно b₁, b₂, ..., b_n продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех m пунктах-поставщиках равна сумме объемов потребления на всех n пунктах-получателях:

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

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

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

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

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

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

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

 

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

 

 

 

 

 

 

 

 

Список используемой литературы:

1)К.Л . Самаров Учебно -методическое пособие для студентов: учебный центр "Резольвента", 2010г.