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

Федеральное государственное образовательное

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

«ФИНАНСОВЫЙ УНИВЕРСИТЕТ

ПРИ ПРАВИТЕЛЬСТВЕ  РОССИЙСКОЙ ФЕДЕРАЦИИ»

ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

Финансово-кредитный  факультет

Кафедра «Экономико-математические методы и аналитические информационные системы»

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

Контрольная работа 

Вариант 3

Выполнил студент:

Факультет: Финансово-кредитный

Уфа 2013

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Геометрическое  решение ЗЛП.

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

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

Геометрический (или графический) метод предполагает последовательное выполнение ряда шагов. Ниже представлен порядок решения  задачи линейного программирования на основе ее геометрической интерпретации.

1. Сформулировать ЗЛП.

2. Построить на плоскости {х₁, х₂} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

3. Найти полуплоскости, определяемые  каждым из ограничений задачи.

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

5. Построить прямую c₁x₁ + c₂x₂ = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.

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

7. Определить координаты точки  максимума (минимума) функции и  вычислить значение функции в  этой точке.

3. Основные  теоремы линейного программирования.

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

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

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

Базисным  решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

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

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

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

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

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

Симплекс-метод  был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

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

В основу симплексного метода положена идея последовательного улучшения  получаемого решения.

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

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

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1) способ определения какого-либо  первоначального допустимого базисного  решения задачи;

2) правило перехода к лучшему  (точнее, не худшему) решению;

3) критерий проверки оптимальности  найденного решения.

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

5. Двойственность в линейном программировании.

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

Пусть в качестве исходной дана задача:

Задача  линейного программирования, двойственная задаче (2.4), будет иметь вид:

Можно сформулировать правила получения двойственной задачи из задачи исходной.

1. Если в исходной задаче ищется  максимум целевой функции, то  в двойственной ей - минимум.

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

3. В исходной ЗЛП все функциональные ограничения - неравенства вида “≤”, а в задаче, двойственной ей, - неравенства вида “≥”.

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

5. Число неравенств в системе  ограничений одной задачи совпадает  с числом переменных в другой.

6. Условие неотрицательности переменных сохраняется в обеих задачах.

Связь между оптимальными планами взаимно  двойственных задач устанавливают  теоремы двойственности.

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

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

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

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

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

Компоненты  оптимального решения двойственной задачи   принято называть двойственными оценками. Часто употребляется также термин «объективно обусловленные оценки».

На  свойствах двойственных оценок базируется экономико-математический анализ распределения  ресурсов. В пределах устойчивости двойственных оценок имеют место  свойства, рассмотренные ниже.

Перейдем  к рассмотрению свойств двойственных оценок.

Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки  , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.

В нашем примере нулевую оценку получил третий ресурс (  = 0), поэтому он не является дефицитным, т.е., с точки зрения задачи, фонд рабочего времени на участке С не ограничивает производство. Напротив, первый (участок А) и второй (участок В) ресурсы являются дефицитными, причем ограничивают производство в одинаковой степени (  =   = 1/3).

Последнее утверждение легко подтвердить, подставив   и   в ограничения исходной задачи:

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

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

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

Для нашего примера увеличение (уменьшение) фонда времени на участке А или В должно приводить к увеличению (уменьшению) максимальной прибыли на $1/3. Соответственно, например, при увеличении фонда времени участка А на 12 н-часов общая прибыль должна увеличиться на $4 (1/3ּ12).

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

В том случае, если Δ_j ≤ 0, вариант производства является выгодным, если Δ_j > 0 – вариант невыгоден.

Вернемся  к нашему примеру. Пусть предприятие  планирует к выпуску новый  вид изделий: бейсбольные биты. Для  производства одной биты необходимо затратить 3 часа работы на участке А, 4 часа работы на участке В и 1 час работы на участке С. Прибыль, получаемая от продажи одной биты, составляет $3. Выгодно ли предприятию выпускать новую продукцию?

Для ответа на вопрос рассчитаем Δ_j по формуле (2.9):

Δ_j = 3ּ  + 4ּ  + 1ּ  - 3 = 3ּ1/3 + 4ּ1/3 + 1ּ0 - 3 = -2/3,

Δ_j < 0, значит производить бейсбольные биты выгодно.

Свойство 4. Оценки как мера относительной заменяемости ресурсов с точки зрения конечного эффекта. Например, отношение  / показывает, сколько единиц k-го ресурса может быть высвобождено при увеличении объема i-го ресурса на единицу, для того чтобы максимум целевой функции остался на прежнем уровне; или наоборот, сколько единиц k-го ресурса необходимо дополнительно ввести при уменьшении на единицу объема i-го ресурса, если мы хотим, чтобы значение целевой функции не изменилось.

Задача 2

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

Продукция двух видов (краска для внутренних (I) и наружных (Е) работ) поступает в оптовую продажу. Для производства красок используются два исходных продукта – А и В. Максимально возможные суточные запасы этих двух продуктов составляют 6 и 8 тонн соответственно. Расходы продуктов А и В на 1 тонну соответствующих красок приведены в таблице.

Изучение  рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны 3000 ден. ед. для краски Е и 2000 ден. ед. для краски I. Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Построить экономико-математическую модель задачи, дать необходимые комментарии к  её элементам и получить решение  графическим методом. Что произойдёт, если решать задачу на минимум, и почему?

Решение:

Вводим  переменные

х₁ – количество краски Е (тонн)

х₂ – количество краски I(тонн)

х₁ - ?; х₂ - ?

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

f(x₁, х₂) = 3000x₁ + 2000x₂           max

(3000x₁ + 2000x₂) – общая выручка от реализации всей краски

Составляем  ограничения по ресурсам

1х₁ + 2х₂ ≤ 6 – ограничение по расходу исходного продукта А

2х₁ + 1х₂ ≤ 8 – ограничение по расходу исходного продукта В

х₂ – х₁ ≤ 1 – по условию

х₂ ≤ 2 – по условию

х₁ ≥ 0; х₂ ≥ 0

Строим  область решений системы ограничений

1) 1х₁ + 2х₂ ≤ 6

1х₁ + 2х₂ = 6 – прямая

1х₁ + 2х₂ < 6 – полуплоскость

Берём точку О (0;0) и подставляем её в неравенство

1*0 + 2*0 < 6;    0 < 6 (верно),  решением  является полуплоскость, содержащая  взятую точку О, т.е. полуплоскость под прямой.

2) 2х₁ + 1х₂ ≤ 8

2х₁ + 1х₂ = 8 – прямая

2х₁ + 1х₂ < 8 – полуплоскость

Подставляем точку О (0; 0)        2*0 + 1*0 < 8;     0 < 8 (верно), решение – полуплоскость, содержащая точку О.

3)  х₂ – х₁ ≤ 1

х₂ – х₁ = 1 – прямая

х₂ – х₁ < 1 – полуплоскость

Подставляем точку О (0; 0)     0 – 0 < 1 (верно), решение – полуплоскость, содержащая точку О.

4) х₂ ≤ 2

х₂ = 2 – прямая, параллельная оси Ох₁

х₂ < 2 – полуплоскость под прямой

5)  х₁ ≥ 0; х₁ = 0 – прямая – ось Ох₂; х₁ > 0 – правая полуплоскость

6)  х₂ ≥ 0; х₂ = 0 – прямая – ось Ох₁; х₂ > 0 – верхняя полуплоскость

Находим общую часть всех построенных  полуплоскостей. Это пятиугольник ОАВСД.

Нахождение  оптимального решения. Ищем среди угловых  точек ОАВСД.

f(x₁, х₂) = 3000x₁ + 2000x₂  

f(x₁, х₂) = 0   3000x₁ + 2000x₂ = 0 – прямая; 1/100 = 3x₁ + 2x₂ = 0

С = (С₁; С₂);  О (0;0);  С₁ = 3000 (1/100 = 3); С₂ = 2000 (1/100 = 2);      С = (3; 2)

max f(x₁, х₂)  в точке К. Для нахождения координат этой точки решаем систему из двух уравнений прямых:

1х₁ + 2х₂ = 6           *2

2х₁ + 1х₂ = 8

2х₁ + 4х₂ = 12

2х₁ + 1х₂ = 8

3х₂ = 4;   х₂ = 4/3 ≈ 1,333;   х₁ = 10/3   ≈ 3,333

Точка К (3,333; 1,333)

f(x₁, х₂)  = 3000*3,333 + 2000*1,333 = 12665

Ответ: для получения максимальной прибыли (12665 ден. ед.), фабрика должна производить 3,333 тонны краски Е и 1,333 тонны краски I.

Задача 3.

Предприятие ежегодно закупает 15000 зеркал размером 4мм*1500мм*2000мм  и использует их для сборки мебели. Затраты на хранение одного  зеркала в течение года составляют 25 руб./шт. Затраты на осуществление  заказа - 1800 руб.  Предприятие работает 300 дней в году. Доставка заказа от поставщиков занимает 4 рабочих дня.

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

Решение:

Дано:

Т=300 р./д./год

М=15000 шт./год

h=25 руб./шт./год

К=1800 руб./зак

t=4 дня

Найти:

Q_опт?

Период поставок?

Точку заказа?

Затраты на управление запасами за год?

1)Q_опт=√2*К*М/h=√2*1800*15000/25=1470 заказов

2)Период поставок: Q_опт/М=1470/15000=0,10лет или 0,10*300=30 дней

3)Точка заказа: х=t*М/Т=4*1500/300=200 заказов.

4)Затраты на управление запасами  за год: Z=(К*М/Q_опт)+h*Q_опт/2=(1800*15000/1470)+25*1470/2=18385.38 руб.

Задача 4

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

Оценить основные характеристики работы данной бухгалтерии как СМО  с отказами (указание руководства  не допускать непроизводительных потерь рабочего времени!). Сколько бухгалтеров  должно работать в бухгалтерии в  отведенные дни с сотрудниками, чтобы  вероятность обслуживания сотрудников  была выше 85%?

Решение:

Находим Σ(n) _j=0  a^j / j !  по формуле: B8+a (1,33), далее растягиваем ячейку С8 вниз, для получения результатов во всех ячейках столбца С.