Тема 1: решение задач линейного программирования

Тема 1: РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Вопросы:

Введение

Задача линейной оптимизации

Последовательность решения задач оптимизации среде MS Excel

Постановка задачи

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

Разработка и создание электронной модели

Поиск оптимального решения

Технология работы с надстройкой Поиск решения

Результат Поиска решения

Введение

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

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

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

Граничные условия: ,

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

Ограничения (ОГР) – устанавливают зависимости между переменными. Они могут быть односторонними () или двусторонними: ( ).

Граничные условия (ГРУ) – показывают, в каких пределах могут изменяться значения переменных.

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

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

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

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

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

 

Задача линейной оптимизации

Постановка задачи

Минимизировать функцию Z=-x ₁ +3x ₂ +2x ₃ при ограничениях:

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

ЦФ:Z=-x ₁ +3x ₂ +2x ₃→min

ОГР:

 

ГРУ:

Поиск оптимального решения

Для поиска оптимальных решений в Microsoft Excel используется надстройка Поиск решения. Поскольку данным средством пользуются не все категории пользователей, она загружается по мере необходимости и выгружается после завершения работы с приложением. Для загрузки надстройки выполните команду меню СервисÞНадстройки, в диалоговом окне Надстройки установите флажок Поиск решения и нажмите кнопку <OK>.

 

Результат поиска решения

 

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

 

 

2.1. Создание математической модели классической транспортной задачи

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

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

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

Транспортная задача формулируется следующим образом. Имеется m пунктов производства (A₁, …, A_m) однородного продукта или взаимозаменяемых продуктов и n пунктов потребления (B₁, …, B_n). Заданы объемы производства a_i каждого пункта производства и размеры спроса b_j каждого пункта потребления в одних и тех же единицах (в штуках, тоннах, вагонах или других единицах измерения). Известны также транспортные издержки c_ij (расходы), связанные с перевозкой единицы продукта из пункта A_i в пункт B_j. В термин «транспортные издержки» не всегда вкладывается его непосредственный экономический смысл. Транспортные издержки здесь – скорее условное понятие, которое в различных задачах может означать себестоимость, расстояние, тариф, время, расход топлива и т.д.

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

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

Переведем транспортную задачу на формальный язык. Пусть x_ij – количество единиц продукта, поставленное из пункта A_i в пункт B_j. Суммарные затраты (суммарные транспортные издержки) на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются суммой

. (1)

Условия полного удовлетворения спроса каждого пункта потребления продуктами из разных пунктов производства имеют вид

j=1, 2, …, n. (2)

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

i=1, 2, …, m. (3)

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

i=1, 2, …, m, j=1, 2, …, n. (4)

Транспортная задача сводится, таким образом, к минимизации суммарных затрат (1) при условиях (2) – (4). Будем называть задачу (1) – (4) задачей Т.

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

i=1, 2, …, m. (5)

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

Задача, в которой требуется минимизировать сумму (1) при условиях (2), (4) и (5), называется открытой транспортной моделью.

Открытую модель можно свести к замкнутой, если ввести фиктивный пункт потребления B_n+1 с объемами потребления:

.

 

Пример решения транспортной задачи в MS Excel.

 

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

 

1. Постановка транспортной задачи.

Фирма имеет 4 фабрики и 5 центров распределения ее товаров. Фабрики имеют производственные возможности соответственно 200, 150, 225 и 175 единиц продукции ежедневно. Распределительные центры имеют следующие потребности: 100, 200, 50, 250 и 150 единиц продукции ежедневно. Хранение не поставленной в центр единицы продукции на фабрике обходится в $0,75 в день, а штраф за просрочку поставки заказанной потребителям в центре распределения единицы продукции, но там находящейся, равен $2,5 в день. Стоимость перевозки единицы продукции с фабрик в пункты распределения приведены ниже.

Центры распреде- ления   Фабрики						Производство
	1,5		1,75	2,25	2,25
	2,5		1,75		1,5
		1,5	1,5	1,75	1,75
		0,5	1,75	1,75	1,75
Потребность

 

Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы.

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

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

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

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

Для решения данной задачи построим ее математическую модель. неизвестными здесь являются объемы перевозок. Пусть x_ij – объем перевозок с i-той фабрики в j-тый центр распределения. Целевой функцией являются суммарные транспортные расходы, то есть:

,

где с_ij – стоимость перевозки единицы продукции с i-той фабрики в j-тый центр распределения. Кроме того, неизвестные должны удовлетворять следующим ограничениям:

· неотрицательность объема перевозок;

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

Таким образом, модель будет такой:

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

,

,

,

где a_i – объем производства на i-той фабрике, b_j – спрос в j-том центре распределения.

3. Решение транспортной задачи.

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

 

2. Ввести в ячейки диапазона B3:F6 стоимости перевозок.

3. Отвести ячейки диапазона B8:F11 под значения неизвестных (объемов перевозок).

4. Ввести в ячейки диапазона H8:H11 объемы производства на фабриках.

5. Ввести в ячейки диапазона B13:F13 потребность в продукции в пунктах распределения.

6. В ячейку B16 ввести целевую функцию:

=СУММПРОИЗВ(B3:F6;B8:F11)

7. В ячейки диапазона G8:G11 ввести формулы, вычисляющие объемы производства на фабриках, в ячейки диапазона B12:F12 – объемы доставляемой продукции в пункты распределения. А именно:

Ячейка Формула Ячейка Формула

G8 =СУММ(B8:F8) B12 =СУММ(B8:B11)

G9 =СУММ(B9:F9) C12 =СУММ(C8:C11)

G10 =СУММ(B10:F10) D12 =СУММ(D8:D11)

G11 =СУММ(B11:F11) E12 =СУММ(E8:E11)

F12 =СУММ(F8:F11)

Рис.1 Исходные данные транспортной задачи

8. Выбрать команду Сервис | Поиск решения и заполнить диалоговое окно Поиск решения, как показано на рис.2.

Рис.2 Заполненное диалоговое окно Поиск решения

 

9. Нажать кнопку Параметры. На экране отобразится диалоговое окно Параметры поиска решения (Рис.3).

Рис.3 Окно Параметры поиска решения

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

10. Нажать кнопку Выполнить. Средство Поиск решения найдет оптимальный план поставок продукции и соответствующие ему транспортные расходы.

11. После нажатия кнопки ОК результаты будут внесены в рабочий лист (Рис.4).

Рис.4. Оптимальное решение транспортной задачи.

На Рис.4 видно, что план перевозок, при котором суммарные транспортные расходы минимальны и равны 975 долл., должен быть следующим: со склада в Денвере нужно перевезти в Лос-Анджелес 100 единиц продукции, в Даллас – 25 единиц, в Сент-Луис – 50 единиц, в Атланту – 25 единиц; со склада в Бостоне 150 единиц продукции – в Вашингтон; со склада в Нью-Орлеане 100 единиц – в Вашингтон и 125 – в Атланту; со склада в Далласе потребителям в Далласе следует отправить 175 единиц продукции.

 

 

Тема 1: РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Вопросы:

Введение

Задача линейной оптимизации