Общая постановка задачи линейного программирования

Дисциплина

«Экономико-математические методы и модели»

Иллюстрационный (раздаточный) материал к теме

«Основы линейного программирования»

Санкт-Петербург-2013

Лекции 5 и 6.

Учебные вопросы:

1. Общая постановка задачи линейного программирования

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

3. Устойчивость решения ЗЛП

4. Двойственная ЗЛП. Экономическая интерпретация

Общая постановка задачи линейного программирования

Термин «математическое программирование» появился в конце 30-х годов, когда про­граммирование на компьютере еще не было развито, и соответ­ствует не очень удачному переводу английского "programming".

Большое число экономических задач сводится к линейным ма­тематическим моделям. Традиционно оптимизационные линейные математические модели называются задачами линейного програм­мирования.

Например, составление плана (программы) фирмы, завода, отрасли промышленности - одна из важнейших задач в экономике и менеджменте, может быть отнесена к программируемым задачам. Решение таких задач осложняется тем, что приходится находить значения не двух и не трех вели­чин. Число переменных может быть от нескольких десятков до нескольких сотен и даже тысяч.

Рассмотрим простейшую задачу составления производственного плана.

Задача 1. Некоторому заводу требуется составить опти­мальный план выпуска двух видов изделий при определенных возможностях четырех видов машин. План выпуска этих изде­лий надо составить так, чтобы от реализации изготовленной про­дукции завод получил наибольшую прибыль. Оба вида изделий последовательно обрабатываются этими машинами. В плане должно быть предусмотрено, что первая машина ежедневно мо­жет обрабатывать эту продукцию лишь в течение 8 ч, вторая— 12ч, третья — 12ч, четвертая — 9 ч.

В таблице указано время, необходимое для обработки каждого изделия этих двух видов (в часах). Нуль означает, что изделие машинами данного вида обрабатывать не надо.

Завод от реализации одного изделия I вида получает 4 тыс. руб., а от реализации одного изделия II вида—6 тыс. руб. прибыли.

Построим математическую модель этой задачи. Пусть — число изделий I вида, — число изделий II вида. Так как машины каж­дого вида (1, 2, 3, 4) могут обрабатывать продукцию не более (18, 12, 12, 9) часов соответственно, то получаем следующую систему ограничений:

(1)

Общая прибыль может быть выражена как

(2)

где х₁ и х₂ удовлетворяют условиям задачи (1).

Таким образом, построенная математическая модель данной за­дачи состоит из системы неравенств (1), на множестве решений ко­торой надо найти наибольшее значение целевой функции (2).

В общем виде задача линейного программирования ставится следующим образом.

Максимизировать (минимизировать) функцию

(3)

при ограничениях

(4)-(6)

(7)

Функция (3) — линейная, ограничения (4) — (6) — линейные. Задача содержит n переменных и т ограничений.

Решить задачу линейного программирования это значит найти значения управляющих переменных , удовлетво­ряющих ограничениям (4) — (6) при которых целевая фун­кция (3) принимает минимальное или максимальное значение.

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

Планирование производства

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

Формирование минимальной потребительской продоволь­ственной корзины

Задан ассортимент продуктов, имеющихся в продаже. Каждый продукт содержит определенное количество разных питательных веществ (витаминов и калорий). Известен требуемый человеку минимум питательных веществ каждого вида. Необходимо опре­делить требуемую потребительскую продовольственную корзину, имеющую минимальную стоимость.

Расчет оптимальной загрузки оборудования

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

Раскрой материала

На раскрой (распил) поступает материал нескольких видов в определенном количестве. Из этого материала необходимо изготовить различные изделия. Материал может быть раскроен разными способами. Каждый способ имеет свою себестоимость и позволяет по­лучить разное количество изделий каждого вида. Определить спо­соб раскроя, при котором суммарная себестоимость минимальна.

Составление плана реализации товара

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