Номера задач из "упражнений" указаны в таблице ниже



страница2/26
Дата04.05.2016
Размер1.06 Mb.
1   2   3   4   5   6   7   8   9   ...   26

Примеры моделей, приводящих к задачам линейного программирования


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

1. Задача о диете


Изучается вопрос о рационе кормления некоего живого существа. Пусть на данном этапе развития этого существа наиболее важными для него являются три питательных вещества. Условно будем говорить о витаминах Е, F и PP. Пусть в нашем распоряжении два продукта, в которых эти витамины содержатся. Содержание витаминов в единице продуктов и суточная потребность в витаминах задаются в приведенной табл. 1.

Табл. 1. Данные к задаче о диете.

Продукт

1

2

Суточная потребность

Е

5

2

10

F

3

4

12

РР

1

5

5

Стоимость единицы продуктов соответственно 13 и 8 денежных единиц.

Обозначим через x1 количество первого продукта, а через x2 — количество второго продукта, включаемых в ежедневный рацион. Приходим к задаче



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





Рис. 1. Иллюстрация решения задачи о диете.

Изучение рис. 1 позволяет выдвинуть гипотезу: оптимальный рацион задается точкой пересечения прямых, отвечающих первым дум ограничениям. Найдем эту точку х*, решая соответствующую систему линейных уравнений; это дает x*=(8/7; 15/7),а стоимость полученного рациона составляет 32 денежных единицы.

Покажем строго аналитически, что действительно х* — оптимальный рацион. Для этого нужно показать, что стоимость любого иного из допустимых рационов не меньше чем 32 денежных единицы. На математическом языке это означает, что для любого решения системы неравенств, описывающих множество X, выполняется неравенство

.

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

Возвращаясь к содержательному изложению, доказанный факт можно сформулировать следующим образом: если рацион удовлетворяет ограничениям по потреблению витаминов Е и F, то (независимо от потребления витамина РР) стоимость рациона не может быть меньше, чем 32 денежных единицы. Тем более это верно для рациона, удовлетворяющего также ограничению по потреблению витамина PP. Но стоимость рациона х* и составляет 32 денежных единицы. Таким образом, это рацион с минимальной стоимостью. Оптимальность полученного рациона х* доказана.

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

Пусть учитываются mтипов питательных веществ, содержащихся в n продуктах, и aij указывает содержание i-го питательного вещества в единице j-го продукта. Пусть стоимость одной единицы j-го продукта равна Cj, а суточная потребность в i-м питательном веществе равнаbi. Обозначив через Xj количество j-го продукта в суточном рационе, получаем следующую задачу поиска рациона минимальной стоимости:

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


2. Классическая транспортная задача


Рассмотрим простейшую задачу, возникающую при моделировании транспортных потоков. Для простоты рассматривается вопрос об организации перевозок лишь какого-то одного продукта от пунктов, в которых он производится (или складируется), к потребителям, расположенным в других пунктах. Пусть имеется m пунктов производства и n пунктов потребления. Известно, что в i-м пункте производства имеется di единиц рассматриваемого продукта, а объем его потребления в j-м пункте потребления составляет hj единиц. Для простоты предположим, что затраты на перевозку продукта из i-го пункта производства в j-й пункт потребления пропорциональны объему поставки, а значит, легко вычисляются, если заданы величины Cij, указывающие стоимость перевозки единицы продукта. Пусть эти величины известны. Требуется спланировать перевозки так, чтобы суммарные затраты на реализацию предлагаемого плана были как можно меньше. Ясно, что задачу имеет смысл рассматривать лишь в предположении, что суммарный объем производства не меньше суммарного объема потребления, т. е..

Обозначим через xij объем планируемой поставки продукта из i-го пункта производства в j-й пункт потребления. Тогда суммарный объем вывоза из i-го пункта производства будет равен , а суммарный объемпоставки в j-й пункт потребления составит . Затраты на реализацию всех перевозок будут задаваться формулой . В результатеполучаем следующую математическую задачу:



Несмотря на кажущееся полное внешнее отличие получаемой математической задачи от той, которую мы получили при рассмотрении рационов кормления, на самом деле это задачи одного класса: требуется минимизировать некоторую линейную функцию при линейных ограничениях на переменные. Однако в новой задаче среди ограничений, наряду с неравенствами, присутствуют и уравнения. Но это, как мы увидим далее, не является существенным. Тот факт, что в транспортной задаче мы имеем двухиндексную нумерацию неизвестных, конечно, не является принципиальным, поскольку можно «вытянуть» матрицу {xij} в вектор, перенумеровав неизвестные заново подряд номерами от 1 до mn.


3. Задача линейного раскроя


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

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

Пусть изделие комплектуется из деталей двух типов, и соответствующие заготовки имеют длины l1 = 51см и l2 = 33 см. Пусть для определенности на одно изделие идет одна деталь первого типа и одна деталь второго типа.

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

Простейший план состоит в том, что из каждой полосы мы пытаемся выкроить максимальное количество комплектов заготовок, идущих на одно изделие. Это приводит нас к плану: из каждой полосы выкраивается 2 комплекта, и остается остаток длиной 57 см, из которого комплект уже не выкраивается, так как на один комплект нужно 51см + 33 см = 84 см (> 57 см). Остаток поступает в отходы. Схематически этот план изображен на рис. 2.



Рис. 2. Допустимый план раскроя в задаче линейного раскроя

Обратив внимание на то, что из остатка в 57 см можно выкроить еще либо первую, либо вторую заготовку, можем предложить более экономичный план: кроим сразу две полосы указанным способом, но из первой дополнительно выкраиваем еще одну заготовку первого типа, а из второй — еще одну заготовку второго типа. В результате из двух полос получим 5 изделий, в то время как при прежнем способе организации производства по плану из двух полос получалось 4 изделия. Схематически новый план изображен на рис. 3.





Рис. 3. Улучшенный план раскроя в задаче линейного раскроя

Анализируя два предложенных способа производства, мы можем теперь конкретизировать понятие плана и определить показатель экономичности плана. Мы рассматриваем лишь такие способы производства, которые носят циклический характер, когда каждые z полос раскраиваются в соответствии с одним и тем же технологическим процессом. Будем называть z длиной технологического цикла. В 1 плане мы имели z = 1, во 2плане имеем z = 2. План задается указанием z и описанием технологического процесса, по которому кроится каждая из следующих друг за другом партий из z полос. В качестве показателя экономичности плана мы берем отношение числа изделий, получаемых на одном технологическом цикле, к длине цикла. Будем обозначать его через. Для плана имеем , для плана получаем .

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

Ясно, что из одной полосы выкраивается 4 заготовки первого типа либо 6 заготовок второго типа. Поэтому если кроить 3 полосы по первому способу и 2 по второму, то на одном технологическом цикле (его длина z = 5) мы получим 12 изделий. Схема плана приведена на рис. 4.





Рис. 4. Третий план раскроя в задаче линейного раскроя

Показатель экономичности данного плана будет 12/5, т.е. этот план оказался менее выгодным, чем план : из 10 полос по плану получается 25 изделий, а по плану — лишь 24 изделия.

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

Как видим, план получается комбинированием различных раскроев одной полосы. Такие раскрои назовем элементарными кроями. Каждый элементарный крой можно описать в виде двумерного вектора а = 12), компоненты которого ai указывают, сколько заготовок соответствующего типа получается из одной полосы при данном крое. Если рассматривать только достаточно экономичные крои, при которых из получающегося остатка уже ни одну заготовку не выкроить, то мы получим следующие 5 векторов: а1 = (4,0), а2 = (3, 2), а3 = (2,3), а4 = (1,5), а5 = (0,6). Крой а = (2,2), который мы использовали в плане , в этот перечень не попал, так как из остатка в 57 см можно еще выкроить любую из заготовок. Но для описания всех планов достаточно рассматривать только перечисленные крои а1, ..., а5, если считать, что некоторые заготовки после комплектации изделий могут оставаться в избытке. В частности, план можно рассматривать как применение кроя а2, но при этом после комплектации двух изделий первая заготовка остается в избытке. Этот же план можно рассматривать и как применение кроя а3, но при этом в избытке будет оставаться уже вторая заготовка.

Пусть на одном технологическом цикле кроится полос по соответствующим кроям и комплектуется v изделий. Длина технологического цикла, таким образом, составляет полос. Выход заготовокна одном цикле задается вектором . Введем также вектор k = (1,1), указывающий комплектность заготовок в одном изделии. В результате приходим к следующей математической задаче:

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



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

Для решения полученной задачи мы вновь можем использовать геометрическую интерпретацию, хотя здесь она иная по сравнению с рассмотренной ранее для задачи о диете (см. рис. 5). Рассмотрим пространство R2 и нанесем точки, отвечающие кроям а1, ..., а5. Если опустить требование рациональности, то при изменении переменных xj в соответствии с условиями 2' и 3' точка, отвечающая левой части неравенства 1', будет заполнять многоугольникМ, описывающий выпуклую оболочку точек а1,…, а5. Чтобы описать все точки q, удовлетворяющие неравенству, нужно рассматривать точки вида а + wпри. Геометрически мы получим все множество таких точек, если пририсуем отрицательный квадрант R2 к точке а. Значит, чтобы описать все множество точекq,удовлетворяющих неравенству , мы должны указанную процедуру пририсовывания квадранта проделать с каждой точкой из М,что приводит к множеству. Его образование можно описать иначе: многоугольник М сдвигается произвольно влево и вниз.



Рис. 5. Иллюстрация к задаче линейного раскроя.

Рассмотрим теперь правую часть неравенства 1'. При изменении v' точка v'kначертит прямую, проходящую через начало координат и точку k. Ясно, что нас интересуют лишь неотрицательные значения v', и это даст нам луч.

В результате получаем следующую геометрическую формулировку задачи: нужно двигать точку а по лучу от начала координат (это соответствует увеличению значения v') до тех пор, пока она находится в множестве .

Анализ рис. 5 позволяет высказать гипотезу: точка луча , лежащая в и имеющая максимальное значение , принадлежит стороне многоугольника с вершинами в а2 и а4. Это говорит о том, что в оптимальном плане используются крои, отвечающие этим точкам, тем самым прочие крои не используются. Если через и обозначить оптимальные значения переменных, то наша гипотеза состоит в том, что . Для переменных , и получаем систему уравнений



Решением этой системы является: , , . Помножив все величины на 5, осуществляем возврат к целочисленным значениям: , т.е., предположительно, оптимальным является план с длиной технологического цикла в 5 полос (z = 5), из которых 4 кроятся по элементарному крою а2, а одна полоса — по крою а4 (рис. 6).





Рис. 6. Оптимальный план раскроя в задаче линейного раскроя

Выход заготовок по этому плану составит3 х 4 + 1 = 13, 2 х 4 + 5 = 13.В самом деле, получаем 13 изделий. По этому плану из 10 полос мы получаем 26 изделий, в то время как по лучшему из ранее рассмотренных плану из 10 полос получали лишь 25 изделий.

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

1   2   3   4   5   6   7   8   9   ...   26


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница