Сетевое издание

Международный студенческий научный вестник

ISSN 2409-529X

• Авторы
• Файлы
• Литература

Овчинникова О.И. 1 Куликова О.В. 1

---

1 Уральский государственный университет путей сообщения

Статья в формате PDF

339 KB

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

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

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

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

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

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

(1)

(2)

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

(3)

где Х_опт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₂ на положительную величину δ, а c1 оставить без изменения, то линия уровня 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 следует составить ЗЛП₁ и ЗЛП₂ с единой ОДР, которая описывается системой неравенств (9). Величине δ можно, например, присвоить значение, равное 0,5. Математические модели целевых функций L₁(x₁; x₂) и L₂(x₁; x₂) соответственно для ЗЛП₁ и ЗЛП₂ составляются по формулам (6), (7) и принимают с учетом выбранной δ следующий вид

(10)

(11)

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

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

Рис. 2.

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

Библиографическая ссылка