Методы математического программирования для решения задач

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

Сущность метода моделирования состоит в том, что наряду с системой (оригиналом) , рассматривается ее образ - модель, в качестве которой выступает некоторая другая система - , представляющая собой образ оригинала при частично определенном моделирующем отображении (т. е. не все черты состава и структуры оригинала отражаются моделью) f. .

Одно из достоинств метода моделирования состоит в возможности построения моделей с “удобной” структурой, что делает исследование модели более легким, чем исследование оригинала.

Цель

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

Задачи

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

. Геометрическая интерпретация и графический метод решения ЗЛП

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

1.1 Цель

Усвоить алгоритм решения задач линейного программирования графическим методом.

1.2 Задачи

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

1.3 Алгоритм решения

С учетом системы ограничений строим область допустимых решений

Строим вектор наискорейшего возрастания целевой функции - вектор градиентного направления.

Проводим произвольную линию уровня

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

Определяем оптимальный план и экстремальное значение целевой функции .

1.4 Пример решения задачи

Гражданин, отделившийся от сельскохозяйственного предприятия, решил заняться фермерским хозяйством, средняя доля по району составила 6 гектар. В долевую собственность вошло две семьи из 13 человек (13*6 = 78) итого в собственность они получили 78 га и решил взять в аренду ещё 290 га. Итого, в общем, площадь составила 368 га.

Комиссия предложило целевое направление, выслушав мнение будущего фермера, выращивание овощной продукции, как капуста и морковь.

У гражданина имеется в наличии 5 тыс. чел/час трудовых ресурсов, 1100 кг действующего вещества удобрений.

Капуста и морковь характеризуются такими показателями, как:

затраты труда на обработку 1 га капусты 11 чел/час, моркови - 9 чел/час;

затраты удобрений на обработку 1 га капусты 4 кг.д.в., моркови - 5 кг.д.в.

урожайность капусты составляет 260 ц/га, моркови - 196 ц/га.

Выход продукции в рублях: капуста 182000 руб с га, морковь 117600 руб с га.

Урожайность составляет: капуста 260 ц, морковь 196 ц.

С учётом севооборота морковью занять не менее 75 га. Капусту требуется получить по условию контракта не менее 23000 ц. Найти оптимальное сочетание этих двух культур.

Решение

Экономико-математическая модель:

Переменные:

Х1 - площадь под капусту, га;

Х2 - площадь под морковь, га.

Ограничения:

. По использованию пашни, га: Х1 + Х2 ≤ 368.

. По использованию и наличию трудовых ресурсов, чел/час: 11Х1 + 9Х2 ≤ 5000.

. По использованию и наличию удобрений, кг.д.в.: 4Х1 + 5Х2 ≤ 1100.

. По площади под морковь, га: Х2 ≥ 75.

. Ограничения по производству капусты, ц: 260Х1 ≥ 23000

Условие неотрицательности: Х1 ≥ 0 и Х2 ≥ 0.

Целевая функция: Z = 182000Х1 + 117600Х2 => max.

Построение матрицы модели

Таблица 1 Матрица модели

В результате получили математическую модель:

Z(x) = 182000X1 + 117600X2 => max.+ X2 ≤ 368,

X1 + 9X2 ≤ 5000,

4X1 + 5X2 ≤ 1100,

X2 ≥ 75,

X1 ³ 23000,

X1,X2 ≥ 0.

Решаем задачу:

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

Строим систему координат Х1ОХ2. Строим прямые

X1 + X2 = 368 11X1 + 9X2 =5000 4X1 + 5X2 = 1100

X2 = 75 260X1 = 23000.

Х2

C

В

А С

Х1

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

Полученные прямые делят плоскость на две полуплоскости. Для того чтобы узнать, какая именно из этих полуплоскостей отвечает данным неравенствам, подставляем координаты любой точки в неравенство. Полуплоскость, в которой лежит точка, для которой неравенство верно, соответствует неравенству. Например, координаты т.О (0,0) подставляем в неравенство X1 + X2 ≤ 368, 0+0 ≤ 368, следовательно полуплоскость, которой принадлежит т. О соответствует неравенству. Следовательно, эту область заштриховываем (рис.1). Область АВC соответствует всем неравенствам, следовательно это область допустимых решений (в ней пересекаются все штрихи).

. Строим вектор градиент N (182000, 117600). Начало вектора в т. О(0,0).

. Z0 линия уровня нуль - проходит через точку О (0;0), Z0 ┴ C.

. Линию уровня Z двигаем вдоль вектора градиента C (182000, 117600). Функция достигает min в точке А, max в точке С.

. Находим координаты точки С из системы уравнений:

Х2 = 75,

Х1 + 5Х2 =1100.

C (181,25; 75)

Z = 182600 · 181,25 + 117600 · 75 = 32987500 + 8820000 = 41807500

Ответ: Максимальная стоимость продукции составит 41807500 руб., если площадь посева капусты составит 181,25 га и площадь посева моркови 75 га.

1.5 Задачи

Составить экономико-математическую модель и решить графическим методом

Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа - 3 т, проволоки - 18 т. На один трансформатор первого вида расходуются 5 кг железа и 3 кг проволоки, а один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д. е., второго - 4 д. е.

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

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

Таблица 1.2 Исходные данные

Лицей арендует сельскохозяйственные земли на площади 150 гектар и хочет заняться выращиванием такой растениеводческой продукции как сахарная свёкла и картофель.

У гражданина имеется в наличии 4 тыс. чел/час трудовых ресурсов, 1000 кг. д.в. удобрений.

Сахарная свекла и морковь, характеризуются такими показателями как:

затраты труда на обработку 1 га сахарной свеклы 11 чел/час, картофель - 6 чел/час;

затраты удобрений на обработку 1 га сахарной свеклы 5 кг.д.в., моркови - 2 гк.д.в.

урожайность сахарной свеклы составляет 215 ц/га, картофеля - 175 ц/га.

Выход продукции в рублях: сахарной свёклы 95600 руб./ га, картофеля - 85000 руб./ га. С учётом севооборота картофелем занять не менее 55 гектаров. Сахарную свёклу требуется получить по условию контракта не более 13000 центнеров. Найти оптимальное сочетание этих двух культур.

В хозяйстве производится молоко, а также зерно для продажи и на корм скоту. На продажу используется 60% зерна. По условиям содержания животных на ферме хозяйство может содержать не более 110 коров. Общая площадь пашни в севообороте, выделенная для посева зерновых - 1500 га. Трудовые ресурсы хозяйства составляют 12000 чел.-ч. Норма трудозатрат при производстве при производстве зерна - 5 чел.-ч./га, при производстве молока - 50 чел.-ч./гол.. Урожайность пшеницы - 25 ц.к.е./га. Норма кормления коров - 80 ц.к.е./гол., продуктивность молочного стада - 4000 кг./гол. Плановое задание по молоку составляет 400 ц. Доход хозяйства определяется продажей молока и товарного зерна. Чистый доход от продажи одного центнера зерна 10 руб, одного кг молока -0,2 руб. Необходимо определить сочетание двух отраслей хозяйства, обеспечивающее максимум чистого дохода.

Продукция двух видов (краска для внутренних и наружных работ) поступает в оптовую продажу. Для производства красок используется два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 т., соответственно. Расходы продуктов А и В на 1 т соответствующих красок приведены в таблице.

Таблица 1.3 Исходные данные

Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т. в сутки. Оптовые цены одной тонны красок равны 3000 ден. Ед. для краски Е и 2000 ден. Ед. для краски I. Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Организации, занимающейся перевозкой и продажей продукции, необходимо перевезти партию товара. При этом можно арендовать для перевозки по железной дороге пяти и семи тонные контейнеры. Пятитонных контейнеров имеется в наличии не более 12 штук, а семитонных не более 18 штук. На перевозку всей продукции по смете выделено не более 60000 рублей, причем цена за аренду пятитонного контейнера - 2000 рублей, а семитонного - 3000 рублей. Определить, сколько и каких контейнеров следует арендовать, при условии, что общий объем грузоперевозок должен быть максимальным.

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

Таблица 1.4 Исходные данные

В месяц используется 60000 тонн горючего. Потребность в рабочей силе не превышает 700 человек. Определите количество судов 1 и 2 типа, чтобы обеспечить максимальный доход, который составляет от эксплуатации судов 1 типа 20 млн.руб., а 2 типа-10 млн.руб. в месяц.

Фермерское хозяйство занимается производством и реализацией астениеводческой продукции. На нее имеются следующие ограниченные ресурсы: посевная площадь 600 га, семена пшеницы 400 ц, ячменя 300 ц, удобрений 5000 кг. Найти оптимальное сочетание сельскохозяйственных культур для получения максимальной прибыли.

Таблица 1.5 Исходные данные

1.5.2 Решить задачи графическим методом

=> max (min),

2.2 Z(x) = -2x1 + 5x2 → max (min)

Z (x) = x1 + 6x2 → max (min)

=> max (min)

Z (x) = x1 + x2 → max (min)

Z (x) = -2x1 + 6x2 → max (min)

• Симплексный метод решения задачи линейного программирования
• Освоение ППП SIMPLEX - пакет линейной оптимизации
• Компьютерная реализация задач линейного программирования стандартными офисными средствами (в среде пакета Excel)
• Задачи распределительного типа, решаемые в землеустройстве
• Освоение ППП PER - пакета экономических расчетов. Решение транспортной задачи