Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Глава 1. Линейное программирование




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

Математическое программирование возникло в 30-е годы XX века. Линейное программирование началось с работы (1938 г.) ленинградского математика Л. В. Канторовича, в которой содержались постановка и метод решения задачи о выборе наилучшей производственной программы. В 1975 году Л. В. Канторовича стал лауреатом Нобелевской премии «за вклад в теорию оптимального распределения ресурсов». Независимо линейное программирование начало развиваться и в США. В 1947 году американский учёный Дж. Данциг описал один из основных методов решения задач ЛП, получивший название «симплексный».

Укажем несколько общих ситуаций, в которых линейное программирование применяется часто и эффективно:

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

· задачи производства, целью которых является подбор наиболее выгодной производственной программы выпуска одного или нескольких видов продукции при использовании некоторого числа ограниченных источников сырья;

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

1.1. Формы модели задач линейного программирования

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

1) выбор переменных задачи;

2) составление системы ограничений;

3) выбор целевой функции.

Переменными задачи называют величины , ,…, , которые полностью характеризуют изучаемый процесс. Их обычно записывают в виде вектора .

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

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

В общем случае задача ЛП может быть записана в виде:

, (1.1)

(1.2)

, , (1.3)

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

Приведем математическую модель задачи использования ресурсов.

Для изготовления нескольких видов продукции , ,…, используют видов ресурсов , ,…, (например, различные материалы, электроэнергию и т.д.). Объём каждого вида ресурсов ограничен и известен: . Известно также количество каждого -го вида ресурса, расходуемого на производство единицы -го вида продукции. Кроме того, известна прибыль, получаемая от реализации единицы каждого вида продукции . Условие задачи можно представить в виде табл. 1.1.

 

Таблица 1.1

Вид ресурсов Объём ресурсов
...
. . . . . . . . . . . . ... ... ... ... ... ... . . .
Прибыль ...

Пусть количество каждого вида продукции, которое необходимо произвести. Для первого ресурса имеет место неравенство-ограничение

.

Аналогичные неравенства будут и для остальных видов ресурсов. Следует учитывать, что все значения , .

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

,

(1.4)

, .

Пример 1.1. Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 досок, а для изделия модели В – 4 . Фирма может получить от своих поставщиков до 1700 досок в неделю. Для каждого изделия модели А требуется 12 мин. машинного времени, а для изделия модели В – 30 мин. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В – 4 дол. прибыли?

Составим математическую модель. Пусть количество выпущенных за неделю полок модели А, а количество выпущенных за неделю полок модели В. Еженедельная прибыль выражается целевой функцией . Ограничение, наложенное на объём используемого сырья, выражается неравенством , а на количество машинного времени – . Задача состоит в том, чтобы найти наилучшие значения и . Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют еженедельную прибыль.

Итак, нужно максимизировать функцию при следующей системе ограничений:

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...