Задачи математического программирования (стр. 4 из 6)
Привести математическую постановку двойственной задачи ЛП;
Получить решение двойственной задачи ЛП с использованием надстройки Excel «Поиск решения»;
Получить решение задачи в предположении целочисленности переменных;
Произвести анализ полученных результатов и дать их содержательную интерпретацию.
Задача: В состав рациона кормления входят три продукта: сено, силос и концентраты, содержащие следующие питательные вещества: белок, кальций и витамины. Содержание питательных веществ в граммах в 1 килограмме соответствующего продукта питания и минимально необходимое их потребление заданы таблицей:
| Продукты | Питательные вещества | ||
| белок | кальций | витамины | |
| 1. Сено | 5 | 6 | 2 |
| 2. Силос | 2 | 4 | 1 |
| 3. Концентраты | 18 | 3 | 1 |
| Норма потребления | 200 | 120 | 40 |
Определить оптимальный режим кормления, из условия минимальной стоимости, если цена 1 кг продукта питания соответственно составляет: для сена - 30коп., для силоса- 20 коп., для концентрата – 50 коп.
Решение
Осуществить математическую запись задачи ЛП. Составим математическую модель. Обозначим через х1 – количество единиц сена, через х2 – количество единиц силоса а через х3 – количество единиц концентрата. Функция затрат на покупку этих продуктов выглядит так: f(x)=30x1+20x2+50x3 её необходимо минимизировать. Необходимые нормы потребления выражены в виде ограничений:
 |
В результате общая постановка задачи ЛП имеет вид:
Решить задачу с использование надстройки Excel «Поиск решения». В качестве значений переменных выступает количество закупаемой продукции каждого вида. В ячейках «Расход питательных веществ» содержатся формулы, определяющие левые части ограничений, а в ячейках необходимое потребление питательных веществ – значения правых частей ограничений.
После ввода всех данных выбираем команду Сервис / Поиск Решения и, заполняем открывшееся диалоговое окно Поиск Решения:
В качестве целевой ячейки выбираем ячейку, в которой находится значение целевой функции, выполняем максимизацию функции, изменяя ячейки со значениями количества продукции. Устанавливаем ограничения.
Далее выбираем пункт «Параметры», чтобы проверить, какие параметры заданы для поиска решения. В окне Параметры поиска решения можно изменять условия и варианты поиска решения исследуемой задачи, а также загружать и сохранять оптимизируемые модели.
Для данной задачи достаточно установить два флажка «Линейная модель» (т.к. ограничения и целевая функция являются линейными по переменным) и «Неотрицательные значения» (для выполнения условий
задачи ЛП).Теперь задача оптимизации подготовлена полностью. После нажатия кнопки «Выполнить» открывается окно «Результаты поиска решения», которое сообщает, что решение найдено.
Таблица 9
| Переменные | Целевая функция | |||||
| Вид продукта | сено | силос | концентрат | f(x) | ||
| значение | 16,77 | 0,00 | 6,45 | 76,13 | ||
| затраты на ед.прод. | 3 | 2 | 4 | min | ||
| Ограничения | ||||||
| Питательные вещества | сено | силос | концентрат | расход питательныхвеществ | знак | необходимое потребление пит.веществ |
| белки | 5 | 2 | 18 | 200,00 | >= | 200 |
| кальций | 6 | 4 | 3 | 120,00 | >= | 120 |
| витамины | 2 | 1 | 1 | 40,00 | >= | 40 |
Привести математическую постановку двойственной задачи ЛП. Двойственная задача ЛП определяется по формуле:
Математическая постановка двойственной задачи ЛП:
Получить решение двойственной задачи ЛП с использованием надстройки Excel «Поиск решения». К имеющимся данным добавляются значения двойственных переменных, ячейка, содержащая формулу целевой функции двойственной задачи, и ячейки, определяющие левые части ограничений двойственной задачи. Далее для решения двойственной задачи выполняем с помощью надстройки Excel «Поиск решения». Получаем:
Таблица 10
| Переменные | Целевая функция | ||||||
| Вид продукта | сено | силос | концентрат | f(x) | |||
| значение | 16,77 | 0,00 | 6,45 | 76,13 | |||
| затраты на ед.прод. | 3 | 2 | 4 | min | |||
| Ограничения | |||||||
| Питательные вещества | сено | силос | концентрат | Левая часть | знак | Правая часть | Двойственные оценки |
| белки | 5 | 2 | 18 | 200,00 | >= | 200 | 0,6 |
| кальций | 6 | 4 | 3 | 120,00 | >= | 120 | 0 |
| витамины | 2 | 1 | 1 | 40,00 | >= | 40 | 0 |
| Ограничения двойственной функции | Целевая функция двойственной задачи | ||||||
| 3 | 1,2 | 10,8 | 120 | ||||
Получить решение задачи в предположении целочисленности переменных/ Для решения поставленной задачи воспользуемся командой Поиск решения. К исходным данным при решении задачи ЛП добавим еще одно ограничение целочисленности для ячеек, содержащих искомое количество производимой продукции. После выполнения поиска получаем решение, приведенное в таблице 11.
Таблица 11
| Переменные | Целевая функция | |||||
| Вид продукта | сено | силос | концентрат | f(x) | ||
| значение | 16 | 0 | 6 | 76 | ||
| затраты на ед.прод. | 3 | 2 | 4 | min | ||
| Ограничения | ||||||
| Питательные вещества | сено | силос | концентрат | расход питательныхвеществ | знак | необходимое потребление питательныхвеществ |
| белки | 5 | 2 | 18 | 200 | >= | 200 |
| кальций | 6 | 4 | 3 | 120 | >= | 120 |
| витамины | 2 | 1 | 1 | 40 | >= | 40 |
Из полученного решения очевидно, что для минимизации затрат необходимо закупать 16 кг сена и 6 кг концентрата, закупка же силоса нецелесообразна. При этом потребление питательных веществ, таких как – белок, кальций и витамины не уменьшится.
Лабораторная работа № 3 (Решение транспортной задачи)
Для заданной матрицы издержек С, вектора – столбца запасов В в пунктах отправления и вектора - строки потребностей А в пунктах назначения решить транспортную задачу и составить отчет по следующим пунктам:
Осуществить математическую запись транспортной задачи;
Решить задачу с помощью надстройки Excel «Поиск решения»;
Изменить данные для получения открытой задачи и решить ее.
2 3 4 2 4 140С= 8 4 1 4 1 180
9 7 3 7 2 160
60 70 120 130 100
Решение
Осуществить математическую запись транспортнойзадачи.Обозначим через хij количество единиц сырья, перевозимого из i-го пункта его получения на j-тое предприятие. Тогда условие доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:
x11+x12+x13+x14+x15 =140x21+x22+x23+x24+x25 =180
x31+x32+x33+x34+x35 =160
x11 +x21 +x31 =60
x 12 +x22 +x32 =70
x 13 +x23 +x33 =120
x 14 +x24 +x34 =130
x 15 +x25 +x35=100
При этом общая стоимость перевозок составит
f(x)= 2x11+3x12+4x13+2x14+4x15 +8 x21+4x22+x23+4x24+x25+9 x31+7x32+3x33+7x34+2x35
Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений, при котором целевая функция f(x) принимает минимальное значение.
Решить задачу с помощью надстройки Excel «Поиск решения». Находим оптимальный план поставок сырья и соответствующие ему транспортные расходы в таблице 12.
Таблица 12
| Пунктыотправления | Пункты назначения | |||||
| В1 | В2 | В3 | В4 | В5 | Запасы | |
| А1 | 2 | 3 | 4 | 2 | 4 | 140 |
| А2 | 8 | 4 | 1 | 4 | 1 | 180 |
| А3 | 9 | 7 | 3 | 7 | 2 | 160 |
| Потребности | 60 | 70 | 120 | 130 | 100 | |
| Транспортная таблица | ||||||
| А1 | 140 | 0 | 0 | 0 | 0 | 140 |
| А2 | 0 | 0 | 180 | 0 | 0 | 180 |
| А3 | 0 | 0 | 0 | 0 | 160 | 160 |
| Потребности | 60 | 70 | 120 | 130 | 100 | |
| Транспортные расходы | 780 | |||||
Изменим, данные для того, чтобы получить открытую задачу. Для этого уменьшим запасы и увеличим потребности, получим:
Таблица 13
| Таблица издержек | ||||||
| Пунктыотправления | Пункты назначения | |||||
| В1 | В2 | В3 | В4 | В5 | Запасы | |
| А1 | 2 | 3 | 4 | 2 | 4 | 140 |
| А2 | 8 | 4 | 1 | 4 | 1 | 150 |
| А3 | 9 | 7 | 3 | 7 | 2 | 100 |
| Потребности | 60 | 100 | 120 | 200 | 100 | |
| Транспортная таблица | ||||||
| А1 | 0 | 0 | 0 | 140 | 0 | 140 |
| А2 | 0 | 0 | 0 | 0 | 150 | 150 |
| А3 | 0 | 0 | 0 | 0 | 100 | 100 |
| Потребности | 60 | 100 | 120 | 200 | 100 | |
| Транспортные расходы | 630 | |||||
Лабораторная работа №4 (решение задач нелинейного программирования)