Курсовая работа (т): Решение типовых задач линейного программирования в табличном процессоре MS Excel

.4 Транспортная задача

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

Пусть имеется m пунктов производства однородного продукта (добыча руды в карьерах, сборка бытовой техники, изготовление кондитерских изделий и др.) и n пунктов потребления этого продукта. Мощности пунктов производства составляют  единиц однородного продукта, а потребности каждого j-го пункта потребления равны  единиц. Известны затраты на перевозку едиицы продукта от i-го поставщика j-му потребителю. Составить такой план перевозок, при котором суммарные затраты на все перевозки были бы наименьшими. Пусть спрос и предложение совпадают, то есть

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

Составим математическую модель задачи. Обозначим через  - количество продукта, перевозимого из i-го пункта производства в j-й пункт потребления. Тогда матрица:  - план перевозок.

Матрицу  называют матрицей затрат (тарифов).

Составим таблицу 4, в которую внесем все исходные данные и перевозки x_ij.

Таблица 4 - Транспортная таблица

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

которую необходимо минимизировать при ограничениях: (весь продукт из каждого i-го () пункта должен быть, вывезен полностью),(спрос каждого j-го () потребителя должен быть, полностью удовлетворен).

Из условия задачи следует, что все .

Итак, математическая модель сбалансированной транспортной задачи имеет вид:

3. ПРИКЛАДНЫЕ ЗАДАЧИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

На основе, рассмотренной теоретической части, необходимо составить математические модели некоторых задач линейного программирования и найти оптимальное решение для каждой из них, с помощью приложения MS Excel 2007.

.1 Характеристика программного средства

Для решения поставленных задач и наглядного представления их решений была важна возможность использования математических формул и непосредственно функции «Поиск решения».

Надстройка «Поиск решения» позволяет найти оптимальное (максимальное или минимальное) значение для формулы <javascript:AppendPopup(this,'xldefFormula_2_2')>, содержащейся в целевой ячейке. Поиск решения» работает с диапазоном ячеек, связанных с формулой в целевой ячейке. Чтобы получить оптимальный результат по формуле из целевой ячейки, «Поиск решения» изменяет значения в ячейках, выбранных как изменяемые. Для конкретизации значений применяются ограничения (система неравенств), которые могут ссылаться на другие ячейки (группы ячеек), влияющие на формулу для ячейки с записанной целевой функцией[3].

Именно этими возможностями обладают известные табличные процессоры Microsoft Office Excel 2007 и Open Office Calc. В отличие от Open Office Calc MS Excel является более распространенным и привычным для обычного пользователя, имеет более широкий спектр поддерживаемых форматов файлов. При использовании MS Excel возникновение несовместимости с другими программы в разы меньше, чем у Open Office. Так же в MS Excel есть встроенный язык программирования - Visual Basic for Applications. Плюс ко всему вышеперечисленному данное программное средство обладает более функциональным и интуитивно понятным интерфейсом.

Надстройка «Поиск решения» в Open Office Calc немногим отличается от похожей надстройки в MS Excel. В последнее время эти два табличных редактора уже стали практически идентичны по функциональному набору. Хотя стоит признать, что Calc все же уступает конкуренту именно в наборе «Пакета анализа»[19].

Таким образом, для решения поставленных задач использовалось программное средство Microsoft Office Excel 2007 из пакета прикладных программ Microsoft Office.

.2 Решение задачи о рационе питания в среде MS Excel

линейное программирование табличный процессор

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

Необходимо составить наименее затратный рацион питания поросят, содержащий необходимое количество витаминов А, C и D. Пищевая ценность рациона питания (в калориях) должна быть не менее необходимой. Данная смесь изготавливается из двух видов кормов - К₁ и К₂. Причем, корма вида K₁ в рационе не должно быть использовано более 0,5 кг. Аналогично для корма K₂ - не более 0,85 кг. Исходные данные для дальнейших расчетов приведены в таблице 5.

Таблица 5 - Содержание витаминов в кормах

Решение:

Построим математическую модель. За  обозначим количество корма К₁, аналогично за  - объем К_2.Исходя из условия задачи  и  - неотрицательные значения. Целевая функция будет стремиться к минимуму т.к. расходы, с учетом всех необходимых условий, должны быть как можно меньше.

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

Из названий столбцов таблицы 5 ясно, что порции кормов составляют по 100 грамм, а ограничение по количеству в условии задачи дано в килограммах. Следовательно, необходимо их привести в ту же систему, что и остальные неравенства. 0,5 кг это 500 г, а 0,85 кг - 850 г. Таким образом, .

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

Задачу линейного программирования можно решить как графически, так и симплекс-методом. В данном случае, воспользуемся пакетом прикладных программ Microsoft Office, в частности MS Excel, надстройкой «Поиск решения».

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

Рисунок 1 - Форма ввода данных в задаче о диете

Ячейки B3 и C3 отведены для переменных , пока они обнулены, но в дальнейшем они будут являться изменяемыми ячейками т.к. именно эти значения влияют на функцию цели. В ячейку E3 введена формула для целевой функции, которая будет стремиться к минимальному значению. В диапазоне ячеек F7:F12 можно применить математическую функцию «Сумму произведений» (СУММПРОИЗВ). Первый массив для всех неравенств, следовательно, его нужно отметить знаком «$», как абсолютную ссылку, чтобы при копировании в другие ячейки адрес этих ячеек не изменялся. Использование данной функции представлено на рисунке 2.

Рисунок 2 - Введение формул

Далее, используем надстройку «Поиск решения». Вызвать ее можно выбрав вкладку «Данные», закладку «Анализ». В диалоговом окне «Поиска решения», рисунок 3, вводим ячейку цели функции, изменяемые ячейки и все ограничения в виде неравенств, так же отмечаем маркером, что целевая функция принимается равной минимальному значению.

Рисунок 3 - Диалоговое окно надстройки «Поиск решения»

После нажатия кнопки «Выполнить» на экране появляется решение задачи линейного программирования, рисунок 4.

Рисунок 4 - Результат работы «Поиска решения»

Таким образом, минимальное значение функции цели , то есть для составления оптимального суточного рациона питания, с минимальными затратами и содержанием всех витаминов в полном объеме, нужно взять 400 грамм корма К₁и 200 грамм корма К₂. При этом стоимость данных витаминных добавок будет составлять 34 денежные единицы.

.3 Решение задачи о плане производства в среде MS Excel

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

Необходимо произвести изделия двух типов. Для их изготовления имеется 120 кг алюминия. На изделиеI типа расходуется 4 кг алюминия, а на изделиеII типа - 2 кг. Составить план выпуска изделий, обеспечивающий получение наибольшей прибыли от продажи изделий. Стоимость изделия I типа установлена 4условные денежные единицы, а изделия II типа - 5условных денежных единиц, причем изделий I типа требуется изготовить не более 35, а изделий II типа - не более 10.

Решение:

Обозначим количество изделийI типа как , а количество, производимых по плану, изделий II типа -.

Логично предположить, что Прибыль от продажи изделий составит

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

Также при составлении оптимального плана производства нельзя не учитывать ограничения по имеющемуся ресурсу. При производстве изделий I типа расходуется  (кг). В то время, на производство изделий II типа используется  (кг) алюминия.Таким образом, суммарный расход алюминия составляет(кг). Данная величина не должна превышать запасы алюминия в количестве 120 кг. В итоге получаем неравенство:

Изделий I типа в плане выпуска продукции должно быть не более 35 штук, то есть. Аналогично для изделий II типа: , так как по условию этих изделий должно быть не более 10.

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

Решим задачу линейного программирования с помощью программы MSExcel.

Для этого необходимо выполнить следующие шаги:

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

Рисунок 5 - Форма для ввода данных

Текст в данной форме непосредственно на ход решения задачи не оказывает никакого влияния. Данные комментарии делают решение задачи более понятной. Для неизвестных и  зарезервированы ячейкиВ10 и С10. В них после решения задачи будут внесены полученные значения. Значение функции цели Z будет зафиксировано в ячейке G9;

2) ввести исходные данные. В диапазон В4:С6 вводим коэффициенты при переменных в системе ограничений: «Первое» - коэффициенты 1 и 0,«Второе» - 0 и 1,«Третье» - 4 и 2.В диапазоне ячеек D4:D6 и Н4:Н6 заносим значения свободных членов системы ограничений: 35, 10 и 120. В диапазон ячеек В11:С11 - коэффициенты целевой функции Z, то есть 4 и 5;

3) ввести формулы для расчета целевой функции и системы ограничений. Для вычисления значений функции цели в ячейкуG9необходимо ввести формулу = В11*В10 + С11*С10.Здесь вместо коэффициентов 4 и 5 записаны их адреса В11 иС11, а вместо переменных  и соответствующие адреса В10 иС10.

Введем формулы левых частей системы ограничений в диапазоне ячеек F4:F6. Сначала в ячейку F4 запишем выражение = В4*$B$10 + C4*$C$10, соответствующее алгебраическому выражению (1· + 0·). Этолевая часть первого ограничения системы неравенств. Абсолютная адресация ячеек ($C$10)необходима, так как абсолютный адрес при перемещении (копировании) не изменяется. Для создания формул в ячейкахF5 и F6 воспользуемся возможностью заполнения формулы в ячейке F4 путем ее копирования. В результате заполнения в ячейке F5 будет записана формула = В5*$B$10 + C5*$C$10, что соответствует выражению - (0· +1·), а в ячейке F6:= B6*$B$10 + C6*$C$10, что соответствует выражению (4· + 2·). В результате вводавсех имеющихся данных таблица примет вид, представленный на рисунке 6: