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

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

Прочие статьи цикла

1. Исследование операций
2. Метод ветвей и границ. Задача коммивояжера
3. Симплексный метод решения задач линейного программирования
4. Симплексный метод решения ЗЛП. Пример
5. Двойственная задача линейного программирования
6. Транспортная задача линейного программирования
7. Задача выбора (назначения). Венгерский метод решения
8. Управление запасами

Транспортная задача линейного программирования относится к перечню классических задач, решаемых в практике деятельности людей. Эта задача методами классической математики не решается. В задаче необходимо отыскивать экстремум целевой функции. В задаче целевая функция – линейная. Ограничения на переменные (их может быть очень много) описываются также линейными зависимостями. Казалось бы чего проще. Но как раз ограничения и порождают трудности, связанные не просто с поиском max и min при отсутствии ограничений, а с необходимостью учета таких ограничений. Искать требуется не просто экстремум, а условный экстремум. Методы решения задачи позволяют учитывать особенности структуры задачи и даже отказаться от симплексного метода решения в чистом виде.

I. Основные параметры, термины и обозначения

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

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

В теории в тексте задачи Хичкока ничего не говорится о равенстве имеющегося общего запаса судов в портах отправления и общей потребности в судах в портах прибытия (назначения). Если такого равенства нет, то система ограничений несовместна. В случае равенства

транспортная задача называется «сбалансированной». Задачи, в которых условие баланса не задано, должны быть приведены к «сбалансированному» виду. Это можно выполнить использованием «фиктивных» перевозок. Рассматриваем два случая:

Поэтому ранг системы равен не n+m, а n+m – 1, т.е с mn неизвестными. Общее число опорных планов равно числу сочетаний из mn по n+m – 1.. Применение симплекс метода для решения задачи возможно, но требует большого объема вычислений уже при n и m ≈ 10 -15. Заметим также, что каждая неизвестная входит лишь в два уравнения системы (матрица коэффициентов системы ограничений имеет в каждой строке и каждом столбце только два ненулевых элемента). Более того, транспортная задача всегда имеет допустимое решение. Все сказанное вызвало потребность попытаться учесть специфику задачи и создать метод ее решения более простой, чем симплекс метод. Такие методы были найдены и получили названия метода потенциалов и распределительного метода. Это разновидности симплексного метода. Они удобно реализуются, если условие задачи представлено в виде таблиц.

ТАБЛИЦА 1 — Вид данных транспортной задачи линейного программирования

Метод содержит три последовательных этапа:

1. Формирование опорного плана;
2. Проверка опорного плана на оптимальность;
3. Переход к новому опорному плану, если предыдущий не оптимален.

II. Формирование опорного плана перевозок

Рассмотрим способ получения начального опорного плана транспортной задачи, названный способом северо-западного (С-З) угла. Способ заключается в заполнении ячеек таблицы m×n значениями переменной x_ij, таким образом, чтобы удовлетворялись условия задачи. При этом план решения Х[m, n] может быть и не оптимальным, но обязательно должен быть допустимым.

В этом способе формируют опорный план, двигаясь по таблице: сверху вниз по строкам и слева направо вдоль строки. Начинают с левого верхнего угла (ячейки), куда вписывают значение x₁₁ =mina₁, b₁>.Первые строка и столбец из рассмотрения далее исключаются.

Затем, если a₁ > b₁, то определяется остаток (a₁ – b₁) продукта на первом пункте отправления и его запас реализуется на 2-м пункте назначения. Остаток потребностей 2-го пункта назначения удовлетворяется за счет 2-го пункта отправления, остатки которого направляются в 3-й пункт назначения и т.д. Ниже метод будет иллюстрирован числовым примером.

Пример 1. Построение опорного плана методом Северо-Западного угла

Заданы значения: m = 3, n = 4; a₁ = 60, a₂ = 80, a₃ =100, b₁ = 40,b₂ = 60, b₃ = 80, b₄ = 60. Слева в таблице приведены d_ij удельные стоимости перевозок; справа — В_ij стоимости совместно с предложениями a_i и потребностями b_{j .}

Требуется найти план Х [m,n] перевозок, удовлетворяющий условиям на целевую функцию Q и переменные х_ij задачи Q.

РЕШЕНИЕ Построить исходный опорный план способом северо-западного угла. Строим симплексную таблицу: Таблица 3. Опорный план задачи

В таблице способом северо-западного угла получен опорный план. Базисные переменные (их число = 6): x₁₁ = 40, x₁₂= 20, x₂₂= 40, x₂₃= 40, x₃₃= 40, x₃₄= 60. Свободные переменные: x₁₃= x₁₄= x₂₁= x₂₄= x₃₁= x₃₂= 0 (их число равно 6).

Ячейки таблицы, соответствующие базисным переменным, называют базисными, остальные – свободными. Далее в алгоритме будем следовать идее симплекс метода. Суммарная стоимость перевозок Q, соответствующая плану Х[m,n], получает представление

Q = d₁₁∙x₁₁ + d₁₂∙x₁₂ + d₂₂∙x₂₂ + d₂₃ ∙x₂₃+ d₃₃ ∙x₃₃+ d₃₄ ∙x₃₄ = = 5∙40 + 2∙20 + 10∙40 + 2∙40 + 8∙40 + 5∙60 = 200+40+400 + 80 + 320+ 300 = 1340 ед

Коэффициенты d_ij называются фиктивными или косвенными стоимостями; их выражают через косвенные величины α и β, d’_ij = α_i +β_j . Здесь параметры α_i и ( — β_j ), по аналогии с механикой называют потенциалами i-го пункта отправления и j-го пункта прибытия. Значения потенциалов определяется из системы линейных уравнений: α_i + β_j = d_ij

Каждому из таких уравнений соответствует какая-либо базисная переменная х_ij Система уравнений с потенциалами содержит m+n неизвестных потенциалов, число же уравнений равняется числу базисных ячеек таблицы, т.е. (m + n – 1). Следовательно, один из потенциалов можно задать произвольно, положив его равным, например, нулю.

Решая далее систему уравнений для потенциалов, находим значения потенциалов строк и столбцов, все фиктивные стоимости d_ij и коэффициенты γ_ij. Если для всех свободных клеток γ_rs ≤ 0, то перевод в базис любой свободной переменной не уменьшит значения целевой функции и, следовательно, выбранный опорный план не является оптимальным. Если же некоторые γ_rs >0, то данный план можно улучшить путем перевода в базис свободной переменной, соответствующей max γ_rs, а также путем исключения из базиса, принадлежащей ему переменной, первой обращающейся в нуль. Переход к новому опорному плану и поиск оптимального плана рассмотрим на примере. Другой способ формирования опорного плана предложен Фогелем. Этот способ при первом чтении можно пропустить, так как дальше он в тексте не используется.

Пример 2. Способ аппроксимации Фогеля

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

Этапы алгоритма: 1. Вычисление разностей в каждой строке и в каждом столбце между наименьшей стоимостью и ближайшей к ней по величине. Разности по строкам записываются справа в столбце разностей, разности по столбцам – внизу в строке разностей. Например, для строк А₁ разность равна А₁В₂ – А₁В₃ = 38 – 24 = 14 и т. д.

ТАБЛИЦА 2 — Метод Фогеля для получения опорного плана транспортной задачи

2. Поиск из всех разностей, как по строкам, так и по столбцам максимальный. В нашем примере максимальная разность равна 38 и находится в строке А₂. Обведем максимальную разность рамкой.

3. Размещение в клетку, где находится наименьшая стоимость (А₂В₂ = 18) (строка с наибольшей разностью), максимально возможного количества ресурсов. Оно равно 20, т.е. всему ресурсу отправителя А₂. Поскольку все ресурсы отправителя А₂ исчерпаны, строку А₂ исключаем из дальнейших расчетов, для чего отметим все клетки этой строки точками.

4. Вычисление разностей столбцам и строкам, не принимая во внимание стоимость в клетках, имеющих ресурсы и клетках с точкой (исключенную строку или столбец) и определение максимальной разности в строке или столбце (В₃ = 76).

5. Поиск минимального элемента в строке или в столбце с максимальной разностью (А₁В₃ = 24) и размещения в данную клетку максимально возможного количества ресурса, возвращение к этапу №4 и т.д. Окончательно

ЦФ Q=23∙19 + 7∙3 + 20∙18 + 2∙10 + 14∙24 + 1∙100 +3∙48 = = 437 + 21 + 360 + 20 +3 36 + 100 + 272 =1546 ед. Это значение соответствует опорному плану Фогеля.

III. Транспортная задача линейного программирования

Как основной метод решения транспортной задачи – используется метод потенциалов. Ни симплексный метод, ни распределительный метод здесь не рассматриваются. У них имеются свои плюсы и минусы, но объем изложения достаточно велик. Возможно этому позднее я уделю внимание и время, но пока отвечаю на пожелание читателя Хабра.

Пример 3 — Транспортная задача. Метод потенциалов

Исходные данные задачи удобно представить двумя матрицами.

ТАБЛИЦА — Исходные данные

Требуется найти план Х [m,n] перевозок, удовлетворяющий условиям на целевую функцию Q и переменные х_ij задачи

Решение задачи:

1. Формирование начального опорного плана способом Северо-Западного угла.

Базисные n + m – 1 = 3 + 4 – 1 = 6 переменные:
x₁₁ =70, x₁₂ = 20, x₂₂ = 10, x₂₃ = 20, x₂₄ = 0, x₃₄ = 40.
Остальные переменные nm – n + m – 1 = 12 – 6 = 6 свободные:
x₁₃ = x₁₄ = x₂₁ = x₂₄ = x₃₁= x₃₂ = 0 .
Суммарная стоимость перевозок для опорного плана получает представление:
Q = d₁₁ ∙x₁₁ + d₁₂∙x₁₂ + d₂₂∙x₂₂ + d₂₃∙x₂₃+ d₂₄∙x₂₄+ d₃₄∙x₃₄ =
=2∙70 + 3∙20 + 3∙10 + 1∙20 + 2∙0 + 2∙40 = 140 + 60 + 30 + 20 + 0 +80 = 330 ед.

2. Проверка опорного плана на оптимальность

Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов. Определим систему уравнений для потенциалов и вычислим их значения:

α₁ + β₁ = d₁₁ = 2;
α₁ + β₂ = d₁₂ = 3;
α₂ + β₂ = d₂₂ = 3;
α₂ + β₃ = d₂₃ = 1;
α₂ + β₄ = d₂₄ = 2;
α₃ + β₄ = d₃₄ = 2.

Каждое из этих значений соответствует одной базисной ячейке. Одну из неизвестных в системе можно задавать произвольно. Пусть β₁ = 0. Тогда после решения системы получены значения потенциалов: α₁= 2, α₂= 2, α₃= 2, β₁ =0, β₂=1, β₃ =–1, β₄ =0,

Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].

Выделяем в Г [m, n] свободные ячейки, содержащие γ_rs. Проверяем наличие положительных переменных γ_i,j > 0. Так как в матрице (в свободных ячейках) имеем γ₃₂ = 2 > 0, то исходный опорный план может быть улучшен, он не является оптимальным.

3. Переход к новому (улучшенному) опорному плану

Переменную x₃₂ =x следует ввести в базис. Обозначим ее предварительно через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся начальным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок

Обозначим ее предварительно через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся начальным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок Очевидно, что наибольшее x определяется теми x_ij в базисных клетках, из которых этот х вычитается. Следовательно, x₁₁ = min22, х₃₄> = = 10. При x >10 перевозка х₂₂ становится отрицательной. Переменную х₂₂ исключаем из базиса и переводим ее в разряд свободных переменных. Далее повторяются рекурсивно три пункта алгоритма.

1. Получаем из модифицированного плана новый опорный план В нем объемы перевозок распределены иначе чем в начальном опорном плане.

Суммарная стоимость перевозок для этого опорного плана получает представление:
Q = d₁₁ ∙x₁₁ + d₁₂∙x₁₂ + d₂₃∙x₂₃ + d₃₂∙x₃₂ + d₂₄∙x₂₄+ d₃₄∙x₃₄ =
=2∙70 + 3∙20 + 2∙10 + 1∙20 + 1∙10 + 2∙30 = 140 + 60 + 20 + 20 + 10 + 60 = 310 ед. Затраты на перевозки при этом плане уменьшились на 330 – 310 = 20 ед.

Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов.

2. Проверка опорного плана на оптимальность

Определим систему уравнений для потенциалов и вычислим их значения:
α₁ + β₁ = d₁₁ = 2;
α₁ + β₂ = d₁₂ = 3;
α₂ + β₃ = d₂₃ = 1;
α₂ + β₄ = d₂₄ = 2;
α₃ + β₂ = d₃₂ = 1;
α₃ + β₄ = d₃₄ = 2.

Каждое из этих значений соответствует одной базисной ячейке. Одну из неизвестных в системе можно задавать произвольно. Пустьα₁ = 0. Тогда после решения системы получены значения потенциалов: α₁= 0, α₂= – 2, α₃= –2, β₁ =2, β₂=3, β₃ = 3, β₄ =4.

Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].

Свободные ячейки матрицы Г [m, n] содержат γ_i,j > 0 (γ₁₄ = 1>0). План не оптимален.

3. Переход к новому (улучшенному) опорному плану

Из свободных переменных с x_ij > 0, выбираем одну x₁₄ для введения ее в базис. Обозначим ее как и ранее через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся очередным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок

Очевидно, что наибольшее x определяется теми x_ij в базисных клетках, из которых этот х вычитается. Следовательно, x₁₁ = min12, х₃₄> = = 20. При х₁₂ >20 перевозка х₁₂ становится отрицательной. Переменную х₁₂ исключаем из базиса и переводим ее в разряд свободных переменных. Переходим к новой итерации

1. Получаем из модифицированного плана новый опорный план.

В нем объемы перевозок распределены иначе чем в предшествующем опорном плане.

Суммарная стоимость перевозок для этого опорного плана получает представление:
Q = d₁₁ ∙x₁₁ + d₁₄∙x₁₄ + d₂₃∙x₂₃ + d₃₂∙x₃₂ + d₂₄∙x₂₄+ d₃₄∙x₃₄ =
=2∙70 + 3∙20 + 1∙20 + 2∙10 + 1∙30 + 2∙10 = 140 + 60 + 20 + 20 + 30 + 20 = 290 ед. Затраты на перевозки при этом плане уменьшились на 310 – 290 = 20 ед. Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов.

2. Проверка опорного плана на оптимальность

Определим систему уравнений для потенциалов и вычислим их значения:
α₁ + β₁ = d₁₁ = 2;
α₁ + β₄ = d₁₄ = 3;
α₂ + β₃ = d₂₃ = 1;
α₂ + β₄ = d₂₄ = 2;
α₃ + β₂ = d₃₂ = 1;
α₃ + β₄ = d₃₄ = 2. Каждое из этих значений соответствует одной базисной ячейке. Одну из неизвестных в системе можно задавать произвольно. Пусть β₁ = 0. Тогда после решения системы получены значения потенциалов: α₁= 2, α₂= 2, α₃= 2, β₁ =0, β₂=1, β₃ =–1, β₄ =0.

Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].

При переходе к новому опорному плану проверяем наличие положительных свободных переменных γ_i,j >0. Но таких переменных не оказалось. Отсюда следует вывод, что полученный последним модифицированный план является оптимальным и ему соответствует значение линейной формы
Q’= 2∙70 + 3∙20 + 1∙20 + 2∙10 + 1∙30 + 2∙10 = 290.

Заключение

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

1. Ваулин А. Е. Методы цифровой обработки данных.– СПб.: ВИККИ им. А. Ф. Можайского, 1993.– 106 с.
2. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.
3. Корбут А.А., Финкельштейн Ю. Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.
4. Макаров И. М. и др. Теория выбора и принятия решений.– М.: Наука, 1982.– 328 с.
5. Пфанцагль И. Теория измерений. – М.: Наука, 1988.–384 с.
6. Таха Х. А. Введение в исследование операций. 7-е изд. М.: Изд. дом «Вильямс», 2005.
7. Фишберн П. С. Теория полезности для принятия решений. – М.: Наука,1978. –352 с.

• пункты отправления
• пункты прибытия
• линейное программирование
• линейное пространства
• ограничения

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

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

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

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

Типичной задачей линейного программирования является следующая: найти максимум линейной функции

Задачи линейного программирования являются математическими моделями задач технико-экономического содержания. Например: предприятие может выпускать n видов продукции; прибыльность единицы продукции вида j, j=1, . n, составляет cj. В производстве используются ресурсы m видов (сырье, рабочая сила, энергия и т.п.). Наличие ресурса i, i=1, . m, ограничено величиной bi. Расход ресурса i на производство единицы продукции вида j составляет aij. Требуется найти объемы выпуска xj по каждому из видов продукции таким образом, чтобы лимиты по ресурсам не были превышены, а суммарная прибыль была бы максимальной. Запись этих требований приводит к задаче (1)-(3).

Причем данную функцию (1) принято называть целевой функцией (или критерием оптимальности, критерием эффективности), а условия (2) и (3) — ограничениями данной задачи. Совокупность чисел X=(x1, x2, . xn) , удовлетворяющих ограничениям задачи, называется допустимым решением задачи (или планом). План, при котором целевая функция задачи принимает свое максимальное (минимальное) значение, называется оптимальным.

Приступая к решению задачи необходимо создать ее математическую модель.

Для построения математической модели необходимо ответить на следующие три вопроса [1]:

1. Что является искомыми величинами, то есть переменными этой задачи?

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

3. Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, описанные в задаче?

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

Условие задачи: Необходимо составить план раскроя с минимальными отходами изделий двух видов. Потребность в изделии первого вида не менее 20 шт., второго — не менее 30 шт.

Введем переменные x1 — количество листов, раскроенных по первому типу, x2 — количество листов, раскроенных по второму типу, x3 — количество листов, раскроенных по третьему типу. Тогда 24∙x1 — стоимость отходов с листов, раскроенных по первому типу, 16∙x2 — стоимость отходов с листов, раскроенных по второму типу, 24∙x3 — стоимость отходов с листов, раскроенных по третьему типу. В результате получим целевую функцию

Учитывая, что потребность в изделии первого вида не менее 20 шт., второго — не менее 30 шт., получим ограничение 2:∙x1 + 1∙x2 + 3∙x3 ≥ 20, аналогично 1:∙x1 + 2∙x2 + 0∙x3 ≥ 30 получается второе ограничение. На переменные накладывается условие неотрицательности.

Таким образом, получим следующую математическую модель:

Решение задачи с помощью OpenOffice.org Calc

Запустите программу OpenOffice.org 3.1.1 Calc (Программы, задачи и сеансы — Офис — Электронная таблица (OpenOffice.org)) и создайте новую книгу. Далее подготовьте исходные данные на листе OpenOffice.org (вставьте необходимые коэффициенты, значения целевой функции, значения свободных членов и в столбец F вставьте функции SUMPRODUCT с абсолютной адресацией на строку 2, где будут отображены искомые значения x).

Выберите команду Сервис-Поиск решения, в появившемся диалоговом окне (рис.1) вводим следующие значения:

Рис. 1. Диалоговое окно «Поиск решения».

— в поле «Целевая ячейка» вводим адрес ячейки $F$3, в данной ячейке будет найдено оптимальное решение функции;

— в поле «Оптимизация результата» выбираем «Минимум»;

— в поле «Путем изменения ячеек» вводим диапазон ячеек $В$2:$D$2, в которых будут отображены искомые значения неизвестных х1, х2, х3;

— Вводим ограничительные условия $F$5>=$G$5, $F$6>=$G$6. В ячейках F5 и F6 появятся значения левых частей ограничений.

— Щелкаем по кнопке «Параметры» и ставим «Принять переменные как не отрицательные».

— Выполним процедуру, щелкнув по кнопке «Решить».

Если решение будет найдено, то появится сообщение: «Процесс решения успешно завершен».

Рис. 2. Диалоговое окно «Результат».

Выбрав «Сохранить результат», получим таблицу результатов.

Рис. 3. Таблица с результатом решения задачи.

Таким образом, для получения минимальных отходов необходимо: 15 листов раскроить по второму способу, 1,7 листов раскроить по третьему способу. Минимальная стоимость отходов 280.

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

1. Что такое математическое и линейное программирование?
2. Какие задачи являются задачами линейного программирования?
3. Что представляют собой целевая функция, план и ограничения задачи?
4. Какой план называется оптимальным?
5. В чем заключается построение математической модели решения задачи линейного программирования?
6. Каким образом решается задача с помощью OpenOffice.orgCalc?

Список литературы:

1. Алесинская Т.В., Сербин В.Д., Катаев А.В. Учебно-методическое пособие по курсу «Экономико-математические методы и модели. Линейное программирование». Таганрог: Изд-во ТРТУ, 2001. 79 с.
2. Математический энциклопедический словарь. / Гл. ред. Ю.В. Прохоров; Ред. кол.: С.И. Адян, Н.С. Бахвалов, В.И. Битюцков, А.П. Ершов, Л.Д. Кудрявцев, А.Л. Онищик, А.П. Юшкевич. — М.: Сов. энциклопедия, 1988. — 847 с.

Издатель журнала: Можаров Максим Сергеевич

Адрес: 654027, Кемеровская обл., г. Новокузнецк, пр. Пионерский, 13

2016-2018 © Электронный научный журнал «Информационно-коммуникационные технологии в педагогическом образовании» зарегистрирован Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций. Свидетельство о регистрации: ЭЛ № ФС 77 — 67119 от 16.09.2016

СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СТРОИТЕЛЬСТВЕ Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Маркелова И. В., Данилов А. М.

Рассматриваются некоторые приложения линейного программирования для решения задач в строительной отрасли.

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Маркелова И. В., Данилов А. М.

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ПРИ РЕШЕНИИ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫХ ЗАДАЧ

Разработка альтернативных решений по организации систем наружного пожаротушения на объектах капитального строительства

ДВОЙСТВЕННАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ РАСПРЕДЕЛЕНИИ РЕСУРСОВ
РЕКОНСТРУКЦИЯ ВОДОСНАБЖЕНИЯ Г. ИГАРКИ КРАСНОЯРСКОГО КРАЯ
Когнитивное моделирование образовательной системы
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СТРОИТЕЛЬСТВЕ»

И.В. Маркелова, А.М. Данилов

СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СТРОИТЕЛЬСТВЕ

Рассматриваются некоторые приложения линейного программирования для решения задач в строительной отрасли.

Ключевые слова: строительство, оптимизационные задачи, линейное программирование.

Известны практические задачи [1, 2], при решении которых эффективно использовались методы математического программирования (в частности, для повышения нефтедобычи на Ак-танышском месторождении Татарстана). К сожалению, указанные методы для решения архитектурно-строительных задач используются редко до настоящего времени. Ниже приводится ряд возможных приложений.

1.Оптимальное размещение головных сооружений

Имеются три площадки для размещения головных предприятий: 1, 2 — для забора подземных вод; 3 — для забора поверхностных вод. Требуется разместить головные водопроводные сооружения для подачи воды трём потребителям с заданными расходами: 1 потребитель — Gl = 30000 м3/сутки; 2 потребитель — G2 =20000 м3/сутки; 3 потребитель — G3 =40000 м3/сутки. При

этом максимальные производительности водозаборов для 1-й и 2-й площадки не должны превышать 20000 м3/сутки. Стоимость водозаборных сооружений для поверхностных вод (водозабор, очистные сооружения) — d3 =37 тыс.руб/м3; стоимость водозаборных сооружений для забора подземных вод dx = d2 = 50 тыс. руб/ м3. Расстояния ^ между потребителями и площадками для водозаборных сооружений приведены на рис. 1. Определить оптимальные производительности x, x2, x3 водозаборов и транспортируемое из пункта P в пункт P количество воды x , обеспечивающие наименьшую стоимость сооружений, если подача 1 м3 на 1 км обходится:

a = 25 тыс.руб — с первой площадки; a2 =20 тыс.руб — со второй площадки; a3=10 тыс.руб — с третьей площадки.

Таким образом, целью решения является минимизация целевой функции

f = Z j + ZZ ajx1j ; Z Xj = G, Z Xj = Xj, Xj > 0, x, < 20000, k = 1,2.

Получили типичную задачу линейного программирования.

2. Оптимальное размещение сети культурно-бытового обслуживания Пусть известны численность A населения города и численность В населения, обслуживаемого культурно-бытовыми учреждениями. Должны иметь B=A. Пусть далее:

n — число жилых районов города, j — номера районов, aj — население j-го района, m —

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

но-бытовым центром, Z b = B (A = Z a = Z b = B), с^ — минимальные затраты времени

© Маркелова И.В., Данилов А.М., 2014.

Вестник магистратуры. 2014. №5(32). Том I

на передвижение из каждого /-го населённого места в каждый 7-й центр культурно-бытового обслуживания.

Рис. 1. Расстояния между потребителями и площадками для водозаборных сооружений

Требуется определить численность х^ населения /-го жилого района, обслуживаемого

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

Снова пришли к задаче линейного программирования: из условий минимума

требуется определить значения х при ограничениях

f=Ё xj =b-‘ Ё xj = aj’ xj -0 •

3. Распределение выпуска продукции по предприятиям

Предполагается за время Т выпуск I видов продукции Д,ДД на г однородных

предприятиях П,П>.••>П соответственно в количествах N,N. N штук. При этом ни

одно предприятие не может одновременно выпускать несколько видов продукции. Пусть известны:

Время работы каждого предприятия не должно превышать Т:

Количество выпускаемой продукции должно соответствовать номенклатуре:

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

Здесь целевая функция представляет собой общую стоимость выпущенной продукции. С учетом, что величина a^. b X] представляет собой стоимость часть продукции Ai, выпускаемой предприятием Пi, общая стоимость выпускаемой продукции

По условиям задачи эта величина должна быть минимизирована при выполнении ограничений:

Как и выше задача свелась к задаче линейного программирования.

Решение указанных задач может производиться известными методами [3. 5]; наиболее распространенным является симплекс-метод (существуют стандартные программы).

1. Данилов А.М., Гарькина И.А.Математическое моделирование сложных систем: состояние, перспективы, пример реализации // Вестник гражданских инженеров. 2012. № 2. С. 333-337.

2. Скачков Ю.П., Данилов А.М., Гарькина И.А.Модификация метода ПАТТЕРН к решению архитектурно-строительных задач // Региональная архитектура и строительство. 2011. № 1. С. 4-9.

3. Жегера К.В., Данилов А.М. Квадратичное программирование при решении оптимизационных задач // Вестник магистратуры. 2014. № 2(29). С. 46-48.

4. Будылина Е.А., Гарькина И.А., Данилов А.М. Декомпозиция динамических систем в приложениях // Региональная архитектура и строительство. 2013. № 3. С. 95-100.

5. Гарькина И.А., Данилов А.М., Домке Э.Р. Промышленные приложения системных методологий, теорий идентификации и управления // Вестник Московского автомобильно-дорожного государственного технического университета (МАДИ). 2009. № 2. С. 77-81.

МАРКЕЛОВА Иветта Владимировна — студент, Пензенский государственный университет архитектуры и строительства.

ДАНИЛОВ Александр Максимович — доктор технических наук, профессор, Пензенский государственный университет архитектуры и строительства.

58. Общая и основная задачи линейного программирования

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

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

(8)

(9)

(10)

(11)

Где — заданные постоянные величины и .

Определение 1.2. Функция (8) называется Целевой функцией (или Линейной формой) задачи (8) — (11), а условия (9) — (11) — Ограничениями данной задачи.

Определение 1.3. Стандартной (или Симметричной> задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (9) и (11), где K = M и L=N.

Определение 1.4. Канонической (или Основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (10) и (11), где K=0 и L=п.

Определение 1.5. Совокупность чисел , удовлетворяющих ограничениям задачи (9) — (11), называется Допустимым решением (или Планом).

Определение 1.6. План , при котором целевая функция задачи (8) принимает свое максимальное (минимальное) значение, называется Оптимальным.

Значение целевой функции (8) при плане Х будем обозначать через . Следовательно, X* — Оптимальный план задачи, если для любого Х выполняется неравенство [соответственно ].

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

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

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

Ограничение-неравенство исходной задачи линейного программирования, имеющее вид «£», можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида «³» — в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство

Преобразуется в ограничение-равенство

(12)

— в ограничение-равенство

(13)

В то же время каждое уравнение системы ограничений

Можно записать в виде неравенств:

(14)

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

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

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

1.4. Записать в форме основной задачи линейного программирования следующую задачу: найти максимум функции при условиях

Решение. В данной задаче требуется найти максимум функции, а система ограничений содержит четыре неравенства. Следовательно, чтобы записать ее в форме основной задачи, нужно перейти от ограничений-неравенств к ограничениям-равенствам. Так как число неравенств, входящих в систему ограничений задачи, равно четырем, то этот переход может быть осуществлен введением четырех дополнительных неотрицательных переменных. При этом к левым частям каждого из неравенств вида «£» соответствующая дополнительная переменная прибавляется, а из левых частей каждого из неравенств вида «³» вычитается. В результате ограничения принимают вид уравнений:

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

1.5. Записать задачу, состоящую в минимизации функции при условиях

В форме основной задачи линейного программирования.

Решение. В данной задаче требуется найти минимум целевой функции, а система ограничений содержит три неравенства. Следовательно, чтобы записать ее в форме основной задачи, вместо нахождения минимума функции F нужно найти максимум функции F1 = — F при ограничениях, получающихся из ограничений исходной задачи добавлением к левым частям каждого из ограничений-неравенств вида «£» дополнительной неотрицательной переменной и вычитанием дополнительных переменных из левых частей каждого из ограничений-неравенств вида «³».

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

1.6. Записать в форме стандартной задачи линейного программирования следующую задачу: найти максимум функции при условиях

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

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

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

• Главная
• Заказать работу
• Стоимость решения
• Варианты оплаты
• Ответы на вопросы (FAQ)
• Отзывы о нас
• Примеры решения задач
• Методички по математике
• Помощь по всем предметам
• Заработок для студентов