Задание по программированию. ДВФУ

ТИТУЛЬНЫЙ ЛИСТ Лабораторная работа №1 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL Цель работы: приобретение навыков решения задач линейного программирования в табличном редакторе Microsoft Excel. Задание: используя MS Excel, найти решение для модели ЛП, соответствующей заданному варианту. Вариант 20 Некоторой компании принадлежат три фермы, где выращивают овощи, предназначенные для последующей обработки на двух холодильных заводах компании. Одним из выращиваемых овощей являются бобы, которые холодильные заводы продают по 200 руб. за 1 т. В таблице 1 приведены издержки производства для каждой фермы и каждого холодильного завода, максимальные значения урожая для каждой фермы, прогнозные значения спроса на следующий сезон для каждого завода. В таблице 2 приведена стоимость транспортировки бобов. Таблица 1 – Издержки производства и максимальный урожай бобов Издержки производства, руб/т Максимальный урожай, т Фермы 1 90 2000 2 95 3000 3 87 1500 Прогнозный спрос, т Заводы 1 20 2750 2 23 3250 Таблица 2 – Стоимость транспортировки бобов, руб/т Фермы Холодильный завод 1 2 1 10 15 2 12 12 3 18 9 Постройте транспортную модель, которая для ферм и холодильных заводов позволяет найти на следующий сезон производственный план, гарантирующий максимальный доход. ВЫПОЛНЕНИЕ РАБОТЫ: 1 Анализ условия задачи Для построения корректной математической модели задачи необходимо свести все исходные данные в одну таблицу, которая будет содержать следующие данные: издержки производства для каждой фермы и холодильного завода, а также издержки на транспортировку (за 1 т); максимальный урожай для каждой фермы и прогнозный спрос для каждого завода. Таблица 3 – Сводные данные Фермы Холодильный завод Максимальный урожай, т 1 2 1 90+20+10=120 90+23+15=128 2000 2 95+20+12=127 95+23+12=133 3000 3 87+20+18=125 87+23+9=119 1500 Прогнозный спрос, т 2750 3250 То есть имеет место транспортная задача линейного программирования. В нотации транспортной задачи получили, что на трех пунктах поставки (фермах) , , объемы запасов однородного груза (бобов) соответственно составляют , , т. Груз необходимо перевезти в два пункта потребления (холодильные заводы) , , потребности которых соответственно составляют , т. Известна матрица удельных транспортных затрат (издержки производства и транспортировки) на единицу (тонну) груза из -го пункта поставок в -ый пункт потребления: Согласно условию, необходимо составить такой план перевозок, чтобы вывезти весь груз из пунктов поставки, удовлетворить потребности всех пунктов потребления и при этом суммарная прибыль должна быть максимальной. Исходя из того, что прибыль определяется разностью между вырученной суммой при продаже и затратами, для дальнейшего расчета целесообразно принять следующую матрицу, где — цена продажи одной тонны груза: Т.е. матрица содержит значения чистой прибыли от реализации 1 т продукции. Для нахождения максимального значения прибыли необходимо определить производственный план. Обозначенная постановка задачи требует выполнения равенства общей суммы запасов общей сумме потребностей, т.е. Для заданных исходных данных получим: , , , т.е. имеет место задача с открытым балансом. Для ее решения следует ввести фиктивный пункт потребления груза с объемом потребностей и (прибыль фиктивна). Тогда матрица примет вид: Теперь получена транспортная задача с закрытым балансом и можно переходить к непосредственному построению математической модели. 2 Построение математической модели задачи Обозначим через количество груза, которое необходимо перевезти из -го пункта поставки в -ый пункт потребления. Суммарную прибыль (максимальный доход) обозначим через . Тогда целевая функция задачи будет иметь вид: Для составления ограничений транспортной задачи воспользуемся следующими суждениями: 1) объем груза, который необходимо перевезти в пункт потребления из всех пунктов поставки, равен , а пункт потребления может принять продукции, таким образом будем иметь ограничения: , где ; 2) объем груза в пункте поставки , который необходимо вывезти в пункты потребления, равен , и этот груз должен быть вывезен в полном объеме , следовательно, получим ограничение: , где ; 3) количество перевезенного груза не может быть отрицательно, следовательно, накладываемое ограничение будет иметь вид: . Таким образом, сокращенная математическая модель задачи имеет вид: В развернутом виде: Подставив численные значения, получим: Таким образом, после построения математической модели задачи ее решение сводится к определению значений переменных , удовлетворяющих условиям системы ограничений, и обращающих в максимум значение целевой функции . Решение данной задачи целесообразно выполнять путем компьютерной реализации модели транспортной задачи с использованием табличного процессора MS Excel; 3 Решение транспортной задачи в среде табличного процессора Для решения транспортной задачи в среде табличного процессора MS Excel введем исходные данные на лист (рисунок 1). Рисунок 1 – Исходные данные задачи Сформируем расчетные ячейки. Заполним нулями ячейки Е12:G14 (начальные значения, рисунок 2) и введем формулы для расчета объемов и значения целевой функции (рисунок 3): Рисунок 2 – Начальные значения для расчетов Рисунок 3 – Введенные формулы Для решения воспользуемся надстройкой табличного процессора Поиск решения (для активации используем вкладку Сервис / Надстройки / Поиск решения) (рисунок 4). Рисунок 4 –Вызов надстройки Поиск решения Введем абсолютный адрес ячейки целевой функции — $D$17, укажем направление оптимизации – максимум, введем абсолютные адреса изменяемых ячеек (значений переменных) — $E$12:$G$14, введем ограничения задачи. Также нажав кнопку Параметры в окне настройки активируем опции Линейная модель и неотрицательные значения (рисунок 5). Рисунок 5 – Ввод данных и настройка опций Поиска решения Нажав кнопку ОК в окне настройки параметров, а затем Выполнить в окне надстройки, получено сообщение о том, что оптимальное решение задачи найдено, выберем опцию Сохранить найденное решение (рисунок 6). Рисунок 6 – Результат поиска решения В результате получим значения, представленные на рисунке 7. Рисунок 7 – Результаты решения транспортной задачи Таким образом, максимальный суммарный доход составит 466750 руб, и достигнут он будет при следующем производственном плане: — на первой ферме целесообразно вырастить 2000 т продукции (бобов) с их последующей транспортировкой на холодильный завод №1; — на второй ферме целесообразно вырастить 2500 т бобов (из возможных 3000 т, т.к. 500 т из них останутся нереализованными), при этом их целесообразно транспортировать на холодильные заводы №1 и №2 в количестве 750 и 1750 т соответственно; — на третьей ферме целесообразно вырастить 1500 т бобов с их последующей транспортировкой на холодильный завод №2. Вывод: в ходе выполнения лабораторной работы закреплены теоретические знания в области анализа и построения математической модели задач линейного программирования, приобретены навыки решения задач указанного типа с использованием табличного процессора MS Excel. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем. – 2-е изд. – М.: Финансы и статистика, 2006. – 432 с. 2. Бродецкий Г.Л., Гусев Д.А. Экономико-математические методы и модели в логистике. Процедуры оптимизации. – 2-е изд. – М.: ИЦ Академия, 2014. – 288 с. 3. Конюховский П.В. Математические методы исследования операций в экономике. – СПб: Питер, 2000. – 208 с. 4. Леоненков А.В. Решение задач оптимизации в среде MS Excel. – СПБ.: БХВ-Петербург, 2005. – 704 с. 5. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. — СПб.: Лань, 2015. — 512 с. 6. Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. Кн.3. Задачи транспортного типа. – М.: Либроком, 2010. – 184 с.