Главная Обратная связь

Дисциплины:






ОСН.ВИДЫ ЗАПИСИ ЗЛП,СПОСОБЫ ПРЕОБРАЗОВАНИЯ



ПРИКЛАДНЫЕ ЗЛП

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

 

Задача о наилучшем использовании ресурсов.

Пусть некоторая производственная единица (цех, завод, объединение и т.д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексом j (j=1,..,n). Ее будем обозначать Пj. Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.). Все эти виды ограничивающих факторов называют ингредиентами Ri. Пусть их число равно m; припишем им индекс i (i=1,..,m). Они ограничены, и их количества равны соответственно b1,…,bi,…,bm условных единиц. Таким образом, b = (b1,…,bi,…,bm) – вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т.д. Примем в качестве такой меры, например, цену реализации cj (j=1,..,n), т.е. с = (c1,…,cj,…,cn) – вектор цен. Известны также технологические коэффициенты aij, которые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции j–го вида. Матрицу коэффициентов aij называют технологической и обозначают буквой А. Имеем А = [aij]. Обозначим через х = (x1,…,xj,…,xn) план производства, показывающий, какие виды товаров П1,..., Пj,...,Пn нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.

Z= c1x1+…+ cn xn (max)

ai1xi+…+aijxj+…ainxn≤bi

xj≥0 (j=1,..,n)

Задача о выборе оптимальных технологий.

Пусть при производстве какого–то общественно необходимого продукта используется n технологий. При этом требуется m видов ресурсов, заданных объемами bi (i=1,..,m). Эффективности технологий, т. е. стоимость конечной продукции, производимой в единицу времени по j–й (j=1,..,n) технологии, обозначим cj. Пусть, далее, aij – расход i–го ресурса в единицу времени по j–й технологии. В качестве неизвестной величины xj примем интенсивность использования j–й технологии, т. е. время, в течение которого продукция производится по j–й технологии. Пренебрегая временем переналадок, необходимым для перехода от одной технологии к другой, получаем следующую математическую модель задачи: найти план интенсивностей использования технологий х = (x1,…,xj,…,xn), обеспечивающий максимум выпуска продукции в стоимостном выражении:



Z= c1x1+…+ cn xn (max)

ai1xi+…+aijxj+…ainxn≤bi

xj≥0 (j=1,..,n)

Задача о смесях.

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

Модель задачи о наилучшем составе смеси рассмотрим на примере задачи о диете. Имеются пищевые продукты, известные под номерами 1, 2, ..., n. Они содержат различные питательные вещества, обозначаемые номерами 1, 2, ..., m (углеводы, белки, жиры, витамины, микроэлементы и др.). Единица j–го продукта содержит aij единиц i–го питательного вещества. Для нормальной жизнедеятельности в заданный промежуток времени нужно потреблять не менее bi единиц i–го питательного вещества. Обозначим через cj стоимость единицы продукта j–го вида. Требуется выбрать рацион минимальной стоимости, содержащий необходимые количества питательных веществ. План задачи – это количества xj продуктов каждого вида, обеспечивающие необходимое количество питательных веществ при минимальных затратах на исходные продукты.

Z= c1x1+…+ cn xn (min)

ai1xi+…+aijxj+…ainxn≥bi

xj≥0 (j=1,..,n)

Задача о раскрое материалов.

Суть задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект– заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму. Модель задачи раскроя по одному измерению длинномерных материалов (прутков, труб, профильного проката и др.) может быть сформулирована так. Пусть имеется N штук исходного материала, длина каждой штуки равна L. Нужны заготовки m видов, длины которых равны li (i=1,..,m). Известна потребность в заготовках каждого вида, она равна bi. Изучение вопроса раскроя (построение технологической карты раскроя) показывает, что можно выделить n приемлемых вариантов раскроя исходного материала длиной L на заготовки длиной li. Обозначим через aij количество заготовок i–го вида, получаемое при раскрое единицы исходного материала по j–му (j=1,..,n) варианту, cj – отходы при раскрое единицы исходного материала по j–му варианту. План задачи х=(x1,…,xj,…,xn), где xj – количество единиц исходного материала, планируемое к раскрою по j–му варианту.

Z= c1x1+…+ cn xn (min)

x1+...+Xn≤N

ai1xi+…+aijxj+…ainxn≥bi

xj≥0 (j=1,..,n)

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

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

Имеется m пунктов производства, в каждом из которых сосредоточено ai (i=1,..,m) единиц однородного продукта. Этот продукт нужно доставить n потребителям, где потребность составляет bj (j=1,..,n) единиц. Причем . Известны величины cij – затраты на перевозку единицы продукта из i–го пункта производства в j–й пункт потребления. Обозначим через xij количество продукта, перевозимое из i –го пункта производства в j–й пункт потребления. Матрица С = [cij] называется матрицей тарифов, X = [xij] – матрицей перевозок. С целью удобства построения математической модели матрицы тарифов и перевозок совмещают в одну, именуемую макетом транспортной задачи.

(min)

(i=1,..,m)

(j=1,..,n)

xij≥0 (i=1,..,m; j=1,..,n)

Задача о размещении заказа.

Речь идет о задаче распределения заказа между предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказа. Требуется составить план размещения заказа, при котором с имеющимися производственными возможностями заказ был бы выполнен, а показатель эффективности достигал экстремального значения. Сформулируем задачу конкретнее. Имеется m однородных групп оборудования, на котором нужно выполнить заказ на выпуск n видов продукции в объемах x*j (j=1,..,n) единиц. Мощность оборудования каждого вида ограничена, например, фондом рабочего времени Ti (i=1,..,m). Производительность оборудования каждого вида задана коэффициентом aij, который показывает, сколько единиц продукции j–гo вида можно произвести на i–м оборудовании в единицу времени. Кроме того, известны коэффициенты cij, отражающие все затраты, вызванные изготовлением на i–м оборудовании в единицу времени продукции j–гo вида. Требуется найти план X=[xij] размещения заказа (загрузки оборудования), т.е. установить, сколько времени i–я группа оборудования будет занята изготовлением j–й продукции.

(min)

(i=1,..,m)

1) по некоторым видам продукции допускается перевыполнение плана:

(j=1,..,n1)

2) выпуск продукции должен соответствовать плану:

(j=n1+1,…,n2)

3) продукция, заказ на которую принимается для более полной загрузки оборудования:

(j=n2+1,…,n)

xij≥0 (i=1,..,m; j=1,..,n)

ОСН.ВИДЫ ЗАПИСИ ЗЛП,СПОСОБЫ ПРЕОБРАЗОВАНИЯ

ЗЛП в общей постановке имеет 3 формы:

- произвольная форма:

- симметричная форма:

- каноническая форма ЗЛП:

Преобразования:

1. Неравенство вида «≥» можно преобразовать в неравенство вида «≤» путём замены знаков в обеих частях.

2. Если в ЗЛП какая-то переменная не подчинена условию неотрицательности, ее заменяют разностью двух других неотрицательных переменных.

3. min(f) = -max(-f), т.е. задачи минимизации функции при необходимости можно заменить задачей максимизации, и наоборот, т.к. экстремумы этих функций достигаются в одной и той же точке, а после решения задачи надо заменить знак оптимума на противоположный;

4. Преобразование неравенств в уравнения и уравнений в неравенства проводится на основании теоремы: Всякому решению (α1;…; αn) неравенства а1х1 +…+ anxn≤a соответствует вполне определенное решение (α1;…; αn ; αn+1) уравнения а1х1 +…+ anxn + xn+1= a, в котором xn+1≥0. И наоборот, каждому решению (α1;…; αn ; αn+1) уравнения а1х1 +…+ anxn + xn+1= a и неравенства xn+1 ≥ 0 соответствует вполне определенное решение (α1;…; αn) неравенства а1х1 +…+ anxn ≤ a.

На основании этой теоремы систему m линейных неравенств с n переменными

a11x1 + … + a1nxn ≤ a10;

…..

am1x1 + … + amnxn ≤ am0

можно заменить эквивалентной системой m линейных уравнений с n+m переменными

a11x1 + … + a1nxn + xn+1 = a10;

…..

am1x1 + … + amnxn + xn+m = am0

 





sdamzavas.net - 2020 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...