Учебные материалы


Линейное программирование



Карта сайта jefferybuild.com

Термин "программирование", вошедший в отечественную экономическую литературу в 60-е годы XX в., имеет несколько значений. Во-первых, этим термином обозначается процесс подготовки специальной программы для ЭВМ; во-вторых, программирование используется как некоторый синоним терминов "планирование" и "прогнозирование". В последнем случае обычно говорят об оптимальном программировании, понимая под этим методы разработки планов и программ, позволяющих оптимизировать некоторые стороны деятельности хозяйствующего субъекта. Особенность методов оптимального программирования заключается в активном использовании достаточно сложных экономико-математических методов. Оптимальное программирование включает несколько разделов, различающихся разной степенью проработанности и практической приложимости: линейное, квадратическое, динамическое программирование и др.

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

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

Пример 2.15.Фабрика по производству чая выпускает две марки этого продукта. Условное наименование марок - А и В. Отпускная цена чая марки А - 60 руб. за килограмм, марки В - 50 руб. за килограмм. Каковы должны быть оптимальные годовые объемы производства чая обеих марок, чтобы выручка фабрики от их реализации была максимальной?

Пусть оптимальный объем производства чая марки А составит X тонн в год, а марки В - у тонн в год. Суммарная выручка от их реализации составит (60x + 50y) тыс. руб. Решение задачи подразумевает поиск такой комбинации (х, у), которая позволила бы обеспечить максимум этой функции, т.е. поиск

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

При изготовлении чайных смесей разных марок используют чайный лист двух сортов: в состав чая марки А входит 70% 1-го сорта и 30% 2-го сорта, в состав марки В - 20% 1-го сорта и 80% 2-го сорта. Стоимость сырья 1-го сорта составляет 38 руб. за килограмм, 2-го сорта - 24 руб./кг. Таким образом, себестоимость чайного листа, необходимого для производства одного килограмма чая марки А, составляет 33,8 руб. (0,7 ∙ 38 + 0,3 ∙ 24 = 33,8), а марки В - 26,8 руб. (0,2 ∙ 38 + 0,8 ∙ 24 = 26,8).

Фабрика может тратить на закупку сырья не более 9000 тыс. руб. в год. Следовательно, на объем выпуска накладывается еще одно ограничение финансового порядка:

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

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

На рис. 2.3 прямая 1 соответствует производственному ограничению, прямая 2 - финансовому; двум оставшимся ограничениям соответствуют сами оси х и у. Таким образом, удовлетворяющие всем ограничениям значения (х, у) лежат в заштрихованной области. Какая же точка этого пятиугольника будет искомым решением? Нам требуется найти такое значение К, которое позволило бы максимизировать целевую функцию на заштрихованной области. Для этого рассмотрим множество функций вида

Загрузка...

Три из этих функций приведены на рис. 2.3 пунктирными прямыми. Чем дальше по направлению стрелок от центра координат находится прямая, тем большему значению Кi она соответствует. Очевидно, что на заштрихованной области функция (60x + 50у) примет максимальное значение в точке пересечения прямых 1 и 2. Следовательно, координаты этой точки будут искомым оптимальным решением, максимизирующим целевую функцию.

Найденное алгебраическим методом решение этой системы уравнений будет таким:

Именно такое соотношение объемов выпуска чая сортов А и В позволит фабрике при существующих технологических и финансовых ограничениях получить максимальный объем выручки.

Существует множество компьютерных программ, позволяющих отыскивать решения в задачах с десятками и даже сотнями параметров и ограничений. Рассмотренный нами в примере 2.15 случай представлял собой задачу оптимизации выпуска при двухпродуктовом производстве (марки А и В). Реальные же предприятия в подавляющем большинстве случаев выпускают гораздо более широкую номенклатуру продукции, вовлекая при этом в производство не два, как в примере 2.15 (1-й и 2-й сорта), а сотни и тысячи видов различных ресурсов. Ограничения могут касаться не только технологических и финансовых возможностей предприятия (т.е. характеристик производства "на входе"), но и особенностей получаемых отходов и побочных продуктов, уровня загрязнения окружающей среды с учетом действующего экологического законодательства и других факторов (т.е. характеристик производства "на выходе"). В отдельных случаях весьма существенными оказываются ограничения по времени, например, если предприятие испытывает сложности с поставками сырья в определенные периоды в течение года.

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

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

Задача составления расписания заключается в таком структурировании времени работы коллектива предприятия, которое было бы максимально удобно для всех его сотрудников и клиентов. Особенно актуальна эта проблема для предприятий сферы услуг, а также образовательных учреждений. Например, если известно, что максимальное количество покупателей приходит в магазин с 15 до 19 часов по будним дням и с 11 до 16 часов по субботам и воскресеньям, то и количество сотрудников, чьи рабочие часы приходятся на это время, должно соответствовать наплыву клиентов. График работы смен должен обеспечивать максимальную численность персонала в торговом зале именно в эти часы. Составление графика работы сотрудников на таких предприятиях можно считать задачей линейного программирования. Типичная постановка задачи линейного программирования в данном случае такова: максимизация количества обслуженных покупателей при имеющихся ограничениях, касающихся количества сотрудников, а также с учетом требований законодательства по поводу продолжительности рабочего дня и количества выходных дней в неделю для каждого сотрудника.

В анализе размещения и использования ресурсов и в процессе планирования метод линейного программирования находит весьма широкое применение.

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



edu 2018 год. Все права принадлежат их авторам! Главная