Задачи линейного программирования канонического вида метод симплекса



бет3/6
Дата11.06.2022
өлшемі489.26 Kb.
#268043
түріСамостоятельная работа
1   2   3   4   5   6
1.2.3 Решение проблемы диеты
На рисунке 1 мы изобразили четыре ограничения для проблемы диеты, рассмотренной ранее (см. (4); A, x и b определены в (3)). Прежде чем найти оптимальное решение, мы сначала находим все возможные возможные решения. Обратите внимание, что если (x1, x2) является возможным решением, то оно должно быть в области в первом квадрант над обеими линиями. Таким образом, существует бесконечно много кандидатов на оптимальное решение (или решений!). К счастью, мы можем значительно сократить список кандидатов для поиска оптимальных решений. То идея несколько схожа по духу с задачей оптимизации из исчисления; здесь мы сначала показываем , что оптимальные решения не могут возникать внутри и, следовательно, должны возникать на границе многоугольника, а затем показываем, что они должны возникать в вершине. Мы пытаемся минимизировать линейную функцию затрат 20x1 + 2x2. Рассмотрим функцию Стоимость(x1, x2) = 20x1+2x2. Мы смотрим на контуры, где функция постоянна: Стоимость (x1, x2) =c; мы набрасываем некоторые контуры постоянных затрат на рисунке 2. Обратите внимание, что контуры постоянных затрат являются параллельные; это ясно, поскольку они имеют вид 20x1 + 2x2 = c. Кроме того, чем меньше значение c, тем меньше стоимость. Таким образом, учитывая выбор между двумя линиями, для минимизации затрат мы выбираем нижнюю линию.
Следовательно, если мы начнем с любой точки внутри многоугольника (множества возможных решений), двигаясь по линии постоянной стоимости, мы можем перейти к точке на границе с той же стоимостью. Таким образом, чтобы найти оптимальное решение, достаточно проверить допустимые решения на границе; это общая особенность задач линейного программирования. Кроме того, достаточно проверить вершины многоугольника. Это связано с тем, что если мы находимся на одном из краев многоугольника, то при перемещении влево стоимость уменьшается. Таким образом, этого достаточно виде:

Рисунок 1: График ограничений для проблемы диеты

Рисунок 2: График ограничений для проблемы диеты


Рисунок 3: График ограничений для задачи о диете
проверить три вершины, чтобы найти самую дешевую диету, содержащую минимальные суточные потребности. Из-за стоимости единицы хлопьев (20 долларов) и стейка (2 доллара) наклон линии таков , что в самой дешевой диете нет хлопьев, а только стейк. Вот почему мы выбрали такие необоснованные цифры для стоимости хлопьев и стейка, чтобы мы могли проверить наше первое решение с помощью нашей интуиции. Давайте теперь рассмотрим более разумный набор цен. Пусть функция затрат равна Cost(x1, x2) =x1 + x2 (таким образом, оба продукта стоят 1 доллар за единицу). Мы построим некоторые линии затрат на рисунке 3. Примечание теперь, когда оптимальное решение, хотя и остается одной из вершинных точек, не равно x1 = 0.

2 Каноническая форма представления ЗЛП


Из общей формы представления ЗЛП и из ее экономического смысла следует, что ЗЛП может быть поставлена как задача на нахождение либо максимального, либо минимального значения целевой функции. Чтобы сформулировать четкий алгоритм решения ЗЛП, можно для универсальности допустить, что во всех случаях будет рассматриваться ЗЛП, в которой необходимо найти минимальное значение целевой функции. Такое допущение может быть оправданным, так как любую задачу оптимизации на поиск максимального значения можно свести к задаче
максимизации значения целевой функции путем умножением целевой функции на -1:
max f (x1, x2 ,..., xn ) = min(− f (x1, x2 ,..., xn )) Действительно, наглядно это можно подтвердить на примере обычной линейной функции, зависящей от одного аргумента х:

На отрезке [A;D] max(−kx + b) = min(kx − b) и наоборот.
Кроме того, из общей постановки ЗЛП следует также , что в системе ограничений
неравенства могут иметь различные знаки соотношений (<,>,=), а с точки зрения
применения алгебраических методов поиска решений систему неравенств следует
преобразовать в систему равенств.
В связи с этим, в теории ЛП была введена каноническая (стандартная) форма
представления ЗЛП. Чтобы ее получить, в исходной задаче должны быть проведены
следующие преобразования:
1) целевую функцию следует минимизировать;
2) системы неравенств ограничений должны быть преобразованы в систему
равенств путем введения дополнительных переменных с неотрицательной правой частью;
3) все переменные должны быть неотрицательными.
Рассмотрим возможные способы преобразования типа 2:
А) пусть имеется неравенство вида a1x + a2 y  b тогда, чтобы преобразовать его в
равенство необходимо добавить некоторую дополнительную переменную w:
a1x + a2 y + w = b
Y = kx-bС точки зрения экономического смысла ЗЛП ограничения, записанные в виде
неравенств со знаком <=, означают, что расход некоторого ресурса на выпуск
производимой продукции не должен превышать запаса этого ресурса. Следовательно,
если в каком-то ограничении неравенство выполниться как равенство, то это будет
означать, что ресурс был использован полностью в производстве, в противном случае
(знак <) – ресурс был использован неполностью. С этой точки зрения величину w можно трактовать как остаток некоторого ресурса (и по смыслу он может быть только неотрицательным).
Б) пусть имеется неравенство вида a1x + a2 y  b , тогда для преобразования его в
равенство можно вычесть некоторую переменную w:
a1x + a2 y − w = b
Тогда, проведя аналогичные рассуждения, можно объяснить экономический смысл
такой переменной как избыток некоторого ресурса.
В) Неотрицательность правой части равенств можно получить путем умножения
всего равенства на -1, то есть a1x + a2 y = −b равносильно − a1x − a2 y = b .
Введение остаточных или избыточных переменных не меняет исходную
постановку ЗЛП, а в уравнении целевой функции их учитывают с нулевыми
коэффициентами. Таким образом, каноническая форма ЗЛП в общем случае имеет вид:

В качестве примера представим задачу в канонической
форме:



Достарыңызбен бөлісу:
1   2   3   4   5   6




©melimde.com 2022
әкімшілігінің қараңыз

    Басты бет
Сабақтың тақырыбы
бойынша жиынтық
жиынтық бағалау
Сабақ тақырыбы
Сабақтың мақсаты
ғылым министрлігі
тоқсан бойынша
бағдарламасына сәйкес
бағалауға арналған
Сабақ жоспары
Реферат тақырыбы
жиынтық бағалауға
сәйкес оқыту
арналған тапсырмалар
Қазақстан республикасы
білім беретін
оқыту мақсаттары
бағалау тапсырмалары
рсетілетін қызмет
Жалпы ережелер
жиынтық бағалаудың
республикасы білім
бекіту туралы
тоқсанға арналған
Қазақстан тарихы
Қазақстан республикасының
мерзімді жоспар
арналған жиынтық
қызмет стандарты
болып табылады
жалпы білім
арналған әдістемелік
бағалаудың тапсырмалары
Мектепке дейінгі
оқыту әдістемесі
Қазақ әдебиеті
нтізбелік тақырыптық
пәнінен тоқсанға
Зертханалық жұмыс
Инклюзивті білім
Әдістемелік кешені
республикасының білім
білім берудің
туралы жалпы
Қазақстанның қазіргі
Қысқа мерзімді
Жұмыс бағдарламасы
қазақ тілінде
қазіргі заман
туралы хабарландыру
атындағы жалпы