- •Методические указания
- •Тема 1. Задача линейного программирования.
- •1.1 Постановка задачи
- •1.2 Задачи на построение математической модели задач линейного программирования.
- •1.2.2 Задача на составление рациональных смесей.
- •Тема 2. Графический метод решения задач линейного программирования.
- •Тема 3. Симплексный метод решения задач линейного программирования.
- •Тема 4. Симплекс-метод с искусственным базисом.
- •Тема 5. Решение задач линейного программирования средствами табличного процессора ms Excel .
- •Тема 6. Транспортная задача.
- •Тема 7. Решение транспортной задачи средствами табличного процессора ms Excel .
- •Приложение 1
- •4. Требования к отчёту
- •4. Требования к отчёту
- •Практическая работа №3 Тема: Транспортная задача.
- •3. Задание
- •4. Требования к отчёту
- •Список использованной литературы
1.2 Задачи на построение математической модели задач линейного программирования.
1.2.1 Максимизация выпуска продукции при ограничениях на расход ресурсов.
Производственная ситуация: необходимо спланировать работу хлебокомбината на некоторый период. Установлен перечень выпускаемой продукции, известна рыночная цена каждого продукта. Для производства продукции используются ресурсы: мука, дрожжи, соль, сахар, яйца, электроэнергия, отопление, труд пекарей, и т.д. Установлен полный перечень этих ресурсов и общее количество каждого ресурса, которое может быть израсходовано в плановом периоде. Известен расход каждого ресурса на единицу каждого продукта. Необходимо определить, сколько каждой продукции нужно производить, чтобы суммарная рыночная стоимость всей продукции (выпуск, выручка) была наибольшей.
Введем обозначения:
j=1,...,n - номера (индексы) производимых продуктов;
i =1,...,m - номера (индексы) используемых ресурсов;
bi - запас i-го ресурса, т.е. допустимый расход i-го ресурса в плановом периоде;
cj - рыночная цена j-го продукта;
aij- расход i-го ресурса на производство единицы j-го продукта;
xj - плановый объем производства j-го продукта, величина неизвестная, ее нужно найти в процессе решения задачи.
Все исходные данные можно представить таблицей:
Таблица 1.1
Ресурсы |
Продукты производства |
Запасы ресурсов | |||
1 |
2 |
…j... |
n | ||
1 |
a11 |
a12 |
….. |
a1n |
b1 |
2 |
a21 |
a22 |
….. |
a2n |
b2 |
….. |
….. |
….. |
….. |
….. |
….. |
i |
….. |
….. |
aij |
….. |
|
….. |
….. |
….. |
….. |
….. |
….. |
m |
am1 |
am2 |
….. |
amn |
bm |
Цена |
c1 |
c2 |
|
cn |
|
Рассмотрим числовой пример и сформулируем задачу линейного программирования.
Пример 1. Для изготовления пяти видов продукции используется три вида сырья. Запасы сырья, нормы его расхода и цена каждого продукта приведены в таблице.
Таблица 1.2
Тип сырья |
Нормы расхода сырья на один вид выпускаемой продукции |
Запасы сырья | ||||
А |
Б |
В |
Г |
Д | ||
I |
5 |
2 |
1 |
0 |
2 |
20 |
II |
1 |
1 |
2 |
1 |
1 |
35 |
III |
1 |
903 |
3 |
2 |
3 |
40 |
Цена изделия |
12 |
7 |
18 |
10 |
20 |
|
Сформулируйте задачу линейного программирования по критерию «максимум рыночной стоимости всей продукции»
Решение:
Определим неизвестные величины - плановый объем производства видов продукции А, Б, В, Г, Д.
Мы хотим найти такой план производства ,при которых суммарная стоимость продукции будет наибольшей. Появляется еще одно понятие – критерий оптимальности: это такой экономический показатель, по которому оценивается решение задачи. В данной задаче критерий оптимальности – общая стоимость продукции. Экономисты обычно говорят в таком случае о валовом продукте в денежном выражении. Если произведенная продукция будет продана по указанным ценам, то полученные деньги составят валовой продукт или выручку. ОбозначимV – валовой продукт и запишем формулу для его вычисления в данной задаче:
В этом выражении цены умножаются на плановые объемы производства продуктов, и все суммируется. Данное выражение называют целевой функцией – это математическое выражение критерия оптимальности.
Теперь нам нужно записать математически то обстоятельство, что нельзя в производстве израсходовать больше ресурсов, чем их имеется. Запишем такое выражение для I-го ресурса:
Здесь слева от знака записан плановый расход I-го ресурса, а справа – наличие I-го ресурса. Смысл ограничения – нельзя израсходовать I-го ресурса больше, чем его имеется. Очевидно, что такие же ограничения должны быть записаны для II-го и III-го ресурсов.
Очевидно, что величины ,при которых суммарная стоимость продукции будет наибольшей, могут принимать любые положительные значения и ноль, но никак не могут быть отрицательной величиной.
Теперь приступим к созданию экономико-математической модели, т.е. к математической записи экономической задачи.
Целевая функция
при ограничениях на ресурсы