Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Три задачи распределительного типа, Формы записи задач линейного программирования кратко

Лекция



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

Задачи линейного программирования во многих случаях называются задачами распределительного типа, суть которых заключается в следующем. Пусть рассматриваемая система характеризуется наличием n видов деятельности, для осуществления которых имеются различные ресурсы с номерамиТри задачи распределительного типа, Формы записи задач линейного программирования . Возможный объем потребления i-го ресурса ограничен неотрицательной величиной bi, а его расход для реализации единицы продукта k-го вида деятельности равен aik, гдеТри задачи распределительного типа, Формы записи задач линейного программирования . В свою очередь единица продукта k-го вида деятельности характеризуется величиной ck, называемой удельной прибылью (удельной эффективностью).

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

Три задачи распределительного типа, Формы записи задач линейного программирования

Три задачи распределительного типа, Формы записи задач линейного программирования Три задачи распределительного типа, Формы записи задач линейного программирования (2.3)

Три задачи распределительного типа, Формы записи задач линейного программирования

Чтобы задача ИО была представлена как задача ЛП необходимо выполнение условий:

- пропорциональности;

- аддитивности;

- неотрицательности.

Все они имели место при записи задач (2.1 , 2.2 , 2.3).

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

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

Рассмотрим геометрический метод решения задачи (2.1). Основой метода является геометрическое (графическое) представление множества допустимых решений и целевой функции.

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

Три задачи распределительного типа, Формы записи задач линейного программирования

Второй этап графического решения состоит в определении направления возрастания целевой функцииf(x1,x2)=3x1+2x2.

При произвольном фиксированном значенииТри задачи распределительного типа, Формы записи задач линейного программирования уравнение f(x1,x2)=f0 может быть представлено в виде x2=-1,5x1+0,5f0, эта прямая является линией уровня целевой функции. Для определения направления возрастания целевой функции (обозначено знаком ) достаточно изобразить линии уровня f(x1,x2)=f01 иf(x1,x2)=f02 при f0102. Чтобы найти оптимальное решение следует перемещать линию уровня в направлении возрастания целевой функции до тех пор, пока она не переместится в область недопустимых решений R2\G.

На рисунке видно, что максимальное значение целевой функции достигается в вершине С многоугольника, являющегося границей ГG множества G допустимых значений. Так как точка С - точка пересечения прямых x1+2x2=6 и 2x1+x2=8, то ее координаты х1* и х2* удовлетворяют системе их этих двух уравнений. Следовательно х1*=10/3 и х2*=4/3. В этом случае доход будет максимальным и равным Три задачи распределительного типа, Формы записи задач линейного программирования.

В данном случае удельная прибыль от продукции каждого вида с1=3 и с2=2 определяется ситуацией задачи (спросом) и по неконтролируемым причинам может колебаться в некоторых пределах. Об этом говорит сайт https://intellect.icu . Так как суточный доход

f(x1,x2)=c1x1+c2x2,

то необходимо знать диапазоны допустимых значений удельных прибылей, не приводящих к новым оптимальным решениям. Из рисунка следует, что для любых положительных значений с1 и с2, удовлетворяющих условию Три задачи распределительного типа, Формы записи задач линейного программированияоптимальным является решение Х*=(10/3;4/3)Т. В остальных случаях решения будут отличаться от найденного. Если, к примеру, f(x1,x2)=3x1+x2, то оптимальным является решение (4;0)Т. При Три задачи распределительного типа, Формы записи задач линейного программирования и Три задачи распределительного типа, Формы записи задач линейного программирования любая точка соответствующей стороны многоугольника ГG1, кроме точки G1, определяет оптимальное решение.

ЛПР полезно знать и о том, как повлияют на оптимальное решение изменение спроса и изменение ресурсов исходных продуктов. Такие исследования называются анализом математической модели (2.2) на чувствительность.

Обратимся к задаче ЛП (2.3) распределительного типа, предположив, что непустое множество Gограничено.

Пусть Х*=(х1*,…,хn*)Т – оптимальное решение задачи ЛП распределительного типа.

Ограничение

Три задачи распределительного типа, Формы записи задач линейного программирования (2.4)

в задаче (2.3) называют активным, если

Три задачи распределительного типа, Формы записи задач линейного программирования

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

Графическое решение задачи ЛП показывает, что оптимальному решению всегда можно поставить в соответствие хотя бы одну вершину многоугольника, изображающего множество G допустимых решений. Такая вершина называется оптимальной вершиной. Через оптимальную вершину G проходят две прямыеx1+2x2=6 и 2x1+x2=8. Поэтому активными являются ограничения на суточные запасы А и В.

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

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

б) предельно допустимое снижение запаса недефицитного ресурса, не изменяющее найденного ранее оптимального решения.

Понятно, что анализ влияния на решение увеличения запаса недефицитного ресурса (А) ограничен величиной b1=6. На рисунке видно, что при увеличении запаса b1 этого ресурса прямая, определяемая уравнением x1+2x2= b1 , начинает перемещаться параллельно самой себе.

Три задачи распределительного типа, Формы записи задач линейного программирования

До момента ее прохождения через точку F при b1 = 7 этому процессу соответствуют перемещение оптимальной вершины С вдоль прямой, заданной уравнением 2x1 + x2 = 8, в направлении точки F и увеличение прибыли (значения целевой функции) при оптимальном решении. При b1 > 7 анализируемый ресурс уже не является дефицитным и дальнейшее увеличение его запаса теряет смысл. Заметим, что при b1 = 7 оптимальное решение X* = (3 2)T соответствует значению целевой функции f* = 13 и наряду с уже имеющимся активным ограничением Три задачи распределительного типа, Формы записи задач линейного программирования появляется еще одно активное ограничение:Три задачи распределительного типа, Формы записи задач линейного программирования .

Аналогичный анализ может быть проведен и по отношению ко второму дефицитному ресурсу (исходный продукт В), объем потребления которого ограничен величиной b2 = 8. На рис. 2.3 видно, что увеличение запасаb2 исходного продукта В имеет смысл до величины b2 = 12, при котором оптимальное решение X* = (6 0) соответствует значению целевой функции f* = 18.

Три задачи распределительного типа, Формы записи задач линейного программирования

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

В рассматриваемом случае ценность дополнительной единицы первого ресурса (продукта А)

Три задачи распределительного типа, Формы записи задач линейного программирования

а второго ресурса (продукта В)

Три задачи распределительного типа, Формы записи задач линейного программирования

Полученные результаты свидетельствуют о том, что при наличии средств дополнительные вложения в первую очередь следует направить на увеличение объема продукта В, а лишь затем на увеличение объема продукта А.

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

Стандартная форма записи задач ЛП предполагает выполнение двух требований:

1.Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.

2.Все переменные неотрицательны.

Преобразование неравенств в равенства.

Неравенства любого типа ( Три задачи распределительного типа, Формы записи задач линейного программированияилиТри задачи распределительного типа, Формы записи задач линейного программирования ) можно преобразовать в равенство путем добавления в левую часть неравенств дополнительных переменных – остаточных или избыточных (балансных), которые связаны с неравенствами типа «Три задачи распределительного типа, Формы записи задач линейного программирования» и «Три задачи распределительного типа, Формы записи задач линейного программирования» соответственно.

Для неравенств «» в левую часть неравенства вводится неотрицательная остаточная переменная. Например, в задаче Reddy Mikks ограничения на количество сырья M1 задается в виде неравенства:

6x1 + 4x2 Три задачи распределительного типа, Формы записи задач линейного программирования24

Введем новую неотрицательную переменную S1, которая показывает остаток (неиспользованное количество) сырья M1. Это приведет к равенству:

6x1+4x2+S1=24, S1Три задачи распределительного типа, Формы записи задач линейного программирования0.

Неравенства типа «Три задачи распределительного типа, Формы записи задач линейного программирования» в задачах ЛП обычно устанавливают нижнюю границу чего-либо. Избыточная переменная определяет превышение левой части над этой границей. Так в модели «диеты» неравенство x1+x2 Три задачи распределительного типа, Формы записи задач линейного программирования0 показывает, что суточное производство пищевой добавки должно быть не меньше 800 фунтов. Математически это эквивалентно равенству:

x1+x2 – S1=800, S1Три задачи распределительного типа, Формы записи задач линейного программирования0.

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

Правую часть неравенства всегда можно сделать неотрицательной, умножив неравенства -1. Неравенства Три задачи распределительного типа, Формы записи задач линейного программирования преобразуются в Три задачи распределительного типа, Формы записи задач линейного программированиятакже умножением на -1. Например, неравенство

-x1+x2Три задачи распределительного типа, Формы записи задач линейного программирования -3

эквивалентно неравенству:

-x1+x2+S1=-3, S1 Три задачи распределительного типа, Формы записи задач линейного программирования0.

x1-x2-S1=3.

Свободная переменная.

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

Пример. Ресторан быстрого обслуживания торгует мясными пирогами и гамбургерами. На порцию пирога идет четверть фунта мяса, на гамбургер- 0,2 фунта. В начале работы имеется 200 фунтов мяса, можно получить еще, но с наценкой в 25 центов. Оставшиеся в конце дня мясо жертвуется благотворительной организации. Доход от одной порции пирога 20 центов, от одного гамбургера- 15 центов. В день ресторан не может продать более 900 порций. Какова должна быть доля каждого блюда, чтобы максимизировать доход?

Вау!! 😲 Ты еще не читал? Это зря!

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

создано: 2015-06-12
обновлено: 2021-05-12
132477



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


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

Математические методы исследования операций .Теория игр и расписаний.

Термины: Математические методы исследования операций .Теория игр и расписаний.