Полное руководство по решению контрольной работы по математическим методам в экономике: от теории до верификации

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

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

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

Прямая и двойственная задачи линейного программирования — это две стороны одной медали, две взаимосвязанные перспективы взгляда на одну и ту же экономическую проблему. Их тесная связь позволяет не только проверить корректность полученных решений, но и получить глубокое экономическое понимание процессов. Например, если прямая задача ставит целью максимизировать прибыль от производства продукции, используя ограниченные ресурсы, то двойственная задача естественным образом стремится минимизировать общую оценку этих ресурсов, или, как говорят экономисты, «теневые цены» этих ресурсов. А что это значит на практике? Это позволяет бизнесу не просто распределить ресурсы, но и понять их истинную ценность в контексте производственных ограничений, что критически важно для стратегического планирования и инвестиций.

Постановка прямой и двойственной задачи

Чтобы приступить к решению, необходимо чётко сформулировать прямую задачу. Пусть, например, предприятие стремится максимизировать свою прибыль от производства n видов продукции при наличии m видов ограниченных ресурсов.

Прямая задача (пример — задача максимизации):

Целевая функция:

Z = c1x1 + c2x2 + ... + cnxn → max

Ограничения:

a11x1 + a12x2 + ... + a1nxn ≤ b1
a21x1 + a22x2 + ... + a2nxn ≤ b2
...
am1x1 + am2x2 + ... + amnxn ≤ bm

Неотрицательность переменных:

xj ≥ 0 для всех j = 1, ..., n

Здесь:

• x_j — количество j-го вида продукции.
• c_j — прибыль от реализации единицы j-го вида продукции.
• b_i — объем i-го вида ресурса.
• a_ij — количество i-го ресурса, необходимое для производства единицы j-го вида продукции.

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

1. Количество переменных и ограничений: Число переменных в двойственной задаче (y_i) равно числу функциональных ограничений в прямой задаче (m), а число функциональных ограничений в двойственной задаче равно числу переменных в прямой задаче (n).
2. Тип задачи: Если прямая задача — это задача максимизации, то двойственная — задача минимизации, и наоборот.
3. Коэффициенты целевой функции: Свободные члены ограничений прямой задачи (b_i) становятся коэффициентами целевой функции двойственной задачи.
4. Правые части ограничений: Коэффициенты целевой функции прямой задачи (c_j) становятся правыми частями ограничений двойственной задачи.
5. Матрица коэффициентов: Матрица коэффициентов при переменных в ограничениях двойственной задачи получается транспонированием матрицы коэффициентов прямой задачи (a_ij становится a_ji).
6. Знаки неравенств: Если в прямой задаче ограничения были вида «≤», то в двойственной они станут «≥», и наоборот. Если ограничение в прямой задаче было равенством, соответствующая двойственная переменная будет без знака (неограниченной).
7. Неотрицательность переменных: Если переменные прямой задачи были неотрицательны, то ограничения двойственной задачи будут неравенствами. Если переменная прямой задачи была без знака, соответствующее ограничение двойственной задачи будет равенством. Для симметричной формы, как в нашем примере, все двойственные переменные неотрицательны (y_i ≥ 0).

Пример построения двойственной задачи:

Пусть прямая задача:

Z = 5x1 + 3x2 → max

При ограничениях:

2x1 + x2 ≤ 10
x1 + 3x2 ≤ 15
x1, x2 ≥ 0

Тогда двойственная задача будет:

F = 10y1 + 15y2 → min

При ограничениях:

2y1 + y2 ≥ 5
y1 + 3y2 ≥ 3
y1, y2 ≥ 0

Теоремы двойственности и их практическое значение

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

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

  Математическое значение: Эта теорема говорит о том, что F(Y) ≥ Z(X) для любых допустимых X и Y, если прямая задача на максимизацию. Это полезно для проверки корректности промежуточных решений: если на каком-то этапе мы получаем Z > F, то это явный признак ошибки.

• Теорема о сильной двойственности: Если прямая задача имеет оптимальное решение, то двойственная задача также имеет оптимальное решение, и их оптимальные значения равны: Z^* = F^*.
  

  Математическое значение: Это ключевая теорема, которая гарантирует, что поиск оптимума одной задачи эквивалентен поиску оптимума другой. Она позволяет находить оптимальный план одной задачи, решая другую, что часто упрощает вычисления.

• Дополнительные следствия:
  • Если линейная функция одной из задач неограничена (например, Z → ∞), то другая задача не имеет допустимого решения (нет ни одного вектора, удовлетворяющего её ограничениям).
  • Если одна из задач не имеет допустимого решения, то другая задача либо не имеет допустимого решения, либо её целевая функция неограничена.

Практическое значение этих теорем неоценимо. Они позволяют:

1. Проверять решения: Зная, что Z^* = F^*, можно проверить, правильно ли найдены оптимальные планы обеих задач.
2. Эффективно решать задачи: В некоторых случаях одна из задач (например, двойственная) может оказаться существенно проще для решения (меньше ограничений или переменных), чем прямая. Решив её, мы сразу получаем информацию об оптимальном значении целевой функции для исходной задачи.
3. Использовать условия дополняющей нежесткости: Оптимальный план двойственной задачи может быть найден непосредственно из последней симплексной таблицы исходной задачи. Это значительно упрощает поиск Y^*, если X^* уже известен.

Экономическая интерпретация двойственных оценок (теневых цен)

Двойственные оценки, или теневые цены (y_i^*), представляют собой один из наиболее мощных инструментов экономического анализа, вытекающих из теории двойственности. Они являются не просто математическими значениями, а отражают глубокий экономический смысл ресурсов и ограничений.

Что такое теневая цена?

Теневая цена ресурса (y_i^*) — это прирост (или убыток) оптимального значения целевой функции (например, прибыли) при увеличении (или уменьшении) на одну единицу объёма i-го ресурса, при условии, что все остальные параметры остаются неизменными и структура оптимального плана не меняется.

Глубокое раскрытие экономического смысла:

1. Ценность ограниченных ресурсов: Теневая цена показывает, насколько ценен каждый дополнительный килограмм сырья, час работы оборудования или единица трудозатрат в условиях дефицита. Если y_i^* > 0, это означает, что i-й ресурс используется полностью (является «дефицитным» или «связывающим» ограничением), и его дополнительная единица могла бы увеличить общую прибыль.
2. Принятие управленческих решений:
   • Закупка ресурсов: Если рыночная цена дополнительной единицы ресурса меньше его теневой цены (т.е. P_{рыночная} < y_i^*), то компании выгодно приобрести этот ресурс, так как он принесёт больше прибыли, чем будут стоить затраты на его покупку.
   • Обоснование инвестиций: Теневые цены могут служить ориентиром для инвестиций в увеличение производственных мощностей или запасов сырья. Инвестировать следует в те ресурсы, которые имеют наибольшие положительные теневые цены.
   • Ценообразование: В условиях внутренних расчётов между подразделениями компании, теневые цены могут использоваться для справедливой оценки стоимости ресурсов, передаваемых от одного подразделения к другому.
3. Идентификация «узких мест»: Ресурсы с положительными теневыми ценами являются «узкими местами» производства. Их нехватка ограничивает максимизацию прибыли. Устранение этих узких мест (например, закупка дополнительного сырья, расширение цеха) должно быть приоритетом.
4. Динамика теневых цен: Важно понимать, что теневые цены не являются статичными. Они действительны только в определённом диапазоне изменения ресурса, внутри которого структура оптимального плана остаётся неизменной. При существенном изменении объёма ресурса оптимальный план может измениться, и теневая цена также изменится.
5. Нулевые теневые цены: Если теневая цена y_i^* = 0, это означает, что i-й ресурс не является дефицитным, то есть его запас не используется полностью в оптимальном плане (есть «излишек»). Дополнительная единица такого ресурса не принесёт прироста прибыли, поскольку его уже достаточно.

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

Графический метод решения задач линейного программирования

Графический метод — это наглядный и интуитивно понятный способ решения задач линейного программирования, который идеально подходит для задач с двумя переменными. Его красота заключается в том, что он позволяет «увидеть» процесс оптимизации, понять геометрию области допустимых решений и логику поиска оптимума.

Алгоритм построения и анализа области допустимых решений

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

Пошаговое построение:

1. Построение граничных линий: Каждое ограничение-неравенство (например, a_ijx_j ≤ b_i) временно превращается в равенство (a_ijx_j = b_i) и строится соответствующая прямая на координатной плоскости (x₁, x₂).
   • Для этого достаточно найти две точки, удовлетворяющие уравнению (например, точки пересечения с осями координат).
2. Определение полуплоскостей: Для каждого ограничения-неравенства необходимо определить, какая из двух полуплоскостей, на которые прямая делит плоскость, удовлетворяет неравенству.
   • Обычно для этого выбирают «пробную» точку, не лежащую на прямой (чаще всего начало координат (0,0), если оно не лежит на самой прямой). Если координаты этой точки удовлетворяют неравенству, то нужная полуплоскость содержит эту точку. Если нет, то нужная полуплоскость — противоположная.
   • Ограничения на неотрицательность переменных (x₁ ≥ 0, x₂ ≥ 0) означают, что область допустимых решений будет находиться только в первом квадранте.
3. Формирование области допустимых решений (ОДР): ОДР, или многогранник решений (многоугольник решений в двухмерном случае), это пересечение всех полуплоскостей, определённых ограничениями. Это выпуклый многогранник (если задача имеет решение).
4. Построение линии уровня целевой функции (изолинии): Целевая функция Z = c₁x₁ + c₂x₂ приравнивается к некоторому произвольному значению (например, Z = 0) для построения начальной изолинии.
   • Например, 5x₁ + 3x₂ = 0.
5. Определение направления градиента целевой функции: Для определения направления возрастания целевой функции (для максимизации) или убывания (для минимизации) строится вектор градиента C = (c₁, c₂). Этот вектор перпендикулярен линии уровня и указывает направление, в котором значение целевой функции увеличивается.
   • Например, для Z = 5x₁ + 3x₂ вектор C = (5, 3).

Нахождение оптимального решения и особые случаи

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

Определение оптимальной вершины:

1. Перемещение изолинии: Перемещайте линию уровня целевой функции параллельно самой себе в направлении вектора C (для максимизации) или в противоположном направлении (для минимизации) до тех пор, пока она не коснётся крайней точки многоугольника решений.
2. Идентификация оптимальной точки:
   • Единственная вершина: Чаще всего, линия уровня коснётся ОДР в одной единственной вершине. Это и есть оптимальное решение. Координаты этой вершины определяются как решение системы уравнений прямых, образующих эту вершину.
   • Целое ребро: Если линия уровня параллельна одному из рёбер ОДР и это ребро является «крайним» в направлении оптимизации, то оптимальное решение будет достигаться в любой точке этого ребра, включая его концевые вершины. Это означает, что задача имеет альтернативные опорные планы (множество оптимальных решений) с одинаковым значением целевой функции.

Возможные результаты графического метода (особые случаи):

• Несовместность системы ограничений: Область допустимых решений пуста. Это означает, что не существует ни одной точки, которая удовлетворяла бы всем ограничениям одновременно. На графике это проявляется в том, что все полуплоскости не пересекаются или пересекаются таким образом, что не образуют замкнутой области. В таком случае задача не имеет допустимых планов, а значит, и оптимального решения.
• Неограниченность целевой функции: Область допустимых решений является неограниченной в направлении оптимизации. На графике это означает, что линия уровня целевой функции может быть бесконечно сдвинута в направлении вектора C (для максимизации) или против него (для минимизации), при этом постоянно оставаясь в пределах ОДР. В этом случае целевая функция может принимать сколь угодно большие (для максимизации) или сколь угодно малые (для минимизации) значения, и задача не имеет конечного оптимального решения.
• Вырожденность: В некоторых случаях оптимальное решение может быть в вершине, где пересекаются более двух граничных линий. Это не всегда очевидно на графике, но может указывать на вырожденность в симплекс-таблице.

Ограничения и применимость метода

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

1. Количество переменных: Главное ограничение — метод эффективно применим только для задач с двумя переменными.
   • Для задач с тремя переменными (x₁, x₂, x₃) теоретически возможно построить область допустимых решений в трехмерном пространстве в виде многогранника. Линия уровня целевой функции при этом становится плоскостью. Однако визуализация, построение и поиск оптимальной вершины в 3D-пространстве сопряжены со значительными трудностями, потерей наглядности и точности. Построить такой многогранник и правильно определить его крайние точки вручную крайне сложно, а иногда и невозможно без специальных программных средств.
   • Для задач с четырьмя и более переменными графический метод становится абсолютно неприменим, поскольку мы не можем визуализировать гиперплоскости и многомерные многогранники.
2. Точность: При ручном построении всегда есть риск погрешностей, особенно при определении координат вершин.
3. Сложность ограничений: Если ограничения имеют сложную структуру (например, много пересекающихся прямых), графическое построение становится громоздким.

Применимость метода:

Графический метод идеален для:

• Обучения и понимания базовых принципов линейного программирования.
• Быстрой проверки результатов, полученных аналитическими методами, для задач с двумя переменными.
• Иллюстрации различных случаев (альтернативный оптимум, неограниченность, несовместность).

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

Симплекс-метод и его модификации: Универсальный инструмент оптимизации

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

Классический симплекс-метод: Алгоритм и применение

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

Приведение задачи к каноническому виду:

Канонический вид ЗЛП требует:

1. Целевая функция: Всегда максимизируется (если исходная задача минимизации, целевая функция F → min, её можно перевести в максимизацию, умножив на -1: Z = -F → max).
2. Ограничения: Все функциональные ограничения должны быть представлены в виде равенств. Это достигается путём введения:
   • Балансовых (дополнительных) переменных: Если ограничение типа «≤», то в левую часть добавляется неотрицательная переменная (например, s_i ≥ 0). Она превращает неравенство в равенство, поглощая «излишек» правой части. Пример: 2x1 + x2 ≤ 10 становится 2x1 + x2 + s1 = 10.
   • Избыточных переменных: Если ограничение типа «≥», то из левой части вычитается неотрицательная переменная (например, s_i ≥ 0). Пример: 2x1 + x2 ≥ 10 становится 2x1 + x2 - s1 = 10.
3. Неотрицательность переменных: Все переменные (включая балансовые/избыточные) должны быть неотрицательными (x_j ≥ 0, s_i ≥ 0).
4. Базис: В каждом ограничении-равенстве должна присутствовать одна переменная, которая входит в это уравнение с коэффициентом 1 и отсутствует во всех других уравнениях системы (единичный вектор). Эти переменные образуют базис и формируют начальный опорный план.

Алгоритм симплекс-метода:

1. Формирование начальной симплекс-таблицы: В таблицу заносятся коэффициенты системы ограничений и целевой функции. Переменные делятся на базисные (образующие единичные векторы) и небазисные.
   • Строка целевой функции (z-строка) обычно представляется в виде: z - c1x1 - c2x2 - ... - cnxn = 0.

   Таблица имеет следующий вид:

   Базисные переменные	x1	x2	…	xn	s1	s2	…	sm	Свободные члены (bi)
   s1	a11	a12	…	a1n	1	0	…	0	b1
   s2	a21	a22	…	a2n	0	1	…	0	b2
   …	…	…	…	…	…	…	…	…	…
   sm	am1	am2	…	amn	0	0	…	1	bm
   Z (оценки)	-c1	-c2	…	-cn	0	0	…	0	0

2. Проверка текущего опорного плана на оптимальность:
   • Для задачи максимизации: план оптимален, если все оценки (коэффициенты в строке Z для небазисных переменных) неотрицательны (z_j — c_j ≥ 0).
   • Для задачи минимизации (если она не была преобразована в максимизацию): план оптимален, если все оценки неположительны (z_j — c_j ≤ 0).
   • Если условие оптимальности не выполнено, переходим к следующему шагу.
3. Определение вводимой в базис переменной (ведущий столбец): Выбирается переменная с наибольшей по модулю отрицательной оценкой (для максимизации) или наибольшей положительной оценкой (для минимизации). Этот столбец называется ведущим.
4. Определение выводимой из базиса переменной (ведущая строка): Для каждого ограничения-строки вычисляется отношение свободного члена (b_i) к соответствующему положительному элементу ведущего столбца (a_ij > 0). Выбирается строка, для которой это отношение минимально. Эта строка называется ведущей. Если все элементы ведущего столбца неположительны, то целевая функция неограничена.
5. Ведущий элемент: Элемент на пересечении ведущей строки и ведущего столбца.
6. Переход к новому базисному решению (итерация): Выполняются элементарные преобразования симплекс-таблицы:
   • Ведущий элемент преобразуется в 1 путём деления всей ведущей строки на ведущий элемент.
   • Все остальные элементы ведущего столбца преобразуются в 0 путём вычитания ведущей строки, умноженной на соответствующий коэффициент, из других строк.
7. Повторение: Шаги 2-6 повторяются до тех пор, пока не будет найден оптимальный план.

Пример (продолжение):

Z = 5x1 + 3x2 → max

При ограничениях:

2x1 + x2 + s1 = 10
x1 + 3x2 + s2 = 15
x1, x2, s1, s2 ≥ 0

Начальная симплекс-таблица:

Базис	x1	x2	s1	s2	bi	Соотношение bi/ai1
s1	2	1	1	0	10	10/2 = 5
s2	1	3	0	1	15	15/1 = 15
Z	-5	-3	0	0	0

Вводимая переменная: x₁ (наибольшее отрицательное -5). Ведущий столбец 1.
Выводимая переменная: s₁ (минимальное отношение 5). Ведущая строка 1.
Ведущий элемент: a₁₁ = 2.
После преобразований получим новую таблицу, и так далее, пока все элементы в Z-строке не станут неотрицательными.

Метод искусственного базиса и двухфазный симплекс-метод

Метод искусственного базиса необходим, когда в исходной системе ограничений, приведённой к каноническому виду, отсутствуют единичные векторы для формирования начального базиса. Это типично для ограничений-равенств или неравенств типа «≥».

Применение искусственных переменных:

1. Введение искусственных переменных (A_i): В каждое ограничение, где нет базисной переменной (то есть нет единичного вектора), вводится новая неотрицательная искусственная переменная A_i ≥ 0 с коэффициентом +1. Эти переменные вместе с имеющимися базисными переменными формируют искусственный базис.
   • Пример: 2x1 + x2 - s1 = 10 становится 2x1 + x2 - s1 + A1 = 10.
2. «Штрафные» коэффициенты M: Чтобы гарантировать, что искусственные переменные выйдут из базиса в оптимальном решении (поскольку они не имеют физического смысла), их вводят в целевую функцию со «штрафными» коэффициентами:
   • Для задач максимизации: -M (где M — очень большое положительное число).
   • Для задач минимизации: +M.

   Например, если Z = c₁x₁ + c₂x₂ → max, то новая целевая функция будет Z’ = c₁x₁ + c₂x₂ — MA₁ — MA₂ — … → max.

Пошаговое решение с использованием «штрафных» коэффициентов M:

1. Привести задачу к каноническому виду, введя балансовые/избыточные переменные.
2. Ввести искусственные переменные в те ограничения, где нет базиса, и добавить их в целевую функцию со «штрафным» коэффициентом M.
3. Перед составлением начальной симплекс-таблицы, строка целевой функции должна быть преобразована так, чтобы искусственные переменные не входили в базис с коэффициентом M, то есть их коэффициенты в строке Z должны быть равны нулю. Это достигается вычитанием или прибавлением строк, содержащих искусственные переменные, из строки Z.
4. Применить стандартный симплекс-алгоритм. Если в оптимальном решении искусственные переменные остаются в базисе со значениями, отличными от нуля, это означает, что исходная задача не имеет допустимого решения. Если все искусственные переменные вышли из базиса или стали равны нулю, оптимальное решение найдено.

Двухфазный симплекс-метод:

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

• Фаза 1 (Поиск допустимого решения):
  1. Формируется вспомогательная целевая функция, которая представляет собой сумму всех искусственных переменных (W = A₁ + A₂ + … + A_k).
  2. Эта вспомогательная функция минимизируется.
  3. Если минимальное значение W^* = 0, и все искусственные переменные вышли из базиса (или стали равны нулю), это означает, что исходная задача имеет допустимое решение. Базис, полученный в конце Фазы 1, является допустимым для исходной задачи, и можно переходить ко второй фазе.
  4. Если W^* > 0, это означает, что исходная задача не имеет допустимого решения. Процесс останавливается.
• Фаза 2 (Поиск оптимального решения):
  1. Искусственные переменные и их столбцы полностью удаляются из симплекс-таблицы.
  2. Строка целевой функции исходной задачи (Z) восстанавливается с учётом базисных переменных, полученных в конце Фазы 1.
  3. Процесс симплекс-метода продолжается со стандартной целевой функцией Z, используя базис, полученный в Фазе 1, до нахождения оптимального решения исходной задачи.

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

Двойственный симплекс-метод: Решение задач с недопустимым, но оптимальным начальным планом

Двойственный симплекс-метод — это специализированный алгоритм, который применяется, когда начальный базисный план является оптимальным по критерию целевой функции, но недопустимым (то есть, некоторые правые части ограничений b_i < 0). Это часто возникает после добавления новых ограничений к уже решённой задаче или при работе с задачами минимизации, где легко получить оптимальную, но недопустимую стартовую таблицу.

Условия применения метода:

1. Оптимальность целевой функции: Все оценки в строке целевой функции (z_j — c_j) должны удовлетворять условию оптимальности:
   • Для задачи максимизации: все z_j — c_j ≥ 0.
   • Для задачи минимизации: все z_j — c_j ≤ 0.
2. Недопустимость плана: При этом, хотя бы один свободный член в ограничениях (b_i) должен быть отрицательным (b_i < 0).

Алгоритм двойственного симплекс-метода:

1. Выбор выводимой переменной (ведущая строка): Найти строку с наиболее отрицательным свободным членом (b_i). Это и будет ведущая строка. Если все b_i ≥ 0, то план допустим и оптимален, решение найдено.
2. Выбор вводимой переменной (ведущий столбец): Для всех элементов a_ij в ведущей строке, которые отрицательны (a_ij < 0), вычислить отношение (z_j — c_j) / a_ij.
   • Выбирается столбец j, для которого это отношение имеет минимальное значение по абсолютной величине (или наибольшее алгебраически, если все оценки z_j — c_j ≤ 0). Это будет ведущий столбец.
   • Если все элементы a_ij в ведущей строке неотрицательны, то исходная задача не имеет допустимого решения.
3. Ведущий элемент: Элемент на пересечении ведущей строки и ведущего столбца.
4. Преобразования симплекс-таблицы: Выполняются стандартные элементарные преобразования симплекс-таблицы, как и в классическом симплекс-методе (преобразование ведущего элемента в 1, а остальных элементов ведущего столбца в 0).
5. Повторение: Шаги 1-4 повторяются до тех пор, пока все свободные члены (b_i) не станут неотрицательными. В этот момент найденный план будет допустимым и оптимальным.

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

Условия дополняющей нежесткости: Связь между прямой и двойственной задачами

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

Формулировка и математическая запись условий

Рассмотрим прямую задачу максимизации с ограничениями типа «≤» и двойственную задачу минимизации с ограничениями типа «≥». Все переменные неотрицательны.

Прямая задача:

Z = Σj=1n cjxj → max

При ограничениях:

Σj=1n aijxj ≤ bi для i = 1, ..., m
xj ≥ 0 для j = 1, ..., n

Двойственная задача:

F = Σi=1m biyi → min

При ограничениях:

Σi=1m aijyi ≥ cj для j = 1, ..., n
yi ≥ 0 для i = 1, ..., m

Для формулировки условий введём понятия невязок:

• Невязки ограничений прямой задачи (S_i): Показывают, насколько ресурс i не используется полностью.
  Si = bi - Σj=1n aijxj ≥ 0
• Невязки ограничений двойственной задачи (R_j): Показывают разницу между оценкой затрат на единицу j-го продукта (теневая цена ресурсов, пошедших на производство) и его фактической прибылью.
  Rj = Σi=1m aijyi - cj ≥ 0

Условия дополняющей нежесткости гласят:

Если X^* = (x₁^*, …, x_n^*) является оптимальным планом прямой задачи, а Y^* = (y₁^*, …, y_m^*) является оптимальным планом двойственной задачи, то должны выполняться следующие условия:

1. y_i^*S_i^* = 0 для всех i = 1, …, m

   Это означает, что для каждого ограничения прямой задачи:

   • Если ресурс i используется не полностью (S_i^* > 0), то его двойственная оценка (теневая цена) y_i^* должна быть равна нулю (y_i^* = 0).
   • Если ресурс i имеет положительную теневую цену (y_i^* > 0), то он должен быть использован полностью (S_i^* = 0).
2. x_j^*R_j^* = 0 для всех j = 1, …, n

   Это означает, что для каждой переменной прямой задачи:

   • Если j-й продукт не производится (x_j^* = 0), то соответствующая невязка двойственной задачи R_j^* может быть любой (включая R_j^* > 0, что означает, что «оценка затрат» на производство единицы j-го продукта превышает его фактическую прибыль, то есть производство нерентабельно).
   • Если j-й продукт производится (x_j^* > 0), то его производство должно быть «эффективным» в смысле двойственной задачи (R_j^* = 0), что означает, что «оценка затрат» на его производство равна его прибыли.

Экономическая интерпретация условий дополняющей нежесткости

Эти условия имеют глубокий экономический смысл и являются ключевыми для понимания оптимальности в линейном программировании.

1. Неиспользуемые ресурсы и их теневая цена (y_i^*S_i^* = 0):
   • Если S_i^* > 0: Это означает, что i-й ресурс используется не полностью; имеется его избыток. В оптимальном плане нет необходимости в дополнительном объёме этого ресурса, поэтому его «теневая цена» или дополнительная ценность для увеличения прибыли равна нулю (y_i^* = 0). Покупка дополнительного объёма этого ресурса по любой цене (даже минимальной) будет невыгодна, поскольку он не будет использован.
   • Если y_i^* > 0: Это означает, что i-й ресурс является «дефицитным» или «связывающим» ограничением. Каждая дополнительная единица этого ресурса приведёт к увеличению прибыли. Следовательно, в оптимальном плане этот ресурс должен быть использован полностью, то есть его невязка S_i^* должна быть равна нулю (S_i^* = 0).
2. Нерентабельные продукты и их производство (x_j^*R_j^* = 0):
   • Если x_j^* > 0: Это означает, что j-й продукт производится в оптимальном плане. Для того чтобы производство было оптимальным, «оценка затрат» на производство единицы этого продукта (Σ_i=1^m a_ijy_i^*) должна быть равна его «прибыли» (c_j). То есть, невязка R_j^* = 0. Это подтверждает принцип, что в оптимальном плане производятся толь��о те продукты, которые являются «экономически эффективными» с точки зрения использования дефицитных ресурсов.
   • Если R_j^* > 0: Это означает, что «оценка затрат» на производство j-го продукта (с учётом теневых цен ресурсов) превышает его фактическую прибыль (c_j). Такой продукт нерентабелен для производства в условиях дефицитных ресурсов, и поэтому он не должен производиться в оптимальном плане (x_j^* = 0).

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

Применение для верификации и нахождения оптимального плана

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

Применение для верификации оптимальности:

Предположим, у нас есть потенциальные оптимальные планы X^* для прямой задачи и Y^* для двойственной задачи. Чтобы проверить, являются ли они действительно оптимальными, можно:

1. Проверить допустимость: Убедиться, что X^* удовлетворяет всем ограничениям прямой задачи, а Y^* — всем ограничениям двойственной задачи.
2. Проверить равенство целевых функций: Убедиться, что Z(X^*) = F(Y^*).
3. Применить условия дополняющей нежесткости: Проверить выполнение условий y_i^*S_i^* = 0 и x_j^*R_j^* = 0. Если все условия соблюдены, то планы X^* и Y^* являются оптимальными.

Применение для нахождения оптимального плана двойственной задачи (если известен оптимальный план прямой):

Этот подход особенно полезен, когда прямая задача решена, например, симплекс-методом, и найден оптимальный план X^*.

Пошаговое использование условий:

1. Идентификация активных и неактивных ограничений прямой задачи:
   • Для каждого ограничения прямой задачи:
     • Если Σ_j=1ⁿ a_ijx_j^* < b_i (ресурс не использован полностью, S_i^* > 0), то из первого условия дополняющей нежесткости следует, что соответствующая двойственная переменная y_i^* должна быть равна нулю (y_i^* = 0).
     • Если Σ_j=1ⁿ a_ijx_j^* = b_i (ресурс использован полностью, S_i^* = 0), то о значении y_i^* пока ничего сказать нельзя.
2. Идентификация положительных переменных прямой задачи:
   • Для каждой переменной прямой задачи:
     • Если x_j^* > 0 (продукт производится), то из второго условия дополняющей нежесткости следует, что соответствующее ограничение двойственной задачи должно выполняться как строгое равенство: Σ_i=1^m a_ijy_i^* — c_j = 0.
     • Если x_j^* = 0 (продукт не производится), то о значении R_j^* ничего сказать нельзя.
3. Формирование и решение системы уравнений:

   Используя полученные равенства (y_i^* = 0 для неактивных ограничений и Σ_i=1^m a_ijy_i^* = c_j для положительных x_j^*), формируется система линейных уравнений относительно двойственных переменных y_i^*.

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

4. Проверка неотрицательности: Найденные y_i^* должны быть неотрицательными. Если это не так, значит, либо начальный X^* не был оптимальным, либо была допущена ошибка в расчётах.

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

Целочисленное линейное программирование: Решение задач с дискретными переменными

В реальном мире многие экономические решения требуют дискретности: нельзя произвести 2.5 автомобиля, нанять 3.7 рабочих или построить 1.8 склада. Именно для таких задач, где переменные должны принимать только целочисленные значения, существует целочисленное линейное программирование (ЦЛП). Это подмножество линейного программирования, которое добавляет важное требование — целочисленность.

Графический метод для ЦЛП (с двумя переменными)

Как и в случае с обычной ЗЛП, графический метод для целочисленного линейного программирования наиболее нагляден и применим для задач с двумя переменными.

Алгоритм решения с учётом целочисленности:

1. Решение непрерывной задачи: Первым шагом является решение задачи линейного программирования без учёта требования целочисленности. Это делается с помощью стандартного графического метода, описанного выше, для определения оптимальной точки (x₁^*, x₂^*) и значения целевой функции Z^*.
2. Проверка целочисленности:
   • Если полученное оптимальное решение (x₁^*, x₂^*) уже является целочисленным, то это и есть оптимальное решение целочисленной задачи.
   • Если решение нецелочисленное, то Z^* будет верхней границей для задачи максимизации ЦЛП и нижней границей для задачи минимизации ЦЛП, так как добавление целочисленных ограничений может только ухудшить значение целевой функции.
3. Поиск ближайших целочисленных точек:
   • На графике необходимо найти все целочисленные точки, которые находятся внутри или на границе области допустимых решений (ОДР). Эти точки представляют собой допустимые целочисленные планы.
   • Особое внимание следует уделить целочисленным точкам, которые находятся в непосредственной близости от найденного нецелочисленного оптимума (x₁^*, x₂^*).
4. Выбор оптимального целочисленного решения:
   • Для каждой из найденных допустимых целочисленных точек вычислить значение целевой функции.
   • Среди этих значений выбрать ту точку, которая даёт наилучшее значение целевой функции (максимальное для задачи максимизации, минимальное для задачи минимизации). Эта точка и будет оптимальным целочисленным решением.

Ограничения метода и случаи, когда он неэффективен:

• Количество переменных: Главное ограничение — метод практически применим только для задач с двумя переменными. В трёхмерном пространстве поиск целочисленных точек в многограннике решений становится крайне сложным, а для большего числа переменных — невозможным.
• Большая ОДР: Если область допустимых решений очень велика, количество целочисленных точек может быть огромным, что делает ручной перебор неэффективным и трудоёмким.
• «Далеко» от оптимума: Оптимальное целочисленное решение может находиться не в ближайшей к нецелочисленному оптимуму точке, а значительно дальше, на другом «конце» ОДР. Это усложняет поиск и может привести к ошибкам при интуитивном выборе.
• Отсутствие наглядности: Для задач с более чем двумя переменными метод теряет свою главную ценность — наглядность.

Метод Гомори (метод отсечений)

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

Алгоритм метода Гомори:

1. Решение обычной ЗЛП: Сначала решается исходная задача линейного программирования без учёта требования целочисленности переменных. Это делается с помощью симплекс-метода.
2. Проверка целочисленности: Если полученное оптимальное решение (базисные переменные) является целочисленным, то это и есть оптимальное решение ЦЛП. Процесс завершён.
3. Выбор строки для отсечения: Если хотя бы одна базисная переменная имеет дробное значение, выбирается строка симплекс-таблицы, соответствующая этой переменной. Предпочтительно выбирать строку с наибольшей дробной частью свободного члена (b_i).

   Пусть выбранная строка имеет вид:

   xБ + Σj∈НБ aij xj = bi

   где x_Б — базисная переменная, НБ — множество небазисных переменных.

4. Построение отсекающего ограничения Гомори:

   Каждый коэффициент a_ij и свободный член b_i разбивается на целую и дробную части:

   aij = ⌊aij⌋ + fij
bi = ⌊bi⌋ + fi0

   где ⌊ ⋅ ⌋ — целая часть числа, f_ij и f_i0 — дробные части (0 ≤ f < 1).

   Из исходной строки получаем:

   xБ + Σj∈НБ (⌊aij⌋ + fij) xj = ⌊bi⌋ + fi0

   Переносим целые части в левую часть, дробные — в правую:

   xБ + Σj∈НБ ⌊aij⌋ xj - ⌊bi⌋ = fi0 - Σj∈НБ fij xj

   Левая часть этого равенства является целым числом, поскольку x_Б, x_j и ⌊ ⋅ ⌋ — целые. Правая часть должна быть целой, если x_j — целые.

   Так как f_i0 < 1 и Σ_j∈НБ f_ij x_j ≥ 0 (f_ij ≥ 0, x_j ≥ 0), то правая часть f_i0 — Σ_j∈НБ f_ij x_j всегда меньше 1.

   Если правая часть является целым числом, то она может быть только 0 или отрицательным целым числом (например, -1, -2…).

   Таким образом, мы можем сформировать отсекающее ограничение:

   Σj∈НБ fij xj ≥ fi0

   Это ограничение отсекает текущее нецелочисленное решение, но не отсекает ни одного целочисленного решения.

5. Добавление отсечения и решение новой задачи:
   • Отсекающее ограничение приводится к каноническому виду путём вычитания дополнительной переменной s_k и добавления искусственной переменной A_k (если требуется):
     Σj∈НБ fij xj - sk = fi0
   • Это новое ограничение добавляется к симплекс-таблице. Поскольку f_i0 > 0, но в левой части стоит сумма неотрицательных переменных, а затем вычитается s_k, то введение этого ограничения часто делает текущий план недопустимым.
   • Поэтому для решения новой задачи линейного программирования с добавленным ограничением используется двойственный симплекс-метод.
6. Повторение: Шаги 2-5 повторяются до тех пор, пока не будет найдено целочисленное оптимальное решение. В каждой итерации добавляется новое отсечение, которое сужает область допустимых решений, пока не будет получена целочисленная вершина.

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

Транспортная задача: Оптимизация перевозок

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

Постановка транспортной задачи и ее особенности

Формулировка задачи:

Пусть имеется m поставщиков (например, складов, заводов) с запасами a_i (i = 1, …, m) единиц товара и n потребителей (например, магазинов, распределительных центров) с потребностями b_j (j = 1, …, n) единиц того же товара. Известна стоимость перевозки c_ij одной единицы товара от i-го поставщика к j-му потребителю. Требуется найти такой план перевозок x_ij (количество товара, перевозимого от i-го поставщика к j-му потребителю), чтобы были удовлетворены все потребности, распределены все запасы, а общие затраты на перевозку были минимальными.

Математическая модель:

Переменные: x_ij ≥ 0 — количество товара, перевозимого от поставщика i к потребителю j.

Целевая функция (минимизация общих затрат):

F = Σi=1m Σj=1n cij xij → min

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

Σj=1n xij = ai для i = 1, ..., m

Ограничения по потребностям (каждый потребитель должен получить требуемое количество):

Σi=1m xij = bj для j = 1, ..., n

Особенности: Закрытая и открытая модели

• Закрытая (сбалансированная) транспортная задача: Общее количество товара у всех поставщиков равно общему спросу всех потребителей.
  Σi=1m ai = Σj=1n bj

  Это идеальный случай, когда спрос точно соответствует предложению.

• Открытая (несбалансированная) транспортная задача: Общее предложение не равно общему спросу.
  Σi=1m ai ≠ Σj=1n bj

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

Сведение открытой задачи к закрытой:

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

1. Если Σ_i=1^m a_i > Σ_j=1ⁿ b_j (избыток предложения): Вводится фиктивный потребитель (n+1) с потребностью b_n+1 = Σ_i=1^m a_i — Σ_j=1ⁿ b_j. Стоимость перевозки к этому потребителю c_i,n+1 обычно принимается равной нулю, так как это товар, который остаётся на складе или не доставляется.
2. Если Σ_i=1^m a_i < Σ_j=1ⁿ b_j (избыток спроса): Вводится фиктивный поставщик (m+1) с запасом a_m+1 = Σ_j=1ⁿ b_j — Σ_i=1^m a_i. Стоимость перевозки от этого поставщика c_m+1,j также принимается равной нулю, так как это неудовлетворённый спрос, который, возможно, будет покрыт из других источников.

После сведения к закрытой форме, транспортная задача становится обычной ЗЛП и может быть решена специализированными методами.

Методы построения начального опорного плана

Для решения транспортной задачи методом потенциалов сначала необходимо найти начальный опорный план (базисное допустимое решение). Это план, который удовлетворяет всем ограничениям и имеет m + n — 1 базисных (ненулевых) перевозок.

1. Метод северо-западного угла:
   • Принцип: Самый простой, но наименее эффективный метод, игнорирующий стоимости перевозок.
   • Алгоритм:
     1. Начать с левой верхней клетки (x₁₁) транспортной таблицы.
     2. В эту клетку записать максимально возможное значение x₁₁, равное min(a₁, b₁).
     3. Если a₁ = b₁, то и строка 1, и столбец 1 исчерпаны. Переход к x₂₂.
     4. Если a₁ < b₁, то запас поставщика 1 исчерпан (a₁ = 0). Переход к клетке x₁₂.
     5. Если a₁ > b₁, то потребность потребителя 1 удовлетворена (b₁ = 0). Переход к клетке x₂₁.
     6. Продолжать до тех пор, пока все запасы не будут распределены, и все потребности удовлетворены.
   • Эффективность: Даёт допустимый, но часто далёкий от оптимального план.
2. Метод минимального элемента (наименьшей стоимости):
   • Принцип: Более эффективный, учитывает стоимости перевозок.
   • Алгоритм:
     1. Во всей транспортной таблице найти клетку с наименьшей стоимостью перевозки c_ij. Если таких клеток несколько, выбрать любую.
     2. В эту клетку записать максимально возможное значение x_ij, равное min(a_i, b_j).
     3. Уменьшить соответствующий запас a_i и потребность b_j на x_ij.
     4. Если запас a_i исчерпан, исключить i-ю строку из дальнейшего рассмотрения. Если потребность b_j удовлетворена, исключить j-й столбец.
     5. Повторять шаги 1-4 для оставшейся части таблицы, пока все запасы не будут распределены, и все потребности удовлетворены.
   • Эффективность: Обычно даёт более дешёвый начальный план, чем метод северо-западного угла.
3. Метод Фогеля (метод аппроксимации Фогеля):
   • Принцип: Наиболее эффективный из эвристических методов, часто даёт план, близкий к оптимальному, за счёт учёта «штрафов» за неоптимальный выбор.
   • Алгоритм:
     1. Для каждой строки и каждого столбца вычислить «штраф» — разность между двумя наименьшими стоимостями c_ij в этой строке/столбце.
     2. Найти строку или столбец с наибольшим штрафом.
     3. В выбранной строке/столбце найти клетку с минимальной стоимостью c_ij.
     4. В эту клетку записать максимально возможное значение x_ij, равное min(a_i, b_j).
     5. Уменьшить соответствующий запас a_i и потребность b_j на x_ij.
     6. Если запас a_i исчерпан, исключить i-ю строку. Если потребность b_j удовлетворена, исключить j-й столбец.
     7. Пересчитать штрафы для оставшейся таблицы и повторить шаги 2-6, пока все запасы не будут распределены, и все потребности удовлетворены.
   • Эффективность: Даёт начальный план, который обычно значительно ближе к оптимальному, чем планы, полученные другими эвристическими методами.

Сравнение эффективности:

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

Метод потенциалов для нахождения оптимального плана

Метод потенциалов (или метод распределения, U-V метод) используется для проверки оптимальности начального опорного плана, полученного одним из вышеописанных методов, и его улучшения до тех пор, пока не будет найден оптимальный план.

Алгоритм метода потенциалов:

1. Построение начального опорного плана: Используя один из методов (северо-западного угла, минимального элемента, Фогеля), создайте первый допустимый план перевозок.
2. Проверка на вырожденность: Подсчитайте количество базисных клеток (клеток с x_ij > 0). Оно должно быть равно m + n — 1.
   • Если количество базисных клеток меньше m + n — 1, план является вырожденным. Для устранения вырожденности необходимо ввести в свободные клетки (с x_ij = 0) фиктивные (нулевые) перевозки, пока их общее число не станет m + n — 1. Эти фиктивные перевозки должны быть выбраны так, чтобы не образовывать замкнутых циклов.
3. Расчёт потенциалов u_i и v_j: Присвойте потенциалы u_i для каждой строки (поставщика) и v_j для каждого столбца (потребителя).
   • Для этого один из потенциалов (например, u₁) произвольно принимается равным нулю.
   • Затем для всех базисных клеток (x_ij > 0) потенциалы рассчитываются по формуле: c_ij = u_i + v_j. Из этой формулы, зная c_ij и один из потенциалов (u_i или v_j), можно найти другой.
4. Вычисление оценок (невязок) Δ_ij для свободных клеток: Для всех свободных клеток (x_ij = 0) вычислите их оценки по формуле: Δ_ij = c_ij — (u_i + v_j).
5. Проверка оптимальности:
   • Для задачи минимизации: Если все оценки Δ_ij ≥ 0, то текущий план является оптимальным. Процесс завершён.
   • Для задачи максимизации: Если все оценки Δ_ij ≤ 0, то текущий план является оптимальным.
   • Если есть отрицательные оценки (для минимизации) или положительные (для максимизации), план неоптимален.
6. Построение замкнутого цикла (цикла пересчёта):
   • Если план неоптимален, выберите свободную клетку с наибольшей по модулю отрицательной оценкой (для минимизации) или положительной (для максимизации). Эта клетка будет началом цикла.
   • Постройте замкнутый цикл, проходящий через выбранную свободную клетку и только через базисные клетки. Углы цикла могут быть только под прямым углом, и в каждой вершине цикла должно быть не менее двух базисных клеток (для того, чтобы можно было «повернуть»).
   • Расставьте знаки «+» и «-» поочередно в вершинах цикла, начиная с «+» в выбранной свободной клетке.
7. Перераспределение перевозок:
   • Найдите минимальное значение перевозок в клетках цикла со знаком «-«. Обозначим это значение как θ.
   • Прибавьте θ к перевозкам в клетках со знаком «+».
   • Вычтите θ из перевозок в клетках со знаком «-«.
   • В результате одна из базисных клеток со знаком «-» обнулится и выйдет из базиса, а выбранная свободная клетка станет базисной.
8. Создание нового опорного плана: Получен новый опорный план с улучшенным значением целевой функции.
9. Повторение: Повторяйте шаги 3-8 до тех пор, пока не будет найден оптимальный план (все Δ_ij ≥ 0 для минимизации).

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

Сетевое планирование: Управление проектами и ресурсами

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

Основные понятия сетевого планирования и построение сетевого графика

В основе сетевого планирования лежит концепция сетевого графика — графического представления проекта.

Основные понятия:

• Работа (или операция): Действие, требующее затрат времени, ресурсов и приводящее к определённому результату. На сетевом графике работы обозначаются дугами (стрелками). Над дугой указывают код работы и её продолжительность.
• Событие: Результат выполнения одной или нескольких работ, который не требует затрат времени или ресурсов. События обозначаются узлами (кружками) на сетевом графике. Каждое событие имеет свой номер. Событие, в которое входят дуги, называется последующим; событие, из которого выходят дуги, называется предшествующим.
• Начальное событие: Событие, не имеющее предшествующих работ (из него только выходят дуги).
• Конечное событие: Событие, не имеющее последующих работ (в него только входят дуги).
• «Пустышка» (фиктивная работа): Работа с нулевой продолжительностью и нулевыми затратами ресурсов, используемая для показа логической взаимосвязи между событиями, когда одна работа должна завершиться до начала другой, но физически они не связаны. Обозначается пунктирной стрелкой.
• Путь: Любая последовательность работ от начального до конечного события.
• Длина пути: Сумма продолжительностей работ, входящих в этот путь.

Построение сетевого графика:

1. Определить все работы проекта: Составить список всех работ, их продолжительность (t_ij) и непосредственных предшественников.
2. Обозначить события: Каждая работа имеет начальное и конечное событие. Начальное событие проекта (обычно с номером 1) не имеет предшествующих работ. Конечное событие не имеет последующих работ.
3. Соединить события дугами: Нарисовать стрелки (дуги) от предшествующего события к последующему, обозначая работы. Над стрелками указать идентификатор работы и её продолжительность.
4. Избегать зацикливаний и повторяющихся связей: Сетевой график должен быть ацикличным (без замкнутых петель) и не иметь более одной работы между парой событий.
5. Использовать «пустышки»: Для корректного отображения логических зависимостей, когда это необходимо, вводятся фиктивные работы.
   • Например, если работа C может начаться только после A и B, а работа D только после B, то A и B входят в одно событие, а затем D выходит из события B, а C из события, куда пришли A и B. Возможно потребуется «пустышка» от конечного события работы B к конечному событию работы A.

Метод критического пути (CPM) и расчет потенциалов

Метод критического пути (Critical Path Method, CPM) — это ключевой алгоритм сетевого планирования, позволяющий определить минимальное время выполнения проекта и выделить «критические» работы, задержка которых неизбежно приведёт к задержке всего проекта. В контексте CPM «потенциалы» — это ранние и поздние сроки наступления событий.

Расчёт ранних и поздних сроков событий и работ:

1. Ранние сроки начала/окончания событий (T^РН_i, T^РО_i):
   • T^РН₁ = 0 для начального события проекта.
   • T^РН_j = max_{i → j} (T^РО_i): Ранний срок начала события j равен максимальному из ранних сроков окончания всех работ, входящих в это событие.
   • T^РО_i = T^РН_i + t_ij: Ранний срок окончания работы (i,j) равен раннему сроку начала её предшествующего события плюс продолжительность работы.
   • Расчёты ведутся от начала к концу проекта.
2. Поздние сроки начала/окончания событий (T^ПН_i, T^ПО_i):
   • T^ПО_N = T^РН_N: Поздний срок окончания для конечного события N равен его раннему сроку окончания (т.е., задержка конечного события не допускается).
   • T^ПО_i = min_{i → j} (T^ПН_j): Поздний срок окончания события i равен минимальному из поздних сроков начала всех работ, выходящих из этого события.
   • T^ПН_j = T^ПО_j — t_ij: Поздний срок начала работы (i,j) равен позднему сроку окончания её последующего события минус продолжительность работы.
   • Расчёты ведутся от конца к началу проекта.

Определение полных резервов времени:

• Полный резерв времени для события i (R_i): Максимальное время, на которое можно отложить наступление события i без изменения срока завершения проекта.
  Ri = TПОi - TРНi
• Полный резерв времени для работы (i,j) (R_ij): Максимальное время, на которое можно отложить начало или увеличить продолжительность работы (i,j) без изменения срока завершения проекта.
  Rij = TПНj - TРНi - tij

Выделение критического пути:

• Критический путь — это самый длинный путь от начального до конечного события проекта.
• Признак критического пути: Все работы, лежащие на критическом пути, имеют нулевые полные резервы времени (R_ij = 0).
• Длина критического пути определяет минимальную возможную продолжительность всего проекта. Любая задержка на критической работе приводит к задержке всего проекта.

Доведение до оптимального плана и нюансы применения потенциалов

В контексте сетевого планирования «доведение до оптимального плана» чаще всего означает не поиск оптимального потока, как в транспортной задаче, а оптимизацию проекта по времени, стоимости или другим ресурсам.

Оптимизация проекта:

1. Оптимизация по времени (сжатие проекта): Если требуется сократить общую продолжительность проекта, это достигается путём сокращения продолжительности работ, лежащих на критическом пути. Однако такое сокращение обычно приводит к увеличению затрат (например, за счёт сверхурочной работы, привлечения дополнительных ресурсов). Важно анализировать соотношение «время-затраты». При сокращении критического пути могут появиться новые критические пути.
2. Оптимизация по стоимости: Целью может быть минимизация общих затрат при соблюдении определённых сроков. Это включает в себя выбор наиболее дешёвых способов выполнения работ, а также эффективное распределение ресурсов.
3. Балансировка ресурсов: Оптимальный план может подразумевать такое распределение ресурсов, чтобы избежать их пиковых нагрузок и обеспечить равномерное использование.

Нюансы применения «метода потенциалов» в сетевом планировании:

Важно отметить, что термин «метод потенциалов» в классическом смысле, как он применяется в транспортной задаче (для нахождения оптимального плана перевозок), не используется напрямую для «оптимального плана сетевой задачи» в смысле потоков.

В сетевом планировании «потенциалы» — это именно ранние и поздние сроки событий. Они используются для:

• Определения критического пути.
• Вычисления резервов времени для событий и работ.
• Оценки чувствительности проекта к задержкам.

Если же речь идёт о сетевых задачах типа «задача о максимальном потоке» или «задача о потоке минимальной стоимости», то для их решения применяются совсем другие алгоритмы (например, алгоритм Форда-Фалкерсона, алгоритм Эдмондса-Карпа, или алгоритмы, использующие двойственные оценки/потенциалы в контексте графов для определения кратчайших путей по стоимостям, но это более сложные и специализированные методы, выходящие за рамки классического CPM).

Таким образом, в рамках сетевого планирования проектов, «метод потенциалов» в основном относится к расчёту временных параметров (ранних/поздних сроков) для эффективного управления проектом, а не к итеративному улучшению потоков.

Задача о назначениях: Оптимальное распределение ресурсов

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

Постановка задачи о назначениях и ее связь с транспортной задачей

Формулировка задачи:

Имеется n исполнителей (например, рабочие, машины, отделы) и n работ (проекты, задачи). Известна «стоимость» (или время, или прибыль) c_ij выполнения j-й работы i-м исполнителем. Необходимо найти такое назначение x_ij (где x_ij = 1, если i-й исполнитель назначен на j-ю работу; x_ij = 0 в противном случае), чтобы минимизировать суммарные затраты.

Математическая модель (для минимизации):

Целевая функция:

F = Σi=1n Σj=1n cij xij → min

Ограничения:

1. Каждый исполнитель выполняет ровно одну работу:
   Σj=1n xij = 1 для i = 1, ..., n (для каждого исполнителя)
2. Каждая работа выполняется ровно одним исполнителем:
   Σi=1n xij = 1 для j = 1, ..., n (для каждой работы)
3. Переменные принимают целочисленные значения:
   xij ∈ {0, 1}

Связь с транспортной задачей:

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

• Каждый поставщик (исполнитель) имеет запас a_i = 1 (может выполнить одну работу).
• Каждый потребитель (работа) имеет потребность b_j = 1 (требует одного исполнителя).
• Общее предложение равно общему спросу (Σa_i = n, Σb_j = n), что делает её сбалансированной транспортной задачей.

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

Венгерский метод (метод Куна): Детальный алгоритм

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

Алгоритм Венгерского метода (для минимизации затрат):

1. Приведение матрицы затрат (этап 1 — по строкам):
   • Для каждой строки матрицы затрат найти минимальный элемент.
   • Вычесть этот минимальный элемент из всех элементов этой строки.
   • Цель: В каждой строке матрицы после этого преобразования появится хотя бы один ноль.
2. Приведение матрицы затрат (этап 2 — по столбцам):
   • Для каждого столбца полученной матрицы найти минимальный элемент.
   • Вычесть этот минимальный элемент из всех элементов этого столбца.
   • Цель: После этого преобразования в каждой строке и в каждом столбце матрицы появится хотя бы один ноль.
   • В результате этих двух этапов матрица преобразуется таким образом, что её оптимальное назначение будет включать только нулевые элементы, и это не изменит относительной оптимальности задачи.
3. Покрытие нулей минимальным числом линий:
   • Задача состоит в том, чтобы покрыть все нули в текущей матрице минимальным количеством горизонтальных и/или вертикальных линий.
   • Как это сделать (эвристический подход):
     • Найти строки и столбцы, содержащие наименьшее количество нулей.
     • Покрывать сначала те строки/столбцы, где нулей больше.
     • Более систематический подход:
       1. Отметить все строки, в которых нет назначений (если мы уже сделали предварительные назначения).
       2. Отметить все столбцы, содержащие нули в отмеченных строках.
       3. Отметить все строки, содержащие назначения в отмеченных столбцах.
       4. Повторять 2 и 3, пока не будет новых отметок.
       5. Провести линии через неотмеченные строки и отмеченные столбцы.
   • Проверка: Если минимальное число линий, покрывающих все нули, равно размерности матрицы n, то оптимальное назначение найдено. Можно перейти к шагу 5.
   • Если число линий меньше n, то текущая матрица не позволяет найти оптимальное назначение. Переходим к шагу 4.
4. Пересчёт матрицы (улучшение матрицы):
   • Найти наименьший из всех элементов, не покрытых ни одной линией. Обозначим его как k.
   • Вычесть k из всех непокрытых элементов.
   • Добавить k к элементам, которые находятся на пересечении двух линий (были покрыты дважды).
   • Элементы, покрытые одной линией, остаются без изменений.
   • После пересчёта вернуться к шагу 3 (покрытие нулей).
5. Определение оптимального назначения:
   • Когда число линий, покрывающих все нули, равно n, необходимо выбрать n нулей таким образом, чтобы каждый из них находился в отдельной строке и отдельном столбце. Это и будет оптимальное назначение.
   • Как выбрать нули: Искать строки или столбцы, в которых есть только один ноль. Сделать назначение в эту клетку, затем «вычеркнуть» соответствующую строку и столбец, чтобы избежать повторных назначений. Продолжать до тех пор, пока не будут сделаны все n назначений.

Для задачи максимизации:

Чтобы применить Венгерский метод для максимизации (например, прибыли), необходимо преобразовать исходную матрицу. Найти максимальный элемент во всей матрице, а затем вычесть каждый элемент матрицы из этого максимального элемента. Это превратит задачу максимизации в эквивалентную задачу минимизации «потерь» или «недополученной выгоды», и далее применяется стандартный Венгерский метод.

Связь Венгерского метода с методом потенциалов

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

1. Двойственные переменные (потенциалы): Каждый раз, когда мы вычитаем минимальный элемент из строки или столбца в Венгерском методе, это фактически эквивалентно введению двойственных переменных (потенциалов).
   • Вычитание минимума из строки i (u_i) можно рассматривать как «теневую стоимость» для исполнителя i.
   • Вычитание минимума из столбца j (v_j) можно рассматривать как «теневую стоимость» для работы j.
   • Таким образом, преобразованная стоимость c’_ij = c_ij — u_i — v_j.
2. Условия дополняющей нежесткости: Венгерский метод ищет такое назначение, чтобы x_ij = 1 только для тех клеток, где c’_ij = 0 (то есть c_ij = u_i + v_j). Это прямое отражение условий дополняющей нежесткости в контексте задачи о назначениях.
3. Итерации пересчёта: Шаг 4 Венгерского метода (пересчёт матрицы путём вычитания k из непокрытых элементов и добавления k к дважды покрытым) также имеет двойственную интерпретацию. Это эквивалентно корректировке потенциалов (u_i и v_j), чтобы создать новые нули и улучшить возможность нахождения оптимального назначения.

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

Заключение: Верификация и оформление решений контрольной работы

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

Резюме по основным математическим методам:

• Линейное программирование (ЛП): Основа всех оптимизационных задач, позволяет моделировать распределение ограниченных ресурсов для достижения оптимальной цели.
• Графический метод: Наглядный, но ограниченный двумя переменными, идеален для понимания основ.
• Симплекс-метод: Универсальный и мощный алгоритм для ЗЛП любой размерности, включающий метод искусственного базиса для задач без начального базиса и двойственный симплекс-метод для специфических условий.
• Условия дополняющей нежесткости: Ключевые для понимания связи между прямой и двойственной задачами, верификации решений и экономической интерпретации теневых цен.
• Целочисленное ЛП: Решает задачи, где переменные должны быть дискретными; метод Гомори обеспечивает точное решение.
• Транспортная задача: Оптимизация перевозок, методы начального плана (северо-западного угла, минимального элемента, Фогеля) и метод потенциалов для достижения оптимума.
• Сетевое планирование: Управление проектами, метод критического пути для определения сроков и критических работ.
• Задача о назначениях: Оптимальное сопоставление ресурсов и задач, эффективно решаемое Венгерским методом.

Важность тщательной верификации решений:

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

• Для ЛП: Проверьте допустимость найденного плана (удовлетворяет ли всем ограничениям). Если использовалась двойственная задача, убедитесь, что Z^* = F^* и выполнены условия дополняющей нежесткости.
• Для транспортной задачи: Убедитесь, что все запасы распределены и все потребности удовлетворены. Проверьте количество базисных клеток и условие Δ_ij ≥ 0.
• Для сетевого планирования: Убедитесь, что критический путь найден правильно и все работы на нём имеют нулевые резервы.
• Для ЦЛП: Проверьте, что все переменные действительно целочисленны.

Рекомендации по оформлению контрольной работы:

Качественно оформленная контрольная работа — это не просто набор правильных ответов, а демонстрация глубокого понимания материала.

1. Чёткость изложения: Начните с постановки задачи, укажите её тип и цель.
2. Пошаговость: Представляйте решение пошагово, следуя алгоритмам. Каждый шаг должен быть логически обоснован и понятен.
3. Пояснения: Каждое действие, каждая вводимая переменная или преобразование должны быть пояснены. Не просто «вычитаем», а «вычитаем минимальный элемент для обнуления в каждой строке».
4. Графики и таблицы: Используйте их проактивно. Графики для графического метода, симплекс-таблицы для симплекс-метода, матрицы для транспортной задачи и задачи о назначениях, сетевые графики для сетевого планирования. Они делают материал наглядным и облегчают проверку.
5. Формулы: Все формулы должны быть представлены чётко и корректно, используя соответствующую математическую нотацию.
6. Экономическая интерпретация результатов: Это ключевой аспект. Полученные числовые значения (оптимальный план, значение целевой функции, теневые цены) должны быть проанализированы и объяснены с экономической точки зрения. Что означает, что ресурс дефицитен? Какие управленческие решения можно принять на основе теневых цен? Какой смысл имеет критический путь для проекта?
7. Выводы: Завершите решение каждой задачи чётким выводом, формулирующим оптимальное решение и его значение.
8. Аккуратность: Чистота и порядок в оформлении работы не только производят хорошее впечатление, но и помогают избежать ошибок при проверке.

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

Список использованной литературы

1. Бабенко Е.А., Мажура В.М., Куршубадзе Р.З., Ковалева К.А. Симплекс метод с искусственным базисом // КиберЛенинка. URL: https://cyberleninka.ru/article/n/simpleks-metod-s-iskusstvennym-bazisom (дата обращения: 03.11.2025).
2. Венгерский метод решения задачи о назначениях // StudFiles. 2020. URL: https://studfile.net/preview/7891338/page:7/ (дата обращения: 03.11.2025).
3. Графический метод решения задач линейного программирования // Политехнический Колледж № 50. URL: https://pk50.mskobr.ru/attach_files/upload_users_files/6451a9bf11c97.pdf (дата обращения: 03.11.2025).
4. Двойственная задача линейного программирования / Хабр. 2021. URL: https://habr.com/ru/articles/566110/ (дата обращения: 03.11.2025).
5. Двойственный симплексный метод // Онлайн-калькулятор. URL: https://math.semestr.ru/optim/dual.php (дата обращения: 03.11.2025).
6. Задача о назначениях. Венгерский метод // StudFiles. 2019. URL: https://studfile.net/preview/7666291/page:10/ (дата обращения: 03.11.2025).
7. Лекция 6: Двойственный симплекс – метод. Исследование моделей задач линейного программирования на чувствительность // Интуит. 2007. URL: https://www.intuit.ru/studies/courses/2190/730/lecture/28168 (дата обращения: 03.11.2025).
8. Метод Гомори. Решение задач целочисленного программирования // StudFiles. 2019. URL: https://studfile.net/preview/7666291/page:6/ (дата обращения: 03.11.2025).
9. Метод потенциалов в транспортной задаче // Решим.ру. 2018. URL: https://math.reshim.ru/optim/metod-potencialov-v-transportnoy-zadache/ (дата обращения: 03.11.2025).
10. Оптимальные решения прямой и двойственной задачи // StudFiles. 2019. URL: https://studfile.net/preview/7666291/page:4/ (дата обращения: 03.11.2025).
11. Примеры решений двойственных задач линейного программирования онлайн. Двойственность в ЗЛП // МатБюро. URL: https://www.matburo.ru/sub_subject.php?p=lp_dual (дата обращения: 03.11.2025).
12. Прямая и двойственная задача линейного программирования // StudFiles. URL: https://studfile.net/preview/6716946/page:14/ (дата обращения: 03.11.2025).
13. Решение ЗЛП симплекс методом с искусственным базисом // Решим.ру. 2018. URL: https://math.reshim.ru/lp/simpleks-metod-s-iskusstvennym-bazisom/ (дата обращения: 03.11.2025).
14. Решение задачи о назначениях венгерским методом // Решим.ру. 2018. URL: https://math.reshim.ru/optim/zadacha-o-naznacheniyah-vengerskiy-metod/ (дата обращения: 03.11.2025).
15. Решение задач целочисленного линейного программирования // StudFiles. 2020. URL: https://studfile.net/preview/7891338/page:5/ (дата обращения: 03.11.2025).
16. Сетевое планирование и управление // StudFiles. 2020. URL: https://studfile.net/preview/7891338/page:6/ (дата обращения: 03.11.2025).
17. Сетевые графики // StudFiles. 2019. URL: https://studfile.net/preview/7666291/page:8/ (дата обращения: 03.11.2025).
18. Симплекс метод с искусственным базисом // Экономика.ру. 2018. URL: https://www.ekonomika.ru/lectures/lecture_view?id=457 (дата обращения: 03.11.2025).
19. Симплекс метод. Метод искусственного базиса // Математика для студентов. URL: https://www.math.by/prog/lp/simplex.html (дата обращения: 03.11.2025).
20. Симплексный метод решения задач линейного программирования // Calc.ru. URL: https://www.calc.ru/simpleksnyi-metod-resheniya-zadach-lineinogo-programmirovaniya.html (дата обращения: 03.11.2025).
21. Транспортная задача // StudFiles. 2020. URL: https://studfile.net/preview/7891338/page:3/ (дата обращения: 03.11.2025).
22. Транспортная задача: постановка, математическая модель, методы решения // Решим.ру. 2018. URL: https://math.reshim.ru/optim/transportnaya-zadacha/ (дата обращения: 03.11.2025).
23. Целочисленное программирование. Графический метод. Метод Гомори // Решим.ру. 2018. URL: https://math.reshim.ru/optim/celochislennoe-programmirovanie-graficheskiy-metod-metod-gomori/ (дата обращения: 03.11.2025).
24. Экономическая интерпретация двойственной задачи // CyberForum.ru. URL: https://www.cyberforum.ru/lp/thread1023773.html (дата обращения: 03.11.2025).