Лекции по линейному программированию
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 4.00 (1 Голос)

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

 

РАЗРАБОТКА МОДЕЛЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

Термин “разработка” дословно означает построение моделей ЛП практических задач. Это скорее искусство, которое постигается с опытом.

Отметим основные этапы этой задачи:

·  определение переменных задачи;

·  представление ее ограничений в виде линейных уравнений или неравенств;

·  задание линейной целевой функции, подлежащей минимизации или максимизации.

Пример разработки модели задачи технического контроля.

Предположим, что в отделе технического контроля (ОТК) некоторой фирмы работают контролеры двух категорий. Норма выработки ОТК за 8-ми часовую смену - не менее 1800 изделий. Контролер I категории проверяет 25 изделий в час, и не допускает ошибок в 98% случаев. Контролер II категории, соответственно, проверяет 15 изделий в час, его точность составляет 95%.

Зарплата контролера I категории - 4$ в час, контролер II категории получает 3$ в час. Вместе с тем, при каждой ошибке контролера фирма несет убытки в размере 2$.

Фирма может использовать не более 8 контролеров I категории и 10 контролеров II категории.

ЗАДАЧА: подобрать оптимальный состав ОТК, при работе которого, фирма бы несла минимальные затраты.

Разработка модели: Пусть и Количество контролеров I и II категории в отделе. Их число ограничено

В смену необходимо проверять не менее 1800 изделий. Следовательно необходимо выполнение неравенства

Или, после упрощения

В расходах фирмы отмечаются два момента: зарплата контролера и его ошибки.

Расходы фирмы на контролера I категории: в час, на контролера II категории: в час.

Таким образом, функция

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

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

Задача, в которой требуется обратить в максимум (минимум) целевую функцию

При условиях

(I. 1.1.)

Называется общей задачей линейного программирования в произвольной форме.

Вектор , удовлетворяющий ограничениям задачи линейного программирования называется ее решением или Планом. Если при этом переменные еще и неотрицательны, то план является допустимым. Множество всех допустимых планов, образуют Область допустимых решений (ОДР) задачи ЛП. Это выпуклое[1] многогранное множество. Поэтому задачи ЛП являются частным случаем более общих задач Выпуклого программирования.

Допустимый план, соответствующий крайней[2] точке ОДР, является Опорным планом, либо Допустимым базисным решением задачи ЛП.

Допустимый план, обращающий в максимум (минимум) целевую функцию, называется Оптимальным планом задачи ЛП.

Теорема (ЛП): Пусть допустимое множество задачи ЛП является многогранником (в обобщенном смысле). Если целевая функция принимает максимальное (минимальное) значение в некоторой точке множества , то она (точка) является крайней точкой для . Если целевая функция принимает максимальное (минимальное) значение более, чем в одной точке, то она принимает это же значение и в любой их выпуклой комбинации: Здесь Внутренняя точка отрезка ; Граничная точка отрезка или крайняя точка ОДР; Некоторый числовой параметр, “пробегающий” все значения из отрезка .

[1] Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую линейную комбинацию (линейную оболочку).

[2] Две граничные точки некоторого отрезка, состоящего из граничных точек ОДР, называются крайними. Точка называется граничной для некоторого множества точек, если для любого сколь угодно малого в окрестности ее находятся и точки множества, и точки ему не принадлежащие.

Задача линейного программирования - 4.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство