Линейное программирование

Поделись знанием:
(перенаправлено с «ЗЛП»)
Перейти к: навигация, поиск

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах <math>n</math>-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Линейное программирование (ЛП) является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.

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





История

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

Развитие экономики потребовало количественных показателей, и в 1920 годы был создан межотраслевой баланс (МОБ). Он-то и послужил толчком в деле создания и исследования математических моделей. Разработка МОБ в 19241925 годах в СССР повлияла на работы экономиста и статистика Василия Васильевича Леонтьева. Он разработал межотраслевую модель производства и распределения продукции.

В 1938 году Леонид Витальевич Канторович в порядке научной консультации приступил к изучению чисто практической задачи по составлению наилучшего плана загрузки лущильных станков (фанерный трест). Эта задача не поддавалась обычным методам. Стало ясно, что задача не случайная.[1]

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

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

В 1949 году американский математик Джордж Бернард Данциг разработал эффективный метод решения задач линейного программирования (ЗЛП) — симплекс-метод.[1]

Термин «программирование» нужно понимать в смысле «планирования» (один из переводов англ. programming). Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году.[2]

Задачи

Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида[3]:

<math>f(x)=\sum_{j=1}^n c_jx_j=c_1x_1+c_2x_2+\ldots+c_nx_n</math>

Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)

<math>\sum_{j=1}^n a_{ij}x_j\geqslant b_i\quad (i=1,\;2,\;\ldots,\;m)</math>,
<math>x_j\geqslant 0\quad (j=1,\;2,\;\ldots,\;n)</math>.

Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства[4]:

<math>\sum_{j=1}^n a_{ij}x_j = b_i\quad (i=1,\;2,\;\ldots,\;m)</math>,

Основную задачу можно свести к канонической путём введения дополнительных переменных.

Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств[5].

Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты <math>c</math> с обратным знаком.

Примеры задач

Максимальное паросочетание

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

Введём переменные <math>x_{ij}</math>, которые соответствуют паре из <math>i</math>-того юноши и <math>j</math>-той девушки и удовлетворяют ограничениям:

<math>0\leqslant x_{ij}\leqslant 1,</math>
<math>x_{1i}+x_{2i}+\ldots+x_{ni}\leqslant 1,</math>
<math>x_{i1}+x_{i2}+\ldots+x_{im}\leqslant 1,</math>

с целевой функцией <math>f=x_{11}+x_{12}+\ldots+x_{nm}</math>. Можно показать, что среди оптимальных решений этой задачи найдётся целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

Максимальный поток

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

Возьмём в качестве переменных <math>x_i</math> — количество жидкости, протекающей через <math>i</math>-тое ребро. Тогда

<math>0\leqslant x_i\leqslant c_i</math>,

где <math>c_i</math> — пропускная способность <math>i</math>-того ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции <math>f</math> естественно взять разность между количеством вытекающей и втекающей жидкости в истоке.

Обобщение предыдущей задачи — максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к двум задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение <math>f(x)\geqslant m</math>, где <math>m</math> — величина максимального потока, и решить задачу с новой функцией <math>f(x)</math> — стоимостью потока.

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

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

Имеется некий однородный груз, который нужно перевезти с <math>n</math> складов на <math>m</math> заводов. Для каждого склада <math>i</math> известно, сколько в нём находится груза <math>a_i</math>, а для каждого завода известна его потребность <math>b_j</math> в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния <math>c_{ij}</math> от <math>i</math>-го склада до <math>j</math>-го завода известны). Требуется составить наиболее дешёвый план перевозки.

Решающими переменными в данном случае являются <math>x_{ij}</math> — количества груза, перевезённого из <math>i</math>-го склада на <math>j</math>-й завод. Они удовлетворяют ограничениям:

<math>x_{i1}+x_{i2}+\ldots+x_{im}\leqslant a_i,</math>
<math>x_{1j}+x_{2j}+\ldots+x_{nj}\geqslant b_j.</math>

Целевая функция имеет вид: <math>f(x)=x_{11}c_{11}+x_{12}c_{12}+\ldots+x_{nm}c_{nm}</math>, которую надо минимизировать.

Игра с нулевой суммой

Есть матрица <math>A</math> размера <math>n\times m</math>. Первый игрок выбирает число от 1 до <math>n</math>, второй — от 1 до <math>m</math>. Затем они сверяют числа и первый игрок получает <math>a_{ij}</math> очков, а второй <math>(-a_{ij})</math> очков (<math>i</math> — число, выбранное первым игроком, <math>j</math> — вторым). Нужно найти оптимальную стратегию первого игрока.

Пусть в оптимальной стратегии, например, первого игрока число <math>i</math> нужно выбирать с вероятностью <math>p_i</math>. Тогда оптимальная стратегия является решением следующей задачи линейного программирования:

<math>0\leqslant p_i\leqslant 1</math>,
<math>p_1+\ldots+p_n=1</math>,
<math>a_{1i}p_1+a_{2i}p_2+\ldots+a_{ni}p_n\geqslant c</math> (<math>i=1,\;\ldots,\;m</math>),

в которой нужно максимизировать функцию <math>f(p_1,\;\ldots,\;p_n,\;c)=c</math>. Значение <math>c</math> в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

Алгоритмы решения

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

Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 году советским математиком Л. Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, нежели симплекс-метод, некомбинаторную природу. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП — методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).

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

Каждой задаче линейного программирования[6] вида

<math>\sum_{j=1}^n a_{ij} x_j \leq c_i, i=1,m; </math> <math>x_j \geq 0, j=1,n; </math> <math>F(x) = \sum_{j=1}^n b_j x_j \to \max </math>

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

Исходная задача Двойственная задача
<math> \sum_{j=1}^n a_{ij} x_j \leq c_i, i=1,m</math> <math>y_i \geq 0, i=1,m</math>
<math>x_j \geq 0, j=1,n</math> <math> \sum_{i=1}^m a_{ij} y_i \geq b_j, j=1,n</math>
<math>F(x) = \sum_{j=1}^n b_j x_j \to \max</math> <math>T(y) = \sum_{i=1}^m c_i y_i \to \min</math>

Если вектора <math>x</math> и <math>y</math> - допустимые решения прямой и двойственной задачи, то <math>F(x)\leq T(y)</math>, причем равенство достигается тогда и только тогда, когда <math>x</math> и <math>y</math> - оптимальные решения. Если же целевая функция одной из пары двойственных задач не ограничена (для исходной – сверху, для двойственной – снизу), то область допустимых решений другой задачи - пустая.

Если вектора <math>x^*</math> и <math>y^*</math> - оптимальные решения прямой и двойственной задачи, соответственно, то верны следующие равенства

<math> x_j^* ( \sum_{i=1}^m a_{ij} y_i^* - b_j ) = 0, j = 1, n; </math>

<math> y_i^* ( \sum_{j=1}^n a_{ij} x_j^* - c_i ) = 0, i = 1, m. </math>

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

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

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

lp_solve - открытое программное обеспечение (лицензия LGPL GNU Стандартная общественная лицензия GNU для библиотек) для решения линейных уравнений. LpSolve имеет IDE, собственный C API, и множество других программных интерфейсов для JAVA, AMPL, MATLAB, O-Matrix, Sysquake, Scilab, Octave, FreeMat, Euler, Python, Sage, PHP, R и Microsoft Solver Foundation.

См. также

Напишите отзыв о статье "Линейное программирование"

Примечания

  1. 1 2 Источник: [elib.altstu.ru Алтайская краевая универсальная научная библиотека им. В. Я. Шишкова (АКУНБ)]. Методы оптимизации: Учеб. пособие. Бразовская Н. В.; Алтайский государственный технический университет им. И. И. Ползунова, [Центр дистанц. обучения]. — Барнаул: Изд-во АлтГТУ, 2000. — 120 с. — ISBN 5-БНВ-МОр.9.00 — УДК/ББК 22.183.4 Б871.
  2. Дикин И. И. Итеративное решение задач линейного и квадратичного программирования // Докл. АН СССР. — 1967. — Т. 174, № 4. — С. 747-748.
  3. Карманов, 1986, с. 63.
  4. Карманов, 1986, с. 80.
  5. Карманов, 1986, с. 77.
  6. Электронный учебник [www.math.mrsu.ru/text/courses/method/dvoistvennost_v_lineinom_programmirovanii.htm "Экономико-математические методы". Двойственность в линейном программировании]

Литература

  • Абрамов Л. М., Капустин В.Ф. Математическое программирование. — Учебное пособие. — Л.: ЛГУ, 1981. — 328 с.
  • Акоф Р., Сасиени М. Основы исследования операций. — Пер.с англ. В.Я.Алтаева. под ред. И.А.Ушакова. — М.: Мир, 1971. — 551 с.
  • Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9.
  • Астафьев Н.Н. Бесконечные системы линейных неравенств в математическом программировании. — М.: Наука, 1991. — 134 с.
  • Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. — М.: Наука, 1991. — 446 с.
  • Гасс С. Линейное программирование. — М.: Физико-математическая литература, 1961. — 300 с.
  • Давыдов Э.Г. Исследование операций. — М.: Высшая школа, 1990. — 382 с.
  • Дегтярёв Ю.И. Исследование операций. — Учебник для вузов. — М.: Высшая школа, 1986. — 320 с.
  • Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. — М.: Наука, 1966. — 348 с.
  • Карманов В. Г. Математическое программирование. — 3-е издание. — М.: Наука, 1986. — 288 с.
  • Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. — Минск.: Вышейшая школа, 1994. — 286 с.
  • Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4.
  • Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. — М.: Наука, 1969. — 424 с.
  • Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

Ссылки

  • [sourceforge.net/projects/lipside/ Linear Program Solver (LiPS)] — Бесплатный оптимизационный пакет, предназначенный для решения задач линейного, целочисленного и целевого программирования.
  • Вершик А. М. «[www.mmonline.ru/articles/1893/ O Л. В. Канторовиче и линейном программировании]»
  • [web.archive.org/web/20070205063920/dims.karelia.ru/~alexmou/tpr/tpr_02_linear_programming.ppt Слайды по линейному программированию]
  • Большакова И. В., Кураленко М. В. «[www.economy.bsu.by/library/Большакова_Линейное_программирование.htm Линейное программирование. Учебно-методическое пособие к контрольной работе] (недоступная ссылка с 13-05-2013 (3973 дня))».
  • Барсов А. С. «[ilib.mirror1.mccme.ru/plm/ann/a33.htm Что такое линейное программирование]», Популярные лекции по математике, Гостехиздат, 1959.
  • М. Н. Вялый. [www.mccme.ru/dubna/2001/material/vyalyi.pdf Линейные неравенства и комбинаторика]. — МЦНМО, 2003.

Отрывок, характеризующий Линейное программирование

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


Ростов своим зорким охотничьим глазом один из первых увидал этих синих французских драгун, преследующих наших улан. Ближе, ближе подвигались расстроенными толпами уланы, и французские драгуны, преследующие их. Уже можно было видеть, как эти, казавшиеся под горой маленькими, люди сталкивались, нагоняли друг друга и махали руками или саблями.
Ростов, как на травлю, смотрел на то, что делалось перед ним. Он чутьем чувствовал, что ежели ударить теперь с гусарами на французских драгун, они не устоят; но ежели ударить, то надо было сейчас, сию минуту, иначе будет уже поздно. Он оглянулся вокруг себя. Ротмистр, стоя подле него, точно так же не спускал глаз с кавалерии внизу.
– Андрей Севастьяныч, – сказал Ростов, – ведь мы их сомнем…
– Лихая бы штука, – сказал ротмистр, – а в самом деле…
Ростов, не дослушав его, толкнул лошадь, выскакал вперед эскадрона, и не успел он еще скомандовать движение, как весь эскадрон, испытывавший то же, что и он, тронулся за ним. Ростов сам не знал, как и почему он это сделал. Все это он сделал, как он делал на охоте, не думая, не соображая. Он видел, что драгуны близко, что они скачут, расстроены; он знал, что они не выдержат, он знал, что была только одна минута, которая не воротится, ежели он упустит ее. Пули так возбудительно визжали и свистели вокруг него, лошадь так горячо просилась вперед, что он не мог выдержать. Он тронул лошадь, скомандовал и в то же мгновение, услыхав за собой звук топота своего развернутого эскадрона, на полных рысях, стал спускаться к драгунам под гору. Едва они сошли под гору, как невольно их аллюр рыси перешел в галоп, становившийся все быстрее и быстрее по мере того, как они приближались к своим уланам и скакавшим за ними французским драгунам. Драгуны были близко. Передние, увидав гусар, стали поворачивать назад, задние приостанавливаться. С чувством, с которым он несся наперерез волку, Ростов, выпустив во весь мах своего донца, скакал наперерез расстроенным рядам французских драгун. Один улан остановился, один пеший припал к земле, чтобы его не раздавили, одна лошадь без седока замешалась с гусарами. Почти все французские драгуны скакали назад. Ростов, выбрав себе одного из них на серой лошади, пустился за ним. По дороге он налетел на куст; добрая лошадь перенесла его через него, и, едва справясь на седле, Николай увидал, что он через несколько мгновений догонит того неприятеля, которого он выбрал своей целью. Француз этот, вероятно, офицер – по его мундиру, согнувшись, скакал на своей серой лошади, саблей подгоняя ее. Через мгновенье лошадь Ростова ударила грудью в зад лошади офицера, чуть не сбила ее с ног, и в то же мгновенье Ростов, сам не зная зачем, поднял саблю и ударил ею по французу.
В то же мгновение, как он сделал это, все оживление Ростова вдруг исчезло. Офицер упал не столько от удара саблей, который только слегка разрезал ему руку выше локтя, сколько от толчка лошади и от страха. Ростов, сдержав лошадь, отыскивал глазами своего врага, чтобы увидать, кого он победил. Драгунский французский офицер одной ногой прыгал на земле, другой зацепился в стремени. Он, испуганно щурясь, как будто ожидая всякую секунду нового удара, сморщившись, с выражением ужаса взглянул снизу вверх на Ростова. Лицо его, бледное и забрызганное грязью, белокурое, молодое, с дырочкой на подбородке и светлыми голубыми глазами, было самое не для поля сражения, не вражеское лицо, а самое простое комнатное лицо. Еще прежде, чем Ростов решил, что он с ним будет делать, офицер закричал: «Je me rends!» [Сдаюсь!] Он, торопясь, хотел и не мог выпутать из стремени ногу и, не спуская испуганных голубых глаз, смотрел на Ростова. Подскочившие гусары выпростали ему ногу и посадили его на седло. Гусары с разных сторон возились с драгунами: один был ранен, но, с лицом в крови, не давал своей лошади; другой, обняв гусара, сидел на крупе его лошади; третий взлеаал, поддерживаемый гусаром, на его лошадь. Впереди бежала, стреляя, французская пехота. Гусары торопливо поскакали назад с своими пленными. Ростов скакал назад с другими, испытывая какое то неприятное чувство, сжимавшее ему сердце. Что то неясное, запутанное, чего он никак не мог объяснить себе, открылось ему взятием в плен этого офицера и тем ударом, который он нанес ему.
Граф Остерман Толстой встретил возвращавшихся гусар, подозвал Ростова, благодарил его и сказал, что он представит государю о его молодецком поступке и будет просить для него Георгиевский крест. Когда Ростова потребовали к графу Остерману, он, вспомнив о том, что атака его была начата без приказанья, был вполне убежден, что начальник требует его для того, чтобы наказать его за самовольный поступок. Поэтому лестные слова Остермана и обещание награды должны бы были тем радостнее поразить Ростова; но все то же неприятное, неясное чувство нравственно тошнило ему. «Да что бишь меня мучает? – спросил он себя, отъезжая от генерала. – Ильин? Нет, он цел. Осрамился я чем нибудь? Нет. Все не то! – Что то другое мучило его, как раскаяние. – Да, да, этот французский офицер с дырочкой. И я хорошо помню, как рука моя остановилась, когда я поднял ее».
Ростов увидал отвозимых пленных и поскакал за ними, чтобы посмотреть своего француза с дырочкой на подбородке. Он в своем странном мундире сидел на заводной гусарской лошади и беспокойно оглядывался вокруг себя. Рана его на руке была почти не рана. Он притворно улыбнулся Ростову и помахал ему рукой, в виде приветствия. Ростову все так же было неловко и чего то совестно.
Весь этот и следующий день друзья и товарищи Ростова замечали, что он не скучен, не сердит, но молчалив, задумчив и сосредоточен. Он неохотно пил, старался оставаться один и о чем то все думал.
Ростов все думал об этом своем блестящем подвиге, который, к удивлению его, приобрел ему Георгиевский крест и даже сделал ему репутацию храбреца, – и никак не мог понять чего то. «Так и они еще больше нашего боятся! – думал он. – Так только то и есть всего, то, что называется геройством? И разве я это делал для отечества? И в чем он виноват с своей дырочкой и голубыми глазами? А как он испугался! Он думал, что я убью его. За что ж мне убивать его? У меня рука дрогнула. А мне дали Георгиевский крест. Ничего, ничего не понимаю!»
Но пока Николай перерабатывал в себе эти вопросы и все таки не дал себе ясного отчета в том, что так смутило его, колесо счастья по службе, как это часто бывает, повернулось в его пользу. Его выдвинули вперед после Островненского дела, дали ему батальон гусаров и, когда нужно было употребить храброго офицера, давали ему поручения.


Получив известие о болезни Наташи, графиня, еще не совсем здоровая и слабая, с Петей и со всем домом приехала в Москву, и все семейство Ростовых перебралось от Марьи Дмитриевны в свой дом и совсем поселилось в Москве.
Болезнь Наташи была так серьезна, что, к счастию ее и к счастию родных, мысль о всем том, что было причиной ее болезни, ее поступок и разрыв с женихом перешли на второй план. Она была так больна, что нельзя было думать о том, насколько она была виновата во всем случившемся, тогда как она не ела, не спала, заметно худела, кашляла и была, как давали чувствовать доктора, в опасности. Надо было думать только о том, чтобы помочь ей. Доктора ездили к Наташе и отдельно и консилиумами, говорили много по французски, по немецки и по латыни, осуждали один другого, прописывали самые разнообразные лекарства от всех им известных болезней; но ни одному из них не приходила в голову та простая мысль, что им не может быть известна та болезнь, которой страдала Наташа, как не может быть известна ни одна болезнь, которой одержим живой человек: ибо каждый живой человек имеет свои особенности и всегда имеет особенную и свою новую, сложную, неизвестную медицине болезнь, не болезнь легких, печени, кожи, сердца, нервов и т. д., записанных в медицине, но болезнь, состоящую из одного из бесчисленных соединений в страданиях этих органов. Эта простая мысль не могла приходить докторам (так же, как не может прийти колдуну мысль, что он не может колдовать) потому, что их дело жизни состояло в том, чтобы лечить, потому, что за то они получали деньги, и потому, что на это дело они потратили лучшие годы своей жизни. Но главное – мысль эта не могла прийти докторам потому, что они видели, что они несомненно полезны, и были действительно полезны для всех домашних Ростовых. Они были полезны не потому, что заставляли проглатывать больную большей частью вредные вещества (вред этот был мало чувствителен, потому что вредные вещества давались в малом количестве), но они полезны, необходимы, неизбежны были (причина – почему всегда есть и будут мнимые излечители, ворожеи, гомеопаты и аллопаты) потому, что они удовлетворяли нравственной потребности больной и людей, любящих больную. Они удовлетворяли той вечной человеческой потребности надежды на облегчение, потребности сочувствия и деятельности, которые испытывает человек во время страдания. Они удовлетворяли той вечной, человеческой – заметной в ребенке в самой первобытной форме – потребности потереть то место, которое ушиблено. Ребенок убьется и тотчас же бежит в руки матери, няньки для того, чтобы ему поцеловали и потерли больное место, и ему делается легче, когда больное место потрут или поцелуют. Ребенок не верит, чтобы у сильнейших и мудрейших его не было средств помочь его боли. И надежда на облегчение и выражение сочувствия в то время, как мать трет его шишку, утешают его. Доктора для Наташи были полезны тем, что они целовали и терли бобо, уверяя, что сейчас пройдет, ежели кучер съездит в арбатскую аптеку и возьмет на рубль семь гривен порошков и пилюль в хорошенькой коробочке и ежели порошки эти непременно через два часа, никак не больше и не меньше, будет в отварной воде принимать больная.
Что же бы делали Соня, граф и графиня, как бы они смотрели на слабую, тающую Наташу, ничего не предпринимая, ежели бы не было этих пилюль по часам, питья тепленького, куриной котлетки и всех подробностей жизни, предписанных доктором, соблюдать которые составляло занятие и утешение для окружающих? Чем строже и сложнее были эти правила, тем утешительнее было для окружающих дело. Как бы переносил граф болезнь своей любимой дочери, ежели бы он не знал, что ему стоила тысячи рублей болезнь Наташи и что он не пожалеет еще тысяч, чтобы сделать ей пользу: ежели бы он не знал, что, ежели она не поправится, он не пожалеет еще тысяч и повезет ее за границу и там сделает консилиумы; ежели бы он не имел возможности рассказывать подробности о том, как Метивье и Феллер не поняли, а Фриз понял, и Мудров еще лучше определил болезнь? Что бы делала графиня, ежели бы она не могла иногда ссориться с больной Наташей за то, что она не вполне соблюдает предписаний доктора?