Общая постановка задачи линейного программирования Дисциплина
«Экономико-математические методы и модели»
Иллюстрационный (раздаточный) материал к теме
«Основы линейного программирования»
Санкт-Петербург-2013
Лекции 5 и 6.
Учебные вопросы:
1. Общая постановка задачи линейного программирования
2. Графический метод решения ЗЛП. Понятие о симплекс-методе
3. Устойчивость решения ЗЛП
4. Двойственная ЗЛП. Экономическая интерпретация
Общая постановка задачи линейного программирования
Термин «математическое программирование» появился в конце 30-х годов, когда программирование на компьютере еще не было развито, и соответствует не очень удачному переводу английского "programming".
Большое число экономических задач сводится к линейным математическим моделям. Традиционно оптимизационные линейные математические модели называются задачами линейного программирования.
Например, составление плана (программы) фирмы, завода, отрасли промышленности - одна из важнейших задач в экономике и менеджменте, может быть отнесена к программируемым задачам. Решение таких задач осложняется тем, что приходится находить значения не двух и не трех величин. Число переменных может быть от нескольких десятков до нескольких сотен и даже тысяч.
Рассмотрим простейшую задачу составления производственного плана.
Задача 1. Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий при определенных возможностях четырех видов машин. План выпуска этих изделий надо составить так, чтобы от реализации изготовленной продукции завод получил наибольшую прибыль. Оба вида изделий последовательно обрабатываются этими машинами. В плане должно быть предусмотрено, что первая машина ежедневно может обрабатывать эту продукцию лишь в течение 8 ч, вторая— 12ч, третья — 12ч, четвертая — 9 ч.
В таблице указано время, необходимое для обработки каждого изделия этих двух видов (в часах). Нуль означает, что изделие машинами данного вида обрабатывать не надо.
Изделие
| Станок
| 1-й
| 2-й
| 3-й
| 4-й
| I
|
| 0,5
|
|
| II
|
|
|
|
| Время
работы станка
(в часах)
|
|
|
|
|
Завод от реализации одного изделия I вида получает 4 тыс. руб., а от реализации одного изделия II вида—6 тыс. руб. прибыли.
Построим математическую модель этой задачи. Пусть — число изделий I вида, — число изделий II вида. Так как машины каждого вида (1, 2, 3, 4) могут обрабатывать продукцию не более (18, 12, 12, 9) часов соответственно, то получаем следующую систему ограничений:
(1)
Общая прибыль может быть выражена как
(2)
где х1 и х2 удовлетворяют условиям задачи (1).
Таким образом, построенная математическая модель данной задачи состоит из системы неравенств (1), на множестве решений которой надо найти наибольшее значение целевой функции (2).
В общем виде задача линейного программирования ставится следующим образом.
Максимизировать (минимизировать) функцию
(3)
при ограничениях
(4)-(6)
(7)
Функция (3) — линейная, ограничения (4) — (6) — линейные. Задача содержит n переменных и т ограничений.
Решить задачу линейного программирования это значит найти значения управляющих переменных , удовлетворяющих ограничениям (4) — (6) при которых целевая функция (3) принимает минимальное или максимальное значение.
Примеры типичных экономических и производственных задач, оптимальное решение которых может быть найдено с помощью построения соответствующих линейных математических моделей.
Планирование производства
Для изготовления различных видов изделий используются разные ресурсы. Общие запасы каждого ресурса, количество ресурса каждого типа, затрачиваемого на изготовление одного изделия каждого вида, и прибыль, получаемая от реализации одного изделия каждого вида, заданы. Нужно составить план производства изделий, обеспечивающий максимальную суммарную прибыль от реализации изделий.
Формирование минимальной потребительской продовольственной корзины
Задан ассортимент продуктов, имеющихся в продаже. Каждый продукт содержит определенное количество разных питательных веществ (витаминов и калорий). Известен требуемый человеку минимум питательных веществ каждого вида. Необходимо определить требуемую потребительскую продовольственную корзину, имеющую минимальную стоимость.
Расчет оптимальной загрузки оборудования
Предприятию необходимо выполнить производственный заказ на имеющемся оборудовании. Для каждой единицы оборудования заданы: фонд рабочего времени, себестоимость на изготовление единицы продукции каждого вида и производительность, т.е. число единиц продукции каждого вида, которое можно произвести в единицу времени. Нужно распределить изготовление продукции между оборудованием таким образом, чтобы себестоимость всей продукции была минимальна.
Раскрой материала
На раскрой (распил) поступает материал нескольких видов в определенном количестве. Из этого материала необходимо изготовить различные изделия. Материал может быть раскроен разными способами. Каждый способ имеет свою себестоимость и позволяет получить разное количество изделий каждого вида. Определить способ раскроя, при котором суммарная себестоимость минимальна.
Составление плана реализации товара
Фирма реализует различные товары, используя при этом определенный набор средств (технических, людских, денежных). Общий запас средств, число средств каждого вида, используемых при реализации единицы любого товара и прибыль от его продажи заданы. Надо сформировать план реализации товаров, приносящий фирме максимальную прибыль.
|