Задача раскроя

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

Согласно данным Конфедерации европейских производителей бумаги, в 2012 году 1331 бумагоделательных машин в регионе производят в среднем отходов на 56 млн евро (примерно 73 млн долларов США) каждая. Экономии даже 1 % будет очень существенной.

Формулировка задачи и подходы к решению

Стандартная формулировка задачи раскроя (но не единственная) предполагает список m заказов, в каждом заказе требуется <math>q_j, j = 1,\ldots,m</math> кусков. Образуем все возможные комбинации раскроя («карты раскроя») и связываем с каждой картой положительную целую переменную <math>x_i</math>, показывающую, сколько раз карта использовалась. Выпишем задачу линейного программирования:

<math>\min\sum_{i=1}^n c_i x_i</math>

<math>\sum_{i=1}^n a_{ij} x_i \ge q_j, \quad \quad \forall j=1,\dots,m</math>

<math>x_i \ge 0</math>, целое

где <math>a_{ij}</math> — сколько раз заказ <math>j</math> появляется в карте <math>i</math> и <math>c_i</math> — цена (часто потери) карты <math>i</math>. Точная природа ограничений может вести к слегка различным математическим характеристикам. Приведённые ограничения являются ограничениями на минимум (по меньшей мере заданное количество должно быть произведено, но не исключается, что будет произведено и больше). Если <math>c_i=1</math>, требуется минимизировать число разрезаемых кусков исходного материала. Если ограничения с неравенств заменить на равенства, задача называется упаковкой в контейнеры. В более общей формулировке ограничения двухсторонние (и в этом случае решение минимизации потерь может отличаться от решения с минимальным числом кусков исходного материала):

<math>q_j \le \sum_{i=1}^n a_{ij} x_i \le Q_j, \quad \quad \forall j=1,\dots,m</math>

Такая формулировка задачи применима не только к одномерному случаю. Возможно много вариаций, например, цель — не минимизация потерь, а максимизация общего числа произведённого товара.

В целом, число возможных карт растёт экспоненциально от m, числа заказов. При росте числа заказов может оказаться непрактичным перечислять возможные карты раскроя.

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

Исходный метод Гилмора и Гомори не был целочисленным, так что решение могло содержать дробные составляющие, например, некоторая карта должна была использоваться 3,67 раз. Округление до ближайшего целого часто не работает, в том смысле, что это приводит к подоптимальному решению и недопроизводству или перепроизводству для некоторых заказов (и возможное нарушение ограничений, если они двусторонние). Этот недостаток преодолён в новых алгоритмах, которые позволяют находить оптимальные решения (в смысле нахождения решения с минимальными отходами) очень больших задач (в общем случае больших, чем нужно на практике ).

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

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

• Задача минимального склада: найти последовательность раскроя, чтобы не накапливалось большого числа частично выполненных заказов. Задача была открытой вплоть до 2007 года, когда опубликован эффективный алгоритм, основанный на динамическом программировании.

• Задача минимального числа смен ножей (для одномерной задачи раскроя): найти последовательность применения карт раскроя, чтобы минимизировать число перемещений режущих ножей. Данная задача является частным случаем обобщённой задачи коммивояжёра.

Иллюстрация одномерной задачи раскроя

Бумагоделательная машина может производить неограниченное число рулонов (заготовок), каждая 5600 мм шириной. Нужно получить следующие 13 конечных рулонов:

Ширина	Рулонов
1380	22
1520	25
1560	12
1710	14
1820	18
1880	18
1930	20
2000	10
2050	12
2100	14
2140	16
2150	18
2200	20

Решение

Имеется 338 возможных карт раскроя для этой маленькой задачи. Оптимальное решение требует 73 исходных рулона и имеет 0,401 % отходов. Можно показать, что минимальное число карт раскроя для такого количества отходов равно 10. Можно также вычислить, что существует 19 таких различных решений, каждое с 10 картами раскроя и 0,401 % отходов. Одно из таких решений показано ниже и на рисунке:

Число карт	Разрезы
2	1820 + 1820 + 1820
3	1380 + 2150 + 1930
12	1380 + 2150 + 2050
7	1380 + 2100 + 2100
12	2200 + 1820 + 1560
8	2200 + 1520 + 1880
1	1520 + 1930 + 2150
16	1520 + 1930 + 2140
10	1710 + 2000 + 1880
2	1710 + 1710 + 2150
73

Классификация

Задачи раскроя можно классифицировать различными способами. Один путь — размерность раскроя: выше приведённый пример иллюстрирует одномерный раскрой (1D). Другие промышленные применения 1D раскроя — резка труб, кабелей и стальных прутков. Двумерные (2D) задачи применяются при производстве мебели, одежды и стекла. Существует не так уж много трёхмерных (3D) применений раскроя, однако близкие 3D задачи упаковки имеют много промышленных приложений, в частности, распределение объектов в контейнеры для водного транспорта (смотрите, например, Контейнерные перевозки, близкая к ней задача упаковки шаров изучалась с 17-го столетия (Гипотеза Кеплера)).

Задача раскроя в бумажной, плёночной и сталепрокатной промышленностях

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

• Двустадийный процесс, когда рулон производится на первой стадии, а затем поступает в обработку ещё раз на другой машине. Например, вся офисная бумага (например, формат A4 в Европе, Letter в США) производится в таком процессе. Трудности появляются ввиду того, что машины для второго процесса уже машин первого. Эффективное использование обеих стадий процесса важно (как с точки зрения экономии материала, так и экономии энергии) и то, что эффективно для первой стадии может оказаться неэфективным для второй, и приходится искать компромисс. Металлизированная плёнка (используемая для упаковки продуктов питания) и покрытая пластиком бумага (упаковочный картон для жидкостей, например, для упаковки соков) — другие примеры таких процессов.

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

• В качестве дополнительного ограничения можно привести, например, ограничение на направление разрезания — различные края листа могут иметь большое различие в толщине и некоторые приложения очень чувствительны к этому.

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

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

• Имеются также задачи, когда результирующие рулоны не обязательно должны быть одного диаметра, а могут быть в пределах некоторого интервала. Иногда эту задачу называют задачей 1½ размерности. Этот вариант появляется, например, при производстве гофрокартона.

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

Программное обеспечение для решения задач раскроя для бумажной промышленности поставляют ABB Group, Greycon, Honeywell и Tieto.

Алгоритм раскроя для сталепрокатной промышленности сформулирован Робертом Гонгорра (Robert Gongorra) в 1998 году и S.O.N.S (Steel Optimization Nesting Software) разработал программное обеспечение для улучшения использования стального листа и уменьшения отходов.

Задача раскроя для стекольной промышленности

Задача гильотинного раскроя — это задача резки листов стекла на прямоугольники определённых размеров, используя только разрезы, проходящие по всей длине (или ширине) листа.

Задача ассортимента

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

История

Задача раскроя впервые сформулирована Канторовичем в 1939 году. В 1951 году, ещё до того, как компьютеры стали широко доступны, Л. В. Канторович и В. А. Залгаллер предложили способ решения задачи экономного использования материала при раскрое с помощью линейного программирования. Предложенная техника позднее получила название Метод генерации столбцов.

Программное обеспечение

Название	Лицензия	Короткое описание
VPSolver	GPL	Свободное программное обеспечение «Vector Packing Solver» ([code.google.com/p/vpsolver/ VPSolver]), которое можно использовать для оптимизации одномерного раскроя. Метод решения основывается на формулировке потока в графе.

Литература

• Linear Programming. — W. H. Freeman, 1983. — ISBN 978-0-7167-1587-0.
• Hatem Ben Amor, J.M. Valério de Carvalho. Column Generation // Cutting Stock Problems in Column Generation / Guy Desaulniers, Jacques Desrosiers and Marius M. Solomon. — Springer, 2005. — Т. XVI. — ISBN 0-387-25485-4.

Ссылки

• [paginas.fe.up.pt/~esicup/tiki-index.php European Special Interest Group on Cutting & Packing]
• [pastebin.com/1XPiBD20 A rudimentary brute-force algorithm for cutting stock]
• [www.codeproject.com/Articles/706136/Csharp-Bin-Packing-Cutting-Stock-Solver Bin Packing and Cutting Stock Solver Algorithm]

Отрывок, характеризующий Задача раскроя

– Я верно знаю, что Кутузов, как непременное условие, выговорил, чтобы наследник цесаревич не был при армии: Vous savez ce qu'il a dit a l'Empereur? [Вы знаете, что он сказал государю?] – И князь Василий повторил слова, будто бы сказанные Кутузовым государю: «Я не могу наказать его, ежели он сделает дурно, и наградить, ежели он сделает хорошо». О! это умнейший человек, князь Кутузов, et quel caractere. Oh je le connais de longue date. [и какой характер. О, я его давно знаю.]
– Говорят даже, – сказал l'homme de beaucoup de merite, не имевший еще придворного такта, – что светлейший непременным условием поставил, чтобы сам государь не приезжал к армии.
Как только он сказал это, в одно мгновение князь Василий и Анна Павловна отвернулись от него и грустно, со вздохом о его наивности, посмотрели друг на друга.


В то время как это происходило в Петербурге, французы уже прошли Смоленск и все ближе и ближе подвигались к Москве. Историк Наполеона Тьер, так же, как и другие историки Наполеона, говорит, стараясь оправдать своего героя, что Наполеон был привлечен к стенам Москвы невольно. Он прав, как и правы все историки, ищущие объяснения событий исторических в воле одного человека; он прав так же, как и русские историки, утверждающие, что Наполеон был привлечен к Москве искусством русских полководцев. Здесь, кроме закона ретроспективности (возвратности), представляющего все прошедшее приготовлением к совершившемуся факту, есть еще взаимность, путающая все дело. Хороший игрок, проигравший в шахматы, искренно убежден, что его проигрыш произошел от его ошибки, и он отыскивает эту ошибку в начале своей игры, но забывает, что в каждом его шаге, в продолжение всей игры, были такие же ошибки, что ни один его ход не был совершенен. Ошибка, на которую он обращает внимание, заметна ему только потому, что противник воспользовался ею. Насколько же сложнее этого игра войны, происходящая в известных условиях времени, и где не одна воля руководит безжизненными машинами, а где все вытекает из бесчисленного столкновения различных произволов?
После Смоленска Наполеон искал сражения за Дорогобужем у Вязьмы, потом у Царева Займища; но выходило, что по бесчисленному столкновению обстоятельств до Бородина, в ста двадцати верстах от Москвы, русские не могли принять сражения. От Вязьмы было сделано распоряжение Наполеоном для движения прямо на Москву.
Moscou, la capitale asiatique de ce grand empire, la ville sacree des peuples d'Alexandre, Moscou avec ses innombrables eglises en forme de pagodes chinoises! [Москва, азиатская столица этой великой империи, священный город народов Александра, Москва с своими бесчисленными церквами, в форме китайских пагод!] Эта Moscou не давала покоя воображению Наполеона. На переходе из Вязьмы к Цареву Займищу Наполеон верхом ехал на своем соловом энглизированном иноходчике, сопутствуемый гвардией, караулом, пажами и адъютантами. Начальник штаба Бертье отстал для того, чтобы допросить взятого кавалерией русского пленного. Он галопом, сопутствуемый переводчиком Lelorgne d'Ideville, догнал Наполеона и с веселым лицом остановил лошадь.
– Eh bien? [Ну?] – сказал Наполеон.
– Un cosaque de Platow [Платовский казак.] говорит, что корпус Платова соединяется с большой армией, что Кутузов назначен главнокомандующим. Tres intelligent et bavard! [Очень умный и болтун!]
Наполеон улыбнулся, велел дать этому казаку лошадь и привести его к себе. Он сам желал поговорить с ним. Несколько адъютантов поскакало, и через час крепостной человек Денисова, уступленный им Ростову, Лаврушка, в денщицкой куртке на французском кавалерийском седле, с плутовским и пьяным, веселым лицом подъехал к Наполеону. Наполеон велел ему ехать рядом с собой и начал спрашивать:
– Вы казак?
– Казак с, ваше благородие.
«Le cosaque ignorant la compagnie dans laquelle il se trouvait, car la simplicite de Napoleon n'avait rien qui put reveler a une imagination orientale la presence d'un souverain, s'entretint avec la plus extreme familiarite des affaires de la guerre actuelle», [Казак, не зная того общества, в котором он находился, потому что простота Наполеона не имела ничего такого, что бы могло открыть для восточного воображения присутствие государя, разговаривал с чрезвычайной фамильярностью об обстоятельствах настоящей войны.] – говорит Тьер, рассказывая этот эпизод. Действительно, Лаврушка, напившийся пьяным и оставивший барина без обеда, был высечен накануне и отправлен в деревню за курами, где он увлекся мародерством и был взят в плен французами. Лаврушка был один из тех грубых, наглых лакеев, видавших всякие виды, которые считают долгом все делать с подлостью и хитростью, которые готовы сослужить всякую службу своему барину и которые хитро угадывают барские дурные мысли, в особенности тщеславие и мелочность.
Попав в общество Наполеона, которого личность он очень хорошо и легко признал. Лаврушка нисколько не смутился и только старался от всей души заслужить новым господам.
Он очень хорошо знал, что это сам Наполеон, и присутствие Наполеона не могло смутить его больше, чем присутствие Ростова или вахмистра с розгами, потому что не было ничего у него, чего бы не мог лишить его ни вахмистр, ни Наполеон.
Он врал все, что толковалось между денщиками. Многое из этого была правда. Но когда Наполеон спросил его, как же думают русские, победят они Бонапарта или нет, Лаврушка прищурился и задумался.
Он увидал тут тонкую хитрость, как всегда во всем видят хитрость люди, подобные Лаврушке, насупился и помолчал.
– Оно значит: коли быть сраженью, – сказал он задумчиво, – и в скорости, так это так точно. Ну, а коли пройдет три дня апосля того самого числа, тогда, значит, это самое сражение в оттяжку пойдет.
Наполеону перевели это так: «Si la bataille est donnee avant trois jours, les Francais la gagneraient, mais que si elle serait donnee plus tard, Dieu seul sait ce qui en arrivrait», [«Ежели сражение произойдет прежде трех дней, то французы выиграют его, но ежели после трех дней, то бог знает что случится».] – улыбаясь передал Lelorgne d'Ideville. Наполеон не улыбнулся, хотя он, видимо, был в самом веселом расположении духа, и велел повторить себе эти слова.
Лаврушка заметил это и, чтобы развеселить его, сказал, притворяясь, что не знает, кто он.
– Знаем, у вас есть Бонапарт, он всех в мире побил, ну да об нас другая статья… – сказал он, сам не зная, как и отчего под конец проскочил в его словах хвастливый патриотизм. Переводчик передал эти слова Наполеону без окончания, и Бонапарт улыбнулся. «Le jeune Cosaque fit sourire son puissant interlocuteur», [Молодой казак заставил улыбнуться своего могущественного собеседника.] – говорит Тьер. Проехав несколько шагов молча, Наполеон обратился к Бертье и сказал, что он хочет испытать действие, которое произведет sur cet enfant du Don [на это дитя Дона] известие о том, что тот человек, с которым говорит этот enfant du Don, есть сам император, тот самый император, который написал на пирамидах бессмертно победоносное имя.
Известие было передано.
Лаврушка (поняв, что это делалось, чтобы озадачить его, и что Наполеон думает, что он испугается), чтобы угодить новым господам, тотчас же притворился изумленным, ошеломленным, выпучил глаза и сделал такое же лицо, которое ему привычно было, когда его водили сечь. «A peine l'interprete de Napoleon, – говорит Тьер, – avait il parle, que le Cosaque, saisi d'une sorte d'ebahissement, no profera plus une parole et marcha les yeux constamment attaches sur ce conquerant, dont le nom avait penetre jusqu'a lui, a travers les steppes de l'Orient. Toute sa loquacite s'etait subitement arretee, pour faire place a un sentiment d'admiration naive et silencieuse. Napoleon, apres l'avoir recompense, lui fit donner la liberte, comme a un oiseau qu'on rend aux champs qui l'ont vu naitre». [Едва переводчик Наполеона сказал это казаку, как казак, охваченный каким то остолбенением, не произнес более ни одного слова и продолжал ехать, не спуская глаз с завоевателя, имя которого достигло до него через восточные степи. Вся его разговорчивость вдруг прекратилась и заменилась наивным и молчаливым чувством восторга. Наполеон, наградив казака, приказал дать ему свободу, как птице, которую возвращают ее родным полям.]
Наполеон поехал дальше, мечтая о той Moscou, которая так занимала его воображение, a l'oiseau qu'on rendit aux champs qui l'on vu naitre [птица, возвращенная родным полям] поскакал на аванпосты, придумывая вперед все то, чего не было и что он будет рассказывать у своих. Того же, что действительно с ним было, он не хотел рассказывать именно потому, что это казалось ему недостойным рассказа. Он выехал к казакам, расспросил, где был полк, состоявший в отряде Платова, и к вечеру же нашел своего барина Николая Ростова, стоявшего в Янкове и только что севшего верхом, чтобы с Ильиным сделать прогулку по окрестным деревням. Он дал другую лошадь Лаврушке и взял его с собой.


Княжна Марья не была в Москве и вне опасности, как думал князь Андрей.
После возвращения Алпатыча из Смоленска старый князь как бы вдруг опомнился от сна. Он велел собрать из деревень ополченцев, вооружить их и написал главнокомандующему письмо, в котором извещал его о принятом им намерении оставаться в Лысых Горах до последней крайности, защищаться, предоставляя на его усмотрение принять или не принять меры для защиты Лысых Гор, в которых будет взят в плен или убит один из старейших русских генералов, и объявил домашним, что он остается в Лысых Горах.
Но, оставаясь сам в Лысых Горах, князь распорядился об отправке княжны и Десаля с маленьким князем в Богучарово и оттуда в Москву. Княжна Марья, испуганная лихорадочной, бессонной деятельностью отца, заменившей его прежнюю опущенность, не могла решиться оставить его одного и в первый раз в жизни позволила себе не повиноваться ему. Она отказалась ехать, и на нее обрушилась страшная гроза гнева князя. Он напомнил ей все, в чем он был несправедлив против нее. Стараясь обвинить ее, он сказал ей, что она измучила его, что она поссорила его с сыном, имела против него гадкие подозрения, что она задачей своей жизни поставила отравлять его жизнь, и выгнал ее из своего кабинета, сказав ей, что, ежели она не уедет, ему все равно. Он сказал, что знать не хочет о ее существовании, но вперед предупреждает ее, чтобы она не смела попадаться ему на глаза. То, что он, вопреки опасений княжны Марьи, не велел насильно увезти ее, а только не приказал ей показываться на глаза, обрадовало княжну Марью. Она знала, что это доказывало то, что в самой тайне души своей он был рад, что она оставалась дома и не уехала.
На другой день после отъезда Николушки старый князь утром оделся в полный мундир и собрался ехать главнокомандующему. Коляска уже была подана. Княжна Марья видела, как он, в мундире и всех орденах, вышел из дома и пошел в сад сделать смотр вооруженным мужикам и дворовым. Княжна Марья свдела у окна, прислушивалась к его голосу, раздававшемуся из сада. Вдруг из аллеи выбежало несколько людей с испуганными лицами.
Княжна Марья выбежала на крыльцо, на цветочную дорожку и в аллею. Навстречу ей подвигалась большая толпа ополченцев и дворовых, и в середине этой толпы несколько людей под руки волокли маленького старичка в мундире и орденах. Княжна Марья подбежала к нему и, в игре мелкими кругами падавшего света, сквозь тень липовой аллеи, не могла дать себе отчета в том, какая перемена произошла в его лице. Одно, что она увидала, было то, что прежнее строгое и решительное выражение его лица заменилось выражением робости и покорности. Увидав дочь, он зашевелил бессильными губами и захрипел. Нельзя было понять, чего он хотел. Его подняли на руки, отнесли в кабинет и положили на тот диван, которого он так боялся последнее время.
Привезенный доктор в ту же ночь пустил кровь и объявил, что у князя удар правой стороны.
В Лысых Горах оставаться становилось более и более опасным, и на другой день после удара князя, повезли в Богучарово. Доктор поехал с ними.
Когда они приехали в Богучарово, Десаль с маленьким князем уже уехали в Москву.
Все в том же положении, не хуже и не лучше, разбитый параличом, старый князь три недели лежал в Богучарове в новом, построенном князем Андреем, доме. Старый князь был в беспамятстве; он лежал, как изуродованный труп. Он не переставая бормотал что то, дергаясь бровями и губами, и нельзя было знать, понимал он или нет то, что его окружало. Одно можно было знать наверное – это то, что он страдал и, чувствовал потребность еще выразить что то. Но что это было, никто не мог понять; был ли это какой нибудь каприз больного и полусумасшедшего, относилось ли это до общего хода дел, или относилось это до семейных обстоятельств?
Доктор говорил, что выражаемое им беспокойство ничего не значило, что оно имело физические причины; но княжна Марья думала (и то, что ее присутствие всегда усиливало его беспокойство, подтверждало ее предположение), думала, что он что то хотел сказать ей. Он, очевидно, страдал и физически и нравственно.
Надежды на исцеление не было. Везти его было нельзя. И что бы было, ежели бы он умер дорогой? «Не лучше ли бы было конец, совсем конец! – иногда думала княжна Марья. Она день и ночь, почти без сна, следила за ним, и, страшно сказать, она часто следила за ним не с надеждой найти призкаки облегчения, но следила, часто желая найти признаки приближения к концу.
Как ни странно было княжне сознавать в себе это чувство, но оно было в ней. И что было еще ужаснее для княжны Марьи, это было то, что со времени болезни ее отца (даже едва ли не раньше, не тогда ли уж, когда она, ожидая чего то, осталась с ним) в ней проснулись все заснувшие в ней, забытые личные желания и надежды. То, что годами не приходило ей в голову – мысли о свободной жизни без вечного страха отца, даже мысли о возможности любви и семейного счастия, как искушения дьявола, беспрестанно носились в ее воображении. Как ни отстраняла она от себя, беспрестанно ей приходили в голову вопросы о том, как она теперь, после того, устроит свою жизнь. Это были искушения дьявола, и княжна Марья знала это. Она знала, что единственное орудие против него была молитва, и она пыталась молиться. Она становилась в положение молитвы, смотрела на образа, читала слова молитвы, но не могла молиться. Она чувствовала, что теперь ее охватил другой мир – житейской, трудной и свободной деятельности, совершенно противоположный тому нравственному миру, в который она была заключена прежде и в котором лучшее утешение была молитва. Она не могла молиться и не могла плакать, и житейская забота охватила ее.