VII Международная студенческая научная конференция Студенческий научный форум - 2015

Линейное программирование рассматривается не только как наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения [4], но и как специальный класс оптимизационных задач, в котором все отношения между переменными выражаются линейными функциями, а переменные принимают действительные значения [1]. Основоположниками линейного программирования считаются Л.В. Канторович (1912-1986) и Д. Данциг (1914-2005). Впервые задача линейного программирования (ЗЛП) в России была сформулирована в 1939 г. Л.В. Канторовичем, который применил математическую модель этой задачи в экономике и разработал метод решения. В 1975 г. Л.В. Канторович получил Нобелевскую премию за достижения в этой области [2]. В 1947 г. американский ученый Д. Данциг разработал алгоритм решения ЗЛП [1].

Математическая модель ЗЛП [4] имеет вид

Содержание ЗЛП формулируется следующим образом: необходимо найти набор действительных чисел (вектор) Х_опт = (х₁, х₂, ..., х_n), доставляющий экстремум (максимум или минимум) линейной целевой функции (1) и удовлетворяющий системе ограничений (2). ЗЛП может иметь одно или множество оптимальных решений Х_опт, которые называются альтернативным отпимумом [4]. Выявление альтернативного оптимума в решении ЗЛП представляется важным условием понимания существенных взаимосвязей, обеспечивающих достижение целевой функцией оптимального значения. При изучении ЗЛП с двумя переменными обязательно рассматривается графический способ ее решения. Критерием альтернативного оптимума в этом случае выступает совпадение оптимальной линии уровня целевой функции L_опт с одной из сторон многоугольника области допустимых решений (ОДР), а оптимальное решение Х_опт находится по формуле

где Х_опт1 и Х_опт2 - оптимальные решения в угловых точках области допустимых решений (ОДР); 0 ≤ t ≤ 1; (х_опт11; х_опт12) и (х_опт21; х_опт22) - координаты угловых точек ОДР [4].

Развитие программного обеспечения современных компьютеров расширяет способы решения задач оптимизации в учебном процессе. Программа «Поиск решения» электронных таблиц Excel позволяет в автоматическом режиме находить только одно оптимальное решение Х_опт и значение целевой функции L(Х_опт) [3]. Если ЗЛП имеет единственное решение, то данная программа определяет его однозначно. Если ЗЛП имеет альтернативный оптимум, то пользователю становится известно одно частное решение. В отчете о результатах вычислений данная программа сигнализирует о множестве оптимальных решений, отмечая в статусе одной из функциональных зависимостей системы ограничений связанность с целевой функцией (если ЗЛП с двумя переменными имеет единственное решение, то связанность с целевой функцией фиксируется у двух функциональных зависимостей системы ограничений). Составление множества Х_опт становится возможным, если моделируются ситуации, при которых обеспечивается достижение условий для использования формулы (3).

Проведем анализ математической модели ЗЛП с двумя переменными и альтернативным оптимумом, которая имеет следующий вид

? (4)

? (5)

Коэффициенты переменных в одном из неравенств системы ограничений пропорциональны коэффициентам целевой функции, что и определяет характерное расположение линии уровня целевой функции L_опт и одной из сторон М₁М₂ многоугольника ОДР (рис. 1).

Рис. 1. Граница ОДР (ОДР располагается ниже отрезка М₁М₂)

Угловой коэффициент k прямой L_опт равен отношению коэффициентов целевой функции (k = c₂/c₁). Если увеличить c₁ на положительную величину δ, а c₂ оставить без изменения, то линия уровня L_опт совершит поворот по ходу часовой стрелки и примет положение, которое на рис. 1 отмечено как L_опт2. При таком изменении целевой функции (4) ЗЛП будет иметь одно оптимальное решение, которому будут соответствовать значения координат точки М₂ (рис. 1). Если увеличить c₂ на положительную величину δ, а c₁ оставить без изменения, то линия уровня L_опт совершит поворот против хода часовой стрелки и примет положение, которое на рис. 1 отмечено как L_опт1. При этом изменении целевой функции (4) ЗЛП будет иметь также одно оптимальное решение, которому будут соответствовать значения координат точки М₁ (рис. 1). Нахождение координат точек М₁ и М₂, которые являются угловыми в ОДР, позволяет составить множество Х_опт при использовании формулы (3). Установление Х_опт ЗЛП, заданной математической моделью (4)-(5), с помощью программы «Поиск решения» требует определения Х_опт1 и Х_опт2, которые относятся к ЗЛП1 и ЗЛП2. Система ограничений ЗЛП1 и ЗЛП2 описывается системой неравенств (5). Математические модели целевых функций L₁(X) и L₂(X) этих задач соответственно будут иметь вид

(6)

(7)

Иллюстрация изложенной выше идеи о применении программы «Поиск решения» для нахождения альтернативного максимума осуществляется на примере решения ЗЛП, которая представлена математической моделью

? (8)

? (9)

Функциональные зависимости (8) и (9) вводятся в ячейки электронного процессора Excel, а в соответствующих разделах диалогового окна программы «Поиск решения» фиксируются их адреса. Автоматический поиск Х_опт и L(Х_опт) завершается сообщением результата: х₁ = 0,8; х₂ = 1,6; L(0,8; 1,6) = 20. Для определения Х_опт1 и Х_опт2 следует составить ЗЛП1 и ЗЛП2 с единой ОДР, которая описывается системой неравенств (9). Величине δ можно, например, присвоить значение, равное 0,5. Математические модели целевых функций L₁(x₁; x₂) и L₂(x₁; x₂) соответственно для ЗЛП1 и ЗЛП2 составляются по формулам (6), (7) и принимают с учетом выбранной δ следующий вид

? (10)

? (11)

Результат работы программы «Поиск решения» для ЗЛП1 и ЗЛП2: Х_опт1 = (0; 2), L₁(0; 2) = 21, Х_опт2 = (2; 1), L₂(2; 1) = 21. Нахождение Х_опт1 и Х_опт2 позволяет записать множество всех оптимальных решений ЗЛП (8)-(9) по формуле (3) в матричном виде

?

Проверка полученного результата (12) может проводиться через его сравнение с результатом, к которому приведет применение другого способа решения ЗЛП. Использование графического способа решения [4] ЗЛП (8)-(9) отражено на рис. 2.

Рис. 2. Линия уровня целевой функции L_опт и ОДР

Четырехугольник М₁М₂М₃М₄ - это ОДР системы ограничений (9) (рис. 2), сторона М₂М₃ совпадает с оптимальной линией уровня целевой функции L_опт(Х_опт) = 20. Координаты вершин М₂(0; 2) и М₃(2; 1) определяют оптимальные решения Х_опт1 и Х_опт2, а их подстановка в формулу (3) подтверждает ранее полученный результат Х_опт (12). Нахождение множества оптимальных решений ЗЛП с двумя переменными при использовании программы «Поиск решения» требует соблюдения условий (составление и решение ЗЛП1 и ЗЛП2), рассмотренных в данной работе.

1. Алексеева Е.В. Построение математических моделей целочисленного линейного программирования. Примеры и задачи: учеб. пособие / Новосиб. Гос. ун-т. Новосибирск, 2012. 131 с.

2. Вершик А.М. Леонид Витальевич Канторович: человек и ученый: В 2 т. Новосибирск: Изд-во СО РАН. Филиал «Гео», 2002. Т.1.

3. Вуколов Э.А. Основы статистического анализа. Практикум по статситическим методам и исследованию операций с использованием пакетов STATISTICA и EXCEL: учеб. пособие. - 2-е изд,, испр. и доп. - М.: ФОРУМ, 2008. 464 с.

4. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании: учеб. пособие. Издательство: Дело, 2008 г. 688 с.