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

Для решения таких задач Excel имеет специальный инструмент «Поиск решения». Надстройка «Поиск решения» в Microsoft Excel позволяет напрямую находить оптимальное решение транспортной задачи.

Для добавления надстройки «Поиск решения», если на вкладке «Данные» этого пункта нет перейдите: Файл - Параметры. Слева выберите меню «Надстройки». В основной части выделите «Поиск решения». Затем ниже, нажмите «Перейти». В открывшемся окне отметьте пункт «Поиск решения» и нажмите «Ok». Во вкладке «Данные» появился соответствующий одноименный пункт.

Рассмотрим общее условие транспортной задачи:

Найти m*n неотрицательных чисел X_ij- объем перевозок от i-ого поставщика к j-ому потребителю, минимизирующих транспортные затраты по перевозке однородных грузов поставщиков с мощностями (запасами) А₁,А₂…Ам к потребителям с потребностями В₁,В₂…Вn, если известны матрица издержек С_ij - издержки перевозки единицы груза от i-ого поставщика к j-ому потребителю.

Рассмотрим математическую постановку транспортной задачи:

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

Ограничения

для i=1,2….m

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

для j=1,2….n

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

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

.1 Решение ЗЛП графическим методом

Для сохранения здоровья и работоспособности человек должен в сутки потреблять не менее 63 усл.ед. белков, не менее 147 усл.ед. жиров и не менее 126 усл.ед. углеводов. Для простоты допустим, что имеется всего два вида продуктов П₁ и П₂ ; стоимость единицы каждого из них равна соответственно 12 и 9 ден.ед. Содержание названных питательных веществ в различных продуктах неодинаково. Предположим, что в единице продукта П₁ содержится 9 усл.ед. белков, 7 усл.ед. жиров 9 усл.ед. углеводов; а в единице продукта П₂ содержится соответственно 3, 21, 10 усл.ед. тех же питательных веществ.

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

Приступим к решению данной задачи с помощью графического метода.

.        Пусть х₁ - количество продукта 1-го вида, х₂ -количество продукта 2-го вида, а f -затраты на приобретение продуктов.

Целевая функция, выражающая совокупные затраты на приобретение продуктов, будет иметь следующий вид: f = 12x₁+9x₂ => min

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

х₁+3х₂ >=63 - для белков

х₁+21х₂>=147 - для жиров

х₁+10х₂>=126 - для углеводов

Кроме того, по смыслу задачи х₁ >=0, х₂>=0

) Для построения области допустимых решений строим в системе координат соответствующие данным ограничениям-неравенствам граничные прямые (см. рис.2).

) 9х₁+3х₂ =63 2) 7х₁+21х₂=147 3) 9х₁+10х₂=126

х₁=0; х₂=21 х₁=0; х₂=7 х₁=0; х₂=12,6

х₂=0;х₁=7 х₂=0; х₁=21 х₂=0; х₁=14

Рис. 2. Прямые в системе координат, соответствующие данным ограничениям-неравенствам

Далее найдем область допустимых решений.

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

Рис. 3. Область допустимых значений

3) Следующим пунктом в решение данной задачи будет построение вектора градиента и выбор оптимальной точки на границе. Вектор-градиент показывает направление минимизации целевой функции. Определим его координаты: координаты начальной его точки - (0; 0), координаты второй точки:

Для того чтобы найти координаты второй точки, мы возьмем производную от целевой функции и она будет равна: df/dx₁=12; df/dx₂=9

Перпендикулярно к построенному вектору проводим линию уровня f=0 (см. рис.4).

Рис.4. Вектор - градиент

Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. Прямая F(x) = const пересекает область в точке А. Так как точка А получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых.

) Найдем координаты этой точки и для этого решим систему уравнения.

x₁+3x₂=63; *(-1) -9х₁-3х₂=-63; 7х₂=63

х₁+10х₂=126. 9x₁+10x₂=126. х₂=9

Далее мы подставим х₂ в любое из уравнений системы:

х₁+3*9=63

х₁=63-27

х₁=36

х₁=4

Мы нашли координаты точки А и они равны: х₁=4; х₂=9

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

F(x) = 12*4+9*9=129

Таким образом, для того, чтобы затраты на рацион были минимальны необходимо приобретать 4 усл.ед. продукта 1-го вида и 9 усл.ед. 2-го. При этом затраты будут минимальны, и составят 129 условных денежных единиц.

.2 Проверка оптимального решения в среде MS Excel с использованием программной надстройки «Поиск решения»

В данном пункте мы проверим правильность решения ЗЛП графическим методом. Для этого мы воспользуемся средой MS Excel.

)Создадим область переменных. Ячейки В2:В3 будут играть роль переменных (пока они пусты)

)В ячейку А6 введем формулу целевой функции (см. рис.5; приложение Б)

Рис. 5. Формула вычисления значений ЦФ

3)Создадим область ограничений. В ячейках А10:А12 будем вычислять левые части ограничений в системе, а в ячейках В10:В12 введем правые части ограничений системы (см. рис.6)

Рис.6. Левые и правые части ограничения

)Вызовем окно диалога «Поиск решения». Устанавливаем целевую ячейку А6 (там где вычисляется значение целевой функции). Указываем направление оптимизации - минимизация (по условию)

В поле изменяя ячейки указываем ячейки переменных В2:В3 ( рис.7; приложение А)

) Далее мы добавим ограничения. Для начала мы укажем неотрицательность переменных (см. рис.8)

Рис.8. Неотрицательность переменных

) Далее мы добавляем остальные ограничения.

Рис. 9.Остальные ограничения

Так же выбираем метод решения: Поиск решения линейных задач симплекс-методом.

После добавления всех параметров мы нажимаем на «Найти решение». Оформим полученный результат и получим следующее (рис.10; приложение Б)

Таким образом, оптимальное решение, полученное с помощью графического метода, совпадает с решением, полученным в среде MS Excel с помощью программной надстройки «Поиск решения».

2.3 Решение ТЗЛП в среде MS Excel с использованием программной надстройки «Поиск решения»

Нам дана следующая транспортная задача:

Дано 5 производителей А1, А2, А3, А4, А5, мощность (запасы) которых соответственно равны: 20, 45, 25, 30,20.

И четыре потребителя В1, В2, В3, В4, потребность которых в продукте составляет соответственно: 45, 50, 20, 25.

Также известна матрица издержек С_ij - издержки перевозки единицы груза от i-ого поставщика к j-ому потребителю.(таблица 1)

Таблица 1 Матрица издержек Сij - издержки перевозки единицы груза от i-ого поставщика к j-ому потребителю

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

Таблица 2 Полное условие транспортной задачи

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

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

) Перенесем полное условие транспортной задачи в Excel (см. рис.11).

Рис. 11. Полное условие ТЗ в Excel

) Далее мы составляем вторую такую же таблицу, но данными заполнять ее не будем (см. рис.12).

Рис. 12 Оформление ТЗЛП

3) В ячейке Н1 введем формулу: СУММAПРОИЗВ(В3:E7;B12:E16) (рис.13)

Рис. 13 Целевая функция

) В ячейку F12 введите формулу СУММ(B12:E12) и растяните её до F16(рис.14)

Рис. 14 Применение формулы для запасов

5) В ячейку B17 введите формулу СУММ(B12:B16) и скопируйте ее в диапазон от B17 до E17(рис.15)

Рис.15 Применение формулы для потребности

) Для решения задачи на панели вкладок выберите вкладку «Данные», а затем «Поиск решения». Оптимизируем целевую функцию, по условию задачи ЦФ минимизируем. Также обозначим ограничения для нашей задачи, ограничения будут следующие:

1)      $B$12:$E$16 = целое

2)      $B$12:$E$16 >=0

3)      $B$17:$E$17= $B$8:$E$8

4)      $B$12:$F$16 = $F$3:$F$7 (см. рис.16)

Рис.16 «Поиск решения»

Таким образом, в диапазоне B12:E16 Мы получим результат решения транспортной задачи (т.е. значение в ячейке соответствует количеству груза перевезенного от i-ого поставщика к j-ому потребителю).

В диапазоне F12:F16 количество груза, которое необходимо вывезти от поставщиков.

В диапазоне B17:E17 количество, которое будет доставлено потребителям согласно найденному решению.

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

Оформим полученный результат и получим следующее (см. рис 17)

Таким образом, Из 1-го склада необходимо груз направить в 2-й магазин (15), в 4-й магазин (5)

Из 2-го склада необходимо груз направить в 1-й магазин (40), в 2-й магазин (5)

Из 3-го склада необходимо груз направить в 1-й магазин (5), в 3-й магазин (20)

Из 4-го склада необходимо весь груз направить в 2-й магазин

Из 5-го склада необходимо весь груз направить в 4-й магазин

На 5-ом складе остался невостребованным груз в количестве 5 ед.

При этом затраты равны 765 ед.

ЗАКЛЮЧЕНИЕ

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

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

В рамках данной работы была решена одна из задач линейного программирования. В результате применения процедуры графического метода было получено оптимальное решение поставленной задачи, в соответствии с которым, чтобы затраты на рацион были минимальны необходимо приобретать 4 усл.ед. продукта 1-го вида и 9 усл.ед. 2-го. При этом затраты будут минимальны, и составят 129 условных денежных единиц Проверка результатов решения задачи в среде MS Excel показала аналогичное решение данной задачи оптимизации.

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

Из 2-го склада необходимо груз направить в 1-й магазин (40), в 2-й магазин (5)

Из 3-го склада необходимо груз направить в 1-й магазин (5), в 3-й магазин (20)