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

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

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

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

Основные понятия и классификация задач

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

Ключевыми элементами любой задачи ЛП являются:

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

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

Построение математической модели — это искусство перевода проблемы из реального мира в формальный язык математики. Этот процесс обычно включает следующие этапы:

1. Понимание проблемы и определение цели: Четкое определение того, что нужно оптимизировать (например, минимизировать затраты, максимизировать прибыль) и какие факторы на это влияют.
2. Идентификация переменных: Определение всех количественных показателей, которые можно изменять и которые влияют на целевую функцию и ограничения. Важно убедиться, что переменные могут принимать неотрицательные значения (xj ≥ 0), что является стандартным требованием в большинстве задач ЛП.
3. Формулирование целевой функции: Запись математического выражения, которое представляет собой функцию, подлежащую оптимизации (минимум или максимум). Это должна быть линейная функция от выбранных переменных, например, F(x) = c1x1 + c2x2 + ... + cnxn.
4. Определение и формулирование ограничений: Запись всех условий, которые связывают переменные. Каждое ограничение должно быть выражено в виде линейного уравнения или неравенства. Например, ограничения могут быть по ресурсам (не более R единиц), по минимальным требованиям (не менее B единиц) или по пропорциям.

Пример 1: Математическая модель задачи оптимизации рациона питания

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

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

1. Переменные задачи:
Пусть xj будет количеством j-го продукта (в килограммах, граммах или условных единицах), которое мы включаем в рацион.
Очевидно, что xj ≥ 0 для всех j = 1, ..., N, поскольку количество продукта не может быть отрицательным.

2. Целевая функция (оптимизируемый показатель):
Чаще всего в таких задачах целью является минимизация общей стоимости рациона.
Пусть cj — стоимость единицы j-го продукта. Тогда целевая функция будет выглядеть так:
F(x) = c1x1 + c2x2 + ... + cNxN → min.

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

3. Ограничения по питательным веществам:
Каждый продукт содержит определённое количество различных питательных веществ (белки, жиры, углеводы, витамины, минералы и т.д.). Для каждого i-го питательного вещества установлены минимальные (bi_min) и/или максимальные (bi_max) требования, которые должны быть соблюдены в суточном рационе.
Пусть aij — количество i-го питательного вещества, содержащегося в единице j-го продукта. Тогда ограничения по питательным веществам будут иметь вид:

• Для минимальных требований: Σj=1N aijxj ≥ bi_min
• Для максимальных требований: Σj=1N aijxj ≤ bi_max

Примеры питательных веществ и их ограничений:

• Белки: Общее количество белков в рационе должно быть не менее 22% от общего веса смеси. Если мы задаем вес смеси W = Σj=1N xj, то Σj=1N aбелок,jxj ≥ 0,22W.
• Жиры: Могут быть ограничения на долю растительных липидов, например, не менее 20% от общего количества жиров. Это потребует дополнительного учёта типов жиров.
• Углеводы: Не менее 30% от общего потребления углеводов должны быть сложными.
• Витамины и минералы: Например, минимальное суточное потребление кальция, витамина C, железа.
• Калорийность: Общая калорийность рациона может быть ограничена сверху и снизу (например, 2000 ккал ≤ Калорийность ≤ 2500 ккал).

4. Дополнительные ограничения по продуктам (ассортименту):
Чтобы обеспечить разнообразие рациона или избежать избыточного потребления какого-либо одного продукта, могут быть введены дополнительные ограничения:

• Максимальное количество конкретного продукта: xj ≤ Max_Quantityj. Например, если речь идет о кормах для кур-несушек, может быть установлено, что конкретного корма можно давать не более 125 грамм в день на особь.
• Доля продукта в рационе: Количество j-го продукта не должно превышать определённую долю от общего веса рациона: xj ≤ k * Σj=1N xj, где k — допустимая доля.

Общий вид математической модели задачи оптимизации рациона питания:
Минимизировать:
F(x) = Σj=1N cjxj

При ограничениях:
Σj=1N aijxj ≥ bi_min (для всех i, требующих минимального значения)
Σj=1N aijxj ≤ bi_max (для всех i, требующих максимального значения)
xj ≥ 0 (для всех j)
xj ≤ Max_Quantityj (для всех j, имеющих верхний лимит)

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

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

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

Пошаговый алгоритм графического метода

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

1. Построение области допустимых решений (ОДР):
   • Преобразование неравенств в равенства: Каждое ограничение-неравенство (например, a1x1 + a2x2 ≤ b) временно рассматривается как равенство (a1x1 + a2x2 = b). Это позволяет построить соответствующую прямую на координатной плоскости (x1, x2). Для построения прямой достаточно найти две точки, лежащие на ней (например, точки пересечения с осями координат).
   • Определение допустимых полуплоскостей: Для каждого неравенства необходимо определить, какая из двух полуплоскостей, разделённых построенной прямой, является допустимой. Простейший способ — использовать «тестовую точку», например, начало координат (0,0), если оно не лежит на прямой. Подставив координаты (0,0) в исходное неравенство, мы увидим, удовлетворяет ли оно условию. Если да, то полуплоскость, содержащая (0,0), является допустимой. Если нет, то допустимой является противоположная полуплоскость.
   • Учёт ограничений неотрицательности: Ограничения x1 ≥ 0 и x2 ≥ 0 означают, что область допустимых решений всегда находится в первом квадранте координатной плоскости.
   • Формирование ОДР: Область, которая одновременно удовлетворяет всем неравенствам и ограничениям неотрицательности, является областью допустимых решений. Это всегда будет выпуклый многоугольник (если область ограничена) или неограниченная выпуклая область. Вершины этого многоугольника называются угловыми точками.
2. Построение вектора градиента целевой функции:
   • Целевая функция имеет вид L = c1x1 + c2x2.
   • Вектор градиента C = (c₁, c₂) строится из начала координат. Этот вектор указывает направление наискорейшего возрастания целевой функции. Это критически важно: для задач максимизации мы будем двигаться в направлении вектора C, а для задач минимизации — в противоположном направлении (т.е. в направлении вектора -C).
3. Поиск оптимального решения:
   • Построение линии уровня: Чтобы найти оптимальное решение, мы строим «линию уровня» целевой функции. Это любая прямая вида c1x1 + c2x2 = K, где K — произвольная константа. Эта линия перпендикулярна вектору градиента C.
   • Параллельный перенос линии уровня: Теперь мы перемещаем эту линию уровня параллельно самой себе.
     • Для задачи максимизации: линию перемещают в направлении вектора C (или перпендикулярно ему, но «дальше» от начала координат в направлении C) до тех пор, пока она не коснется области допустимых решений в самой «удалённой» точке в этом направлении.
     • Для задачи минимизации: линию перемещают в противоположном направлении от вектора C (или перпендикулярно ему, но «ближе» к началу координат в направлении -C) до тех пор, пока она не коснется области допустимых решений в самой «близкой» точке в этом направлении.
   • Определение оптимальной точки: Точка (или отрезок), в которой линия уровня в последний раз касается ОДР, является оптимальным решением. Этой точкой всегда будет одна из вершин многоугольника допустимых решений (или целый отрезок, если линия уровня совпадает с одной из сторон многоугольника).
   • Вычисление оптимального значения: Координаты (x1*, x2*) этой оптимальной вершины подставляются в целевую функцию L = c1x1 + c2x2 для получения оптимального значения L*.
   • Случаи неограниченной ОДР: Если область допустимых решений неограничена в направлении оптимизации (например, для максимизации), то целевая функция также может быть неограниченной, и задача не имеет конечного оптимального решения.

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

Симплекс-метод: универсальный инструмент решения ЗЛП

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

Приведение задачи к стандартной (канонической) форме

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

Ключевые требования стандартной формы:

1. Целевая функция должна быть на максимизацию. Если исходная задача на минимизацию F(x), её можно преобразовать в задачу на максимизацию, минимизируя -F(x). То есть, min F(x) ≡ max (-F(x)).
2. Все ограничения должны быть представлены в виде равенств. Неравенства преобразуются следующим образом:
   • Для неравенства типа «≤» (например, Σaijxj ≤ bi) вводится дополнительная неотрицательная переменная si (переменная остатка), которая превращает неравенство в равенство: Σaijxj + si = bi. Переменная si представляет собой неиспользованный остаток ресурса.
   • Для неравенства типа «≥» (например, Σaijxj ≥ bi) вводится избыточная неотрицательная переменная si (переменная избытка), которая вычитается из левой части, превращая неравенство в равенство: Σaijxj - si = bi. Переменная si представляет собой превышение минимального требования.
3. Все переменные должны быть неотрицательными: xj ≥ 0. Если какая-либо переменная xk не ограничена по знаку, её можно заменить разностью двух неотрицательных переменных: xk = xk' - xk'', где xk' ≥ 0, xk'' ≥ 0.
4. Свободные члены ограничений (правые части) должны быть неотрицательными: bi ≥ 0. Если bi < 0, можно умножить всё ограничение на -1, изменив знак неравенства, а затем преобразовать его в равенство.

После этих преобразований мы получаем систему m линейных уравнений с n переменными (включая дополнительные и избыточные), где n > m, и все переменные неотрицательны.

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

Введение избыточных переменных (для "≥" ограничений) или наличие раве��ств в исходной задаче часто приводит к тому, что в стандартной форме отсутствует естественный базис (то есть, нет единичной матрицы, соответствующей базисным переменным). В таких случаях для запуска симплекс-метода необходимо искусственно создать начальный базис. Для этого используются искусственные переменные и специальные методы.

М-метод (метод "больших штрафов")

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

Пошаговый алгоритм:

1. Приведение задачи к стандартной форме: Как описано выше.
2. Введение искусственных переменных:
   • Для каждого ограничения-равенства или неравенства типа "≥", где нет базисной переменной (т.е. нет коэффициента 1 при одной из переменных и 0 при остальных в данном уравнении), вводится новая неотрицательная искусственная переменная Ri.
   • Эти Ri переменные формируют начальный единичный базис.
3. Модификация целевой функции:
   • Для задачи максимизации: из целевой функции вычитается произведение очень большого положительного числа M на сумму всех искусственных переменных: F' = F - M ΣRi → max.
   • Для задачи минимизации: к целевой функции прибавляется произведение очень большого положительного числа M на сумму всех искусственных переменных: F' = F + M ΣRi → min.
   • M выбирается настолько большим, чтобы оно доминировало над всеми остальными коэффициентами в целевой функции, "штрафуя" искусственные переменные и вынуждая их к нулю.
4. Решение симплекс-методом: Применяется стандартный симплекс-метод к модифицированной задаче.
5. Анализ результатов:
   • Если в оптимальном плане все искусственные переменные равны нулю, то найден оптимальный план исходной задачи.
   • Если в оптимальном плане хотя бы одна искусственная переменная больше нуля, то исходная задача не имеет допустимых решений.

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

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

Принцип: Этот метод более надёжен и позволяет избежать проблем с выбором M. Он состоит из двух последовательных фаз.

Пошаговый алгоритм:
Фаза 1: Поиск допустимого базисного решения.

1. Приведение задачи к стандартной форме и введение искусственных переменных: Как и в М-методе.
2. Формирование вспомогательной целевой функции: Создается новая целевая функция, представляющая собой сумму всех введенных искусственных переменных: W = ΣRi → min.
3. Решение симплекс-методом: Применяется симплекс-метод для минимизации W.
4. Анализ результатов Фазы 1:
   • Если минимальное значение W* = 0, и все искусственные переменные выведены из базиса (или равны нулю, если остались в базисе), значит, найдено допустимое базисное решение для исходной задачи. Переходим к Фазе 2.
   • Если минимальное значение W* > 0, то исходная задача не имеет допустимых решений. Процесс прекращается.

Фаза 2: Оптимизация исходной целевой функции.

1. Удаление искусственных переменных: Все искусственные переменные и столбцы, им соответствующие, удаляются из симплекс-таблицы.
2. Восстановление исходной целевой функции: Исходная целевая функция F(x) заносится в таблицу с учётом базисных переменных, полученных в Фазе 1.
3. Решение симплекс-методом: Применяется стандартный симплекс-метод к полученной таблице для оптимизации исходной целевой функции F(x).

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

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

Пошаговый алгоритм симплекс-метода

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

1. Составление начальной симплекс-таблицы:
   • В таблице указываются базисные переменные, коэффициенты при всех переменных в ограничениях, свободные члены (P0) и коэффициенты целевой функции (Z-строка или Δ-строка).
   • Коэффициенты целевой функции для базисных переменных должны быть равны нулю в Z-строке после приведения к виду max (-F).
2. Проверка плана на оптимальность (критерий оптимальности):
   • Для задачи максимизации: текущий план оптимален, если все коэффициенты в Z-строке (или Δ-строке, часто обозначаемой как Zj - Cj) неотрицательны (Δj ≥ 0). Это означает, что нет смысла вводить в базис новые переменные, так как это не улучшит целевую функцию.
   • Для задачи минимизации (которая была преобразована в максимизацию -F): все коэффициенты в Z-строке должны быть неотрицательны.
3. Выбор ведущего столбца (вводящей переменной):
   • Если план не оптимален, необходимо ввести в базис новую переменную, которая улучшит значение целевой функции.
   • Для задачи максимизации: выбирается переменная с наибольшим по модулю отрицательным коэффициентом в Z-строке. Столбец этой переменной называется ведущим. (Если задача была min F ≡ max (-F), то выбирается переменная с наибольшим отрицательным значением, что соответствует наибольшему положительному значению в исходной F).
   • Если таких столбцов несколько, можно выбрать любой.
4. Выбор ведущей строки (выводящей переменной):
   • Необходимо определить, какая базисная переменная покинет базис. Для этого для каждого положительного элемента в ведущем столбце вычисляется отношение свободного члена (из столбца P0) к этому элементу.
   • Ведущей строкой считается та, для которой это отношение минимально. Эта строка соответствует переменной, которая покинет базис.
   • Если все элементы ведущего столбца неположительны (≤ 0), то целевая функция неограничена, и задача не имеет конечного оптимального решения.
   • Если минимальное отношение встречается в нескольких строках, выбирается любая из них.
5. Пересчет симплекс-таблицы (Жордановы преобразования):
   • Элемент, находящийся на пересечении ведущего столбца и ведущей строки, называется разрешающим (ведущим) элементом.
   • Ведущая строка делится на разрешающий элемент, чтобы сделать его равным 1.
   • Остальные элементы в ведущем столбце (включая элемент в Z-строке) должны стать 0. Это достигается путём вычитания из каждой строки ведущей строки, умноженной на соответствующий коэффициент ведущего столбца.
   • Эти преобразования формируют новую симплекс-таблицу с новым базисным решением.
6. Повторение шагов: Процесс повторяется, начиная с шага 2 (проверка на оптимальность), до тех пор, пока не будет найден оптимальный план или установлено, что задача не имеет решения.

Экономическая интерпретация результатов симплекс-метода

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

Коэффициенты в Z-строке (Δj) для свободных (небазисных) переменных, когда план оптимален, имеют глубокий экономический смысл. Они называются относительными оценками или теневыми ценами (для ресурсов).

• Для свободной переменной xj: значение Δj показывает, на сколько изменится оптимальное значение целевой функции, если вводить в производство единицу j-го продукта (или увеличить значение xj на единицу), при условии, что этот продукт сейчас не производится. Если Δj < 0 (для максимизации), то введение этой переменной в базис улучшит целевую функцию. Если Δj = 0, то существует альтернативный оптимальный план. Если Δj > 0, то введение этой переменной ухудшит целевую функцию.
• Для дополнительных переменных (si), которые соответствуют ограничениям-ресурсам "≤":
  • Если si > 0 в оптимальном плане, это означает, что i-й ресурс используется не полностью, он является избыточным. Его теневая цена (соответствующая Δi в Z-строке) будет равна нулю, что логично: увеличение доступности избыточного ресурса не принесёт дополнительной пользы.
  • Если si = 0 в оптимальном плане, это означает, что i-й ресурс используется полностью, он является дефицитным. Его теневая цена (соответствующая Δi) будет положительной. Эта теневая цена показывает, на сколько улучшится значение целевой функции (например, увеличится прибыль), если увеличить доступность i-го ресурса на одну единицу, при прочих равных условиях. Это крайне важная информация для принятия управленческих решений, например, о расширении производства или закупке дополнительных ресурсов.

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

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

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

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

Построение двойственной задачи из прямой — это систематизированный процесс, основанный на строгих правилах трансформации.

Предположим, прямая задача (ПЗ) имеет вид:
Максимизировать F(x) = c1x1 + c2x2 + ... + cnxn
При ограничениях:
a11x1 + a12x2 + ... + a1nxn ≤ b1
a21x1 + a22x2 + ... + a2nxn ≤ b2
...
am1x1 + am2x2 + ... + amnxn ≤ bm
xj ≥ 0 для всех j = 1, ..., n.

Тогда двойственная задача (ДЗ) будет строиться следующим образом:

1. Направление целевой функции: Если прямая задача — на максимизацию, то двойственная — на минимизацию, и наоборот. В нашем примере прямая задача на max, значит, двойственная будет на min.
2. Коэффициенты:
   • Коэффициенты целевой функции прямой задачи (cj) становятся свободными членами ограничений двойственной задачи.
   • Свободные члены ограничений прямой задачи (bi) становятся коэффициентами целевой функции двойственной задачи.
3. Матрица коэффициентов: Матрица коэффициентов системы ограничений двойственной задачи (AT) является транспонированной матрицей коэффициентов прямой задачи (A). То есть, строки прямой матрицы становятся столбцами двойственной, и наоборот (aij прямой задачи становится aji двойственной).
4. Количество переменных и ограничений:
   • Число переменных двойственной задачи (yi) равно числу ограничений прямой задачи (m).
   • Число ограничений двойственной задачи равно числу переменных прямой задачи (n).
5. Соотношение знаков (для симметричной пары): Если прямая задача на max F(x) с ограничениями вида "≤" и все xj ≥ 0, то двойственная задача на min G(y) с ограничениями вида "≥", и все yi ≥ 0.

Математическая модель двойственной задачи для нашего примера:
Минимизировать G(y) = b1y1 + b2y2 + ... + bmym
При ограничениях:
a11y1 + a21y2 + ... + am1ym ≥ c1
a12y1 + a22y2 + ... + am2ym ≥ c2
...
a1ny1 + a2ny2 + ... + amnym ≥ cn
yi ≥ 0 для всех i = 1, ..., m.

Для несимметричной пары (смешанные ограничения/переменные):

• Если i-е ограничение прямой задачи является равенством, то i-я переменная двойственной задачи (yi) не ограничена по знаку.
• Если j-я переменная прямой задачи не ограничена по знаку, то j-е ограничение двойственной задачи является равенством.
• Если i-е ограничение прямой задачи типа "≥", а целевая функция на max, то yi ≤ 0 (или его можно преобразовать к стандартному виду с yi' ≥ 0).

Основные теоремы двойственности

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

1. Теорема о слабой двойственности:
   • Для любых допустимых решений x прямой задачи на максимизацию и y двойственной задачи на минимизацию, значение целевой функции прямой задачи всегда меньше или равно значению целевой функции двойственной задачи: F(x) ≤ G(y).
   • Это означает, что любой допустимый план двойственной задачи является верхней границей для оптимального значения целевой функции прямой задачи, и наоборот.
2. Первая теорема двойственности (о сильной двойственности):
   • Если одна из пары двойственных задач имеет оптимальное решение, то и другая задача также имеет оптимальное решение.
   • При этом экстремальные значения их целевых функций равны: max F = min G.
   • Если целевая функция одной из задач неограничена (например, F → ∞), то другая задача не имеет допустимых решений.
   • Это ключевая теорема, которая позволяет найти оптимальное решение одной задачи, решив её двойственную пару.
3. Вторая теорема двойственности (теорема о дополняющей нежесткости):
   • Это самый мощный критерий для проверки оптимальности. Для того чтобы допустимые решения x* прямой задачи и y* двойственной задачи были оптимальными, необходимо и достаточно выполнения следующих условий:
     1. Для каждого ограничения прямой задачи (ai1x1* + ... + ainxn* ≤ bi):
        yi* * (Σj=1n aijxj* - bi) = 0
        Это означает, что если i-е ограничение прямой задачи выполняется как строгое неравенство (то есть Σaijxj* < bi, остаётся неиспользованный ресурс), то соответствующая ему i-я двойственная переменная yi* обязательно равна нулю. И наоборот, если yi* > 0, то i-е ограничение прямой задачи выполняется как равенство (ресурс полностью исчерпан).
     2. Для каждого ограничения двойственной задачи (a1jy1* + ... + amjym* ≥ cj):
        xj* * (Σi=1m aijyi* - cj) = 0
        Аналогично, если j-е ограничение двойственной задачи выполняется как строгое неравенство, то соответствующая ему j-я прямая переменная xj* равна нулю. И наоборот, если xj* > 0 (продукт производится), то j-е ограничение двойственной задачи выполняется как равенство.

Экономический смысл двойственных переменных (yi*) чрезвычайно важен. Они часто интерпретируются как теневые цены или оценки дефицитных ресурсов. Значение yi* показывает, на сколько изменится оптимальное значение целевой функции прямой задачи (например, максимальная прибыль), если увеличить доступность i-го ресурса на одну единицу. Если ресурс избыточен (Σaijxj* < bi), его теневая цена равна нулю, что означает, что дополнительное количество этого ресурса не принесёт выгоды.

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

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

Прямая задача (минимизация стоимости):
Минимизировать F(x) = Σj=1N cjxj (где cj — стоимость продукта j)
При ограничениях:
Σj=1N aijxj ≥ bi (где aij — содержание i-го вещества в продукте j, bi — минимальная потребность в веществе i)
xj ≥ 0

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

1. Направление целевой функции: Прямая на min, значит двойственная на max.
2. Переменные двойственной задачи: yi — по числу ограничений прямой задачи (по количеству питательных веществ).
3. Целевая функция двойственной задачи: G(y) = Σi=1m biyi → max.
4. Ограничения двойственной задачи: По числу переменных прямой задачи (по количеству продуктов). Для каждого продукта j:
   Σi=1m aijyi ≤ cj
yi ≥ 0

Экономический смысл двойственной задачи:
Переменные yi* в данном контексте представляют собой теневые цены питательных веществ. Они показывают, какую "внутреннюю стоимость" имеет каждая единица i-го питательного вещества для системы, чтобы удовлетворить минимальные требования.
Целевая функция G(y) = Σ biyi* будет максимизировать общую "стоимость" всех необходимых питательных веществ, исходя из их теневых цен.

Интерпретация ограничений двойственной задачи:
Σi=1m aijyi ≤ cj
Это ограничение означает, что суммарная теневая стоимость питательных веществ, содержащихся в единице j-го продукта (Σ aijyi), не должна превышать рыночную стоимость cj этого продукта. Если теневая стоимость питательных веществ в продукте ниже его рыночной цены, то этот продукт не будет выгодно использовать (xj* = 0). Если теневая стоимость равна рыночной цене, то продукт выгодно использовать (xj* > 0).

Двойственная задача, таким образом, предоставляет бесценную информацию для анализа чувствительности и оценки ресурсов. Она позволяет понять, какие питательные вещества являются "дефицитными" (их теневые цены > 0) и ограничивают минимизацию стоимости рациона, а какие "избыточны" (теневые цены = 0). Это может помочь в принятии решений о поиске более дешёвых источников дефицитных веществ или корректировке норм питания, что является критически важным для управленческой практики.

Транспортная задача: оптимизация логистики

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

Математическая модель транспортной задачи

Представим m поставщиков (P1, P2, ..., Pm) с запасами a1, a2, ..., am соответственно, и n потребителей (C1, C2, ..., Cn) с потребностями b1, b2, ..., bn. Известна также стоимость cij перевозки единицы груза от поставщика i к потребителю j.

• Переменные задачи:
  Пусть xij — объем груза, перевозимого от поставщика i к потребителю j.
  Очевидно, что xij ≥ 0.
• Целевая функция (минимизация затрат):
  Суммарные затраты на перевозку, которые необходимо минимизировать, определяются как сумма произведений объемов перевозок на соответствующие тарифы:
  Z = Σi=1m Σj=1n cijxij → min
• Ограничения по предложению (запасам):
  Общий объем груза, отправляемого от каждого поставщика i, не должен превышать его запас:
  Σj=1n xij = ai (для i = 1, ..., m)
  Это означает, что весь запас поставщика i должен быть распределён между потребителями.
• Ограничения по спросу (потребностям):
  Общий объем груза, получаемого каждым потребителем j, должен удовлетворять его потребности:
  Σi=1m xij = bj (для j = 1, ..., n)
  Это означает, что потребность потребителя j должна быть полностью удовлетворена поставками от разных поставщиков.

Баланс и несбалансированные задачи

Условие баланса: Фундаментальное условие для разрешимости транспортной задачи заключается в том, что общий объем предложения должен быть равен общему объему спроса:
Σi=1m ai = Σj=1n bj

Если это условие выполняется, задача называется сбалансированной (или закрытой).

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

• Избыток предложения (Σ ai > Σ bj): Если суммарное предложение превышает спрос, вводится фиктивный потребитель с потребностью, равной избытку (bфиктивный = Σ ai - Σ bj). Стоимость перевозок от всех поставщиков к этому фиктивному потребителю принимается равной нулю (ci,фиктивный = 0). Это отражает то, что избыточный груз остаётся на складах поставщиков, не неся дополнительных транспортных расходов.
• Дефицит предложения (Σ ai < Σ bj): Если суммарный спрос превышает предложение, вводится фиктивный поставщик с запасом, равным дефициту (aфиктивный = Σ bj - Σ ai). Стоимость перевозок от этого фиктивного поставщика ко всем потребителям также принимается равной нулю (cфиктивный,j = 0). Это означает, что часть потребностей останется неудовлетворённой, но без дополнительных транспортных издержек.

После введения фиктивных объектов несбалансированная задача становится сбалансированной и может быть решена стандартными методами.

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

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

1. Метод северо-западного угла:
   • Самый простой, но наименее эффективный метод.
   • Заполнение таблицы перевозок начинается с клетки в левом верхнем углу (северо-западном).
   • В эту клетку (x11) записывается максимально возможное значение груза, ограниченное либо запасом первого поставщика (a1), либо потребностью первого потребителя (b1).
   • Если запас поставщика исчерпан, соответствующая строка исключается, и переходят к следующей строке.
   • Если потребность потребителя удовлетворена, соответствующий столбец исключается, и переходят к следующему столбцу.
   • Процесс повторяется до тех пор, пока все запасы не будут распределены, а все потребности не будут удовлетворены.
2. Метод минимального элемента (наименьшей стоимости):
   • Этот метод обычно даёт начальный план, более близкий к оптимальному.
   • В таблице стоимостей (тарифов) выбирается клетка с наименьшим тарифом cij.
   • В эту клетку xij записывается максимально возможное значение груза, ограниченное ai и bj.
   • Строка или столбец, чей запас/потребность исчерпан, исключается из дальнейшего рассмотрения.
   • Процесс повторяется, выбирая наименьший тариф из оставшихся клеток, пока задача не будет полностью решена.
3. Метод аппроксимации Фогеля:
   • Наиболее сложный, но обычно дающий начальный план, который наиболее близок к оптимальному.
   • Для каждой строки и каждого столбца рассчитывается "штраф" — разница между двумя наименьшими тарифами в этой строке/столбце.
   • Выбирается строка или столбец с наибольшим штрафом.
   • В выбранной строке/столбце выбирается клетка с наименьшим тарифом и заполняется максимально возможным объемом груза.
   • Строка или столбец, чей запас/потребность исчерпан, исключается.
   • Процесс повторяется с пересчётом штрафов для оставшихся строк/столбцов, пока задача не будет решена.

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

Метод потенциалов для проверки оптимальности и улучшения плана

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

1. Проверка на вырожденность:
   • Опорный план считается невырожденным, если число заполненных (базисных) клеток равно m + n - 1 (где m — количество поставщиков, n — количество потребителей).
   • Если число заполненных клеток меньше m + n - 1, план вырожден. Для продолжения метода необходимо искусственно добавить нулевые перевозки в свободные клетки, чтобы достичь необходимого количества m + n - 1 занятых клеток. Эти нулевые перевозки выбираются так, чтобы не нарушать циклы и не создавать лишних циклов в базисе.
2. Расчет потенциалов (ui и vj):
   • Каждому поставщику (строке) i присваивается потенциал ui, а каждому потребителю (столбцу) j — потенциал vj.
   • Для всех занятых клеток (xij > 0) должно выполняться условие: ui + vj = cij.
   • Чтобы решить эту систему уравнений, один из потенциалов (например, u1) произвольно принимается равным нулю. Остальные потенциалы рассчитываются последовательно, используя равенство ui + vj = cij для занятых клеток.
3. Расчет оценок для свободных клеток (δij):
   • Для всех незанятых клеток (xij = 0) вычисляются оценки (или неявные тарифы) δij по формуле: δij = ui + vj - cij.
   • (Иногда используется эквивалентное условие проверки ui + vj ≤ cij).
4. Проверка на оптимальность:
   • Если все оценки δij ≤ 0 (или ui + vj ≤ cij для всех свободных клеток), то текущий опорный план является оптимальным. Достигнут минимальный суммарный тариф.
   • Если существует хотя бы одна оценка δij > 0, план не оптимален и может быть улучшен.
5. Улучшение плана (построение цикла пересчета):
   • Выбирается незанятая клетка с наибольшей положительной оценкой δij. Эта клетка является "входящей" в базис.
   • Из этой входящей клетки строится замкнутый цикл пересчета. Цикл состоит из горизонтальных и вертикальных отрезков, углы которого находятся только в занятых (базисных) клетках. Цикл должен быть минимальным по числу углов.
   • Входящей клетке присваивается знак "+θ", затем по циклу чередуются знаки "−θ", "+θ", "−θ" и так далее.
   • Определяется максимальное значение θ, равное минимальному значению перевозок в клетках со знаком "−θ".
   • Значение θ прибавляется к объемам перевозок в клетках со знаком "+" и вычитается из объемов перевозок в клетках со знаком "−". Одна или несколько клеток со знаком "−θ" обнулятся, что приведёт к выходу одной или нескольких переменных из базиса.
   • Таким образом формируется новый опорный план с улучшенным значением целевой функции.
6. Повторение шагов: Процесс повторяется с шага 2 (расчет потенциалов) до достижения оптимального плана.

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

Теория игр: поиск оптимальных стратегий

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

Основные понятия матричной игры

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

• Матричная игра (парная игра с нулевой суммой): Это математическая модель конфликтной ситуации, в которой участвуют два игрока (назовём их Игрок А и Игрок В), каждый из которых имеет конечное число чистых стратегий. Игра называется с нулевой суммой, потому что выигрыш одного игрока в точности равен проигрышу другого, то есть сумма выигрышей всех игроков равна нулю.
• Игрок А (строки): Первый игрок, выбирающий одну из m стратегий, соответствующих строкам платежной матрицы.
• Игрок В (столбцы): Второй игрок, выбирающий одну из n стратегий, соответствующих столбцам платежной матрицы.
• Платежная матрица A = (a_ij): Это таблица размером m × n, где каждый элемент aij представляет собой выигрыш Игрока А (и, соответственно, проигрыш Игрока В) в случае, если Игрок А выбрал стратегию i, а Игрок В — стратегию j.

Пример платежной матрицы 2x2:

      Игрок B
    | B1 | B2
----|----|----
A1  | a11| a12
A2  | a21| a22

Здесь a11 — выигрыш Игрока А, если он выбирает стратегию А1, а Игрок В — стратегию В1.

Чистые стратегии и седловая точка

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

1. Нижняя цена игры (максимин):
   • Игрок А стремится максимизировать свой гарантированный выигрыш. Он рассуждает так: "Какую бы стратегию я ни выбрал, Игрок В попытается нанести мне максимальный ущерб (минимизировать мой выигрыш). Поэтому для каждой своей стратегии i я должен найти минимальный выигрыш (min_j aij), который я могу получить, а затем из этих минимальных выигрышей выбрать наибольший."
   • Нижняя цена игры α = maxi (minj aij). Это называется максиминным критерием. Стратегия, обеспечивающая α, является оптимальной чистой стратегией для Игрока А.
2. Верхняя цена игры (минимакс):
   • Игрок В стремится минимизировать максимальный проигрыш для Игрока А (т.е. свой собственный проигрыш). Он рассуждает так: "Какой бы стратегию я ни выбрал, Игрок А попытается получить максимальный выигрыш. Поэтому для каждой своей стратегии j я должен найти максимальный выигрыш для Игрока А (max_i aij), который он может получить, а затем из этих максимальных выигрышей выбрать наименьший."
   • Верхняя цена игры β = minj (maxi aij). Это называется минимаксным критерием. Стратегия, обеспечивающая β, является оптимальной чистой стратегией для Игрока В.
3. Седловая точка и цена игры:
   • Если нижняя цена игры равна верхней цене игры (α = β), то игра имеет седловую точку.
   • Седловая точка — это элемент aij платежной матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце.
   • Значение α (или β) в этом случае называется ценой игры (ν).
   • Стратегии, соответствующие седловой точке, являются оптимальными чистыми стратегиями для обоих игроков. Если игра имеет седловую точку, игрокам нет смысла отклоняться от своих чистых оптимальных стратегий, поскольку они уже гарантируют наилучший возможный исход при рациональном поведении оппонента.

Смешанные стратегии

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

1. Применение смешанных стратегий: Смешанная стратегия предполагает, что игрок выбирает свои чистые стратегии случайным образом, в соответствии с определённым вероятностным распределением. Это делает действия игрока непредсказуемыми для оппонента.
2. Определение смешанной стратегии:
   • Для Игрока А: вектор P = (p1, p2, ..., pm), где pi ≥ 0 — вероятность выбора i-й чистой стратегии, и Σi=1m pi = 1.
   • Для Игрока В: вектор Q = (q1, q2, ..., qn), где qj ≥ 0 — вероятность выбора j-й чистой стратегии, и Σj=1n qj = 1.
3. Цена игры (ν) при смешанных стратегиях: Это средний (математическое ожидание) выигрыш Игрока А, когда оба игрока придерживаются своих оптимальных смешанных стратегий.

Методы решения матричных игр в смешанных стратегиях

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

1. Графический метод решения для игр 2xN или Nx2:
   • Этот метод применим, когда у одного из игроков всего две чистые стратегии.
   • Для игры 2xN (у Игрока А две стратегии, у Игрока В — N стратегий):
     • Строятся две параллельные оси (например, вертикальные), соответствующие стратегиям Игрока А (А1 и А2). На них откладываются значения выигрышей.
     • Для каждой стратегии j Игрока В на этих осях отмечаются соответствующие выигрыши (a1j на оси А1 и a2j на оси А2), и эти точки соединяются отрезком.
     • Нижняя огибающая этих отрезков представляет собой минимальный гарантированный выигрыш Игрока А при использовании любой смешанной стратегии P = (p1, p2 = 1 - p1). Ось p1 (от 0 до 1) располагается между осями А1 и А2.
     • Наивысшая точка на этой нижней огибающей определяет цену игры (ν). Её абсцисса (значение p1) соответствует оптимальным вероятностям смешанной стратегии Игрока А.
     • Отрезки, проходящие через эту наивысшую точку, соответствуют активным (оптимальным) стратегиям Игрока В. Исходная игра сводится к игре 2x2, образованной этими активными стратегиями, которая затем решается аналитически.
2. Аналитические методы (для игр 2x2 без седловой точки):
   • Если платежная матрица имеет вид A = [[a11, a12], [a21, a22]] и не имеет седловой точки, оптимальные вероятности p1, p2, q1, q2 и цена игры ν вычисляются по следующим формулам (при условии, что знаменатель (a11 + a22 - a12 - a21) ≠ 0):
     • p1 = (a22 - a21) / (a11 + a22 - a12 - a21)
     • p2 = 1 - p1
     • q1 = (a22 - a12) / (a11 + a22 - a12 - a21)
     • q2 = 1 - q1
     • ν = (a11a22 - a12a21) / (a11 + a22 - a12 - a21)
3. Сведение к задачам линейного программирования:
   • Любая конечная матричная игра может быть сведена к паре двойственных задач линейного программирования.
   • Это универсальный метод, который позволяет решать игры любого размера (m x n), хотя он и является более трудоёмким для ручного счёта.
   • Решение этих задач ЛП дает оптимальные смешанные стратегии для обоих игроков и цену игры.

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

Заключение: Сводный анализ и верификация решений контрольной работы

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

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

Сводный анализ и взаимосвязи:

• Оптимизация рациона питания продемонстрировала, как линейное программирование позволяет решать задачи распределения ресурсов (продуктов) для достижения цели (минимизации стоимости) при соблюдении множества ограничений (норм питательных веществ). Её решение даёт не только оптимальный состав рациона, но и, через анализ двойственной задачи, позволяет оценить "ценность" каждого питательного вещества.
• Транспортная задача показала применение ЛП в логистике, фокусируясь на минимизации затрат на перевозки. Здесь методы построения начального плана и метод потенциалов становятся ключевыми. Важно помнить о необходимости балансировки задачи и внимательно следить за вырожденностью при расчёте потенциалов.
• Теория игр раскрыла аспекты принятия решений в условиях конфликта и неопределённости, где действия одного игрока влияют на другого. Поиск седловой точки для чистых стратегий и использование графических или аналитических методов для смешанных стратегий позволяют выработать оптимальные линии поведения в конкурентной среде.

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

1. Проверка математической корректности:
   • Для задач ЛП (графический/симплекс-метод): Подставьте найденные оптимальные значения переменных в исходные ограничения и целевую функцию. Все ограничения должны быть удовлетворены, а значение целевой функции должно соответствовать полученному оптимуму.
   • Симплекс-метод: Убедитесь, что все критерии оптимальности соблюдены (например, все Δj ≥ 0 для максимизации). Если использовались искусственные переменные, они должны быть равны нулю в оптимальном плане (или, для двухфазного метода, вспомогательная целевая функция должна быть равна нулю после первой фазы).
   • Двойственная задача: Проверьте выполнение теоремы о сильной двойственности (max F = min G). Самое главное — примените теорему о дополняющей нежесткости. Это позволит убедиться, что найденные прямые и двойственные решения действительно являются оптимальными и согласованы друг с другом.
   • Транспортная задача: После применения метода потенциалов убедитесь, что все оценки свободных клеток δij ≤ 0. Проверьте баланс между запасами и потребностями.
   • Теория игр: Для чистых стратегий проверьте, что максимин равен минимаксу. Для смешанных стратегий убедитесь, что найденные вероятности суммируются к 1 и что ожидаемые выигрыши для активных стратегий равны цене игры.
2. Экономическая обоснованность и интерпретация:
   • Всегда давайте содержательную интерпретацию полученным результатам. Что означают оптимальные количества продуктов в рационе? Какие ресурсы являются дефицитными в задаче ЛП и какова их теневая цена? Что означают оптимальные маршруты и объемы перевозок в транспортной задаче? Какие стратегии являются наилучшими для игроков в конфликтной ситуации?
   • Анализируйте чувствительность. Как изменится оптимальное решение, если незначительно изменятся коэффициенты целевой функции или правые части ограничений? Это особенно важно при анализе теневых цен, которые показывают предельное изменение целевой функции при изменении ресурса.
   • Убедитесь, что найденные решения имеют смысл в контексте реальной задачи. Например, не может быть отрицательного количества продукта или перевозок.
3. Сопоставление методов (применимо, если возможно):
   • Если задача ЛП с двумя переменными была решена как графическим, так и симплекс-методом, сравните результаты. Они должны полностью совпадать. Это служит отличной перекрестной проверкой.

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

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

1. Методичка СПбГИЭУ / Составители: ст. преп. В. Г. Блинова, канд. техн. наук, доцент Я. В. Войтишек, ст. преп. Е. Н. Зверева.
2. Двойственная задача линейного программирования. URL: https://www.matburo.ru/tv_sub.php?p=dual_lp (дата обращения: 04.11.2025).
3. Лекция 9. Методы решения транспортной задачи. URL: https://www.intuit.ru/studies/courses/102/102/lecture/2916?page=1 (дата обращения: 04.11.2025).
4. Лекция 14. URL: https://www.kstu.ru/servlet/contentblob?id=255734 (дата обращения: 04.11.2025).
5. Галяутдинов, Р. Транспортная задача - решение методом потенциалов // Сайт преподавателя экономики. URL: https://galyautdinov.ru/post/transportnaya-zadacha-reshenie-metodom-potencialov (дата обращения: 04.11.2025).
6. Решение симплекс методом задачи ЛП: пример и алгоритм. URL: https://function-x.ru/simplex_method_example_algorithm.html (дата обращения: 04.11.2025).
7. Правило составления двойственных задач. Симметричная пара. URL: https://www.matburo.ru/tv_sub.php?p=dual_lp_sym (дата обращения: 04.11.2025).
8. Правила построения двойственных задач. URL: https://www.econ.msu.ru/ext/lib/CourseMaterials/578a48b89e625a256e4c70f0/file/lec03-3.pdf (дата обращения: 04.11.2025).
9. Линейное программирование. Симплекс-метод // Решатель. URL: https://reshal.ru/linear-programming/simplex-method (дата обращения: 04.11.2025).
10. Правила составления двойственных задач линейного программирования. URL: https://1cov-edu.ru/linejnoe-programmirovanie/pravila-sostavleniya-dvojstvennyh-zadach-linejnogo-programmirovaniya.html (дата обращения: 04.11.2025).
11. Транспортная задача // Википедия. URL: https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D0%BD%D1%81%D0%BF%D0%BE%D1%80%D1%82%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0 (дата обращения: 04.11.2025).
12. Методы решения транспортной задачи. URL: https://ru.solverbook.com/spravochnik/metody-matematicheskoj-optimizacii/transportnaya-zadacha/metody-resheniya-transportnoj-zadachi/ (дата обращения: 04.11.2025).
13. Алгоритм решения транспортной задачи методом потенциалов. URL: https://studfile.net/preview/4311094/page:4/ (дата обращения: 04.11.2025).
14. Симплекс-метод // Википедия. URL: https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81-%D0%BC%D0%B5%D1%82%D0%BE%D0%B4 (дата обращения: 04.11.2025).
15. Симплекс-метод // Онлайн-калькулятор. URL: https://www.calc.ru/simplex-method.html (дата обращения: 04.11.2025).
16. Этапы решения графического метода задач линейного программирования. URL: https://studfile.net/preview/10243402/page:3/ (дата обращения: 04.11.2025).
17. Лабораторная работа № 4. Тема: «Транспортная задача. Метод потенциалов». URL: https://do.gendocs.ru/docs/index-180020.html (дата обращения: 04.11.2025).
18. Метод потенциалов // Онлайн-калькулятор. URL: https://www.calc.ru/potentials-method.html (дата обращения: 04.11.2025).
19. Симплекс-метод решения задачи линейного программирования. URL: https://www.unn.ru/pages/issues/vestnik/99999999_West_2003_2(1)/29.pdf (дата обращения: 04.11.2025).
20. Алгоритм расчёта потенциалов для ТЗПП // Циклопедия. URL: https://cyclowiki.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%80%D0%B0%D1%81%D1%87%D1%91%D1%82%D0%B0_%D0%BF%D0%BE%D1%82%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D0%BE%D0%B2_%D0%B4%D0%BB%D1%8F_%D0%A2%D0%97%D0%9F%D0%9F (дата обращения: 04.11.2025).
21. Двойственная задача линейного программирования // Хабр. URL: https://habr.com/ru/articles/565780/ (дата обращения: 04.11.2025).
22. Транспортная задача для чайников по шагам за 15 минут. Применение транспортной задачи в экономике. URL: https://www.youtube.com/watch?v=0kF_3v-o07k (дата обращения: 04.11.2025).
23. Решение задач линейного программирования графическим методом // МатБюро. URL: https://www.matburo.ru/ex_ma.php?p=lp_graph (дата обращения: 04.11.2025).
24. Понятие, виды и методы решения транспортной задачи // Международный студенческий научный вестник. URL: https://eduherald.ru/ru/article/view?id=12555 (дата обращения: 04.11.2025).
25. Матричные игры. Платежная матрица, стратегии. Седловая точка, цена игры // 100task. URL: https://100task.ru/teoria-igr/sedlovaya-tochka-cena-igry.php (дата обращения: 04.11.2025).
26. Построение математических моделей. URL: https://moodle.bsut.by/pluginfile.php/14115/mod_resource/content/1/%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F%204.%20%D0%9F%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5%20%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85%20%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B5%D0%B9.pdf (дата обращения: 04.11.2025).
27. Методы оптимизации. Лекция 5: Теория двойственности ЛП. URL: https://www.hse.ru/data/2010/11/02/1225888204/Lec5.pdf (дата обращения: 04.11.2025).
28. Решение матричных игр в смешанных стратегиях // Международный студенческий научный вестник. URL: https://science-education.ru/ru/article/view?id=32599 (дата обращения: 04.11.2025).
29. Симплексный метод решения задач линейного программирования. Основы и примеры. URL: https://economictheory.ru/simplex-method-solution-problems-linear-programming/ (дата обращения: 04.11.2025).
30. Графический метод решения задач линейного программирования // Политехнический Колледж № 50. URL: http://pt50.mskobr.ru/attach_files/upload_users_files/2016-11-20/files/lekciya-po-linejnomu-programmirovaniyu-graficheskij-metod.pdf (дата обращения: 04.11.2025).
31. Симплексный метод решения задач линейного программирования // Habr. URL: https://habr.com/ru/articles/565778/ (дата обращения: 04.11.2025).
32. Лекция 7. Двойственность задачи линейного программирования. URL: https://www.intuit.ru/studies/courses/102/102/lecture/2915?page=1 (дата обращения: 04.11.2025).
33. Алгоритм решения задачи линейного программирования графическим методом. URL: https://studfile.net/preview/5391998/page:3/ (дата обращения: 04.11.2025).
34. Основные теоремы двойственности. URL: https://studfile.net/preview/8061405/page:11/ (дата обращения: 04.11.2025).
35. Решение игр графическим методом. URL: https://www.matburo.ru/tv_sub.php?p=game_graph (дата обращения: 04.11.2025).
36. Научная электронная библиотека. Монографии, изданные в издательстве Российской Академии Естествознания. URL: https://www.monographies.ru/ru/book/section?id=7964 (дата обращения: 04.11.2025).
37. Решение игры в смешанных стратегиях геометрическим методом. URL: https://www.matburo.ru/tv_sub.php?p=game_theory_graph (дата обращения: 04.11.2025).
38. Теория двойственности. URL: https://studfile.net/preview/7926227/page:13/ (дата обращения: 04.11.2025).
39. Симплекс-метод линейного программирования. URL: https://e.sfu-kras.ru/bitstream/handle/2151/15720/galkin.pdf (дата обращения: 04.11.2025).
40. Графический метод решения задачи линейного программирования // Онлайн-калькулятор. URL: https://www.calc.ru/graphical-method.html (дата обращения: 04.11.2025).
41. Математическая модель составления рациона питания // Elibrary. URL: https://www.elibrary.ru/item.asp?id=48600104 (дата обращения: 04.11.2025).
42. Прикладная математика. Пример решения задачи о рационе питания // МатБюро. URL: https://www.matburo.ru/ex_dr_all.php?p1=prmath&p2=diet_lp (дата обращения: 04.11.2025).
43. Глава 7. Элементы теории матричных игр. URL: https://www.unn.ru/pages/issues/vestnik/99999999_West_2004_2(1)/55.pdf (дата обращения: 04.11.2025).
44. Математическое моделирование задачи оптимального рациона // Онлайн-калькулятор. URL: https://www.calc.ru/optim-ration.html (дата обращения: 04.11.2025).
45. Нижняя и верхняя цена игры // Онлайн-калькулятор. URL: https://www.calc.ru/lower-and-upper-value-of-game.html (дата обращения: 04.11.2025).
46. Математическое моделирование. Задача составления рациона (задача о диете, задача о смесях): презентации для подготовки // Инфоурок. URL: https://infourok.ru/matematicheskoe-modelirovanie-zadacha-sostavleniya-raciona-zadacha-o-diete-zadacha-o-smesyah-prezentacii-dlya-podgotovki-na-infour-6003290.html (дата обращения: 04.11.2025).
47. Матричные игры // Википедия. URL: https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D0%B8%D0%B3%D1%80%D1%8B (дата обращения: 04.11.2025).
48. Решение матричных игр в смешанных стратегиях / И.В. Буткевич. Мелитополь // Международный студенческий научный вестник. URL: https://science-education.ru/ru/article/view?id=27055 (дата обращения: 04.11.2025).
49. Графический метод решения матричной игры (2xm). URL: https://studfile.net/preview/10255470/page:19/ (дата обращения: 04.11.2025).
50. Лекция 10 §1. Элементы теории матричных игр. URL: https://www.unn.ru/pages/issues/vestnik/99999999_West_2005_1(1)/63.pdf (дата обращения: 04.11.2025).
51. Симплексный метод решения задач линейного программирования // Онлайн-калькулятор. URL: https://www.calc.ru/simplex-method-solution.html (дата обращения: 04.11.2025).