Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Постановка задачи линейного программирования
|
|
Тема 5. Лекция 5.
Условная оптимизация.
Линейное программирование.
1. Пример постановки задачи оптимизации
2. Линейное программирование (ЛП)
2.1. Постановка задачи линейного программирования
2.2. Основные определения и теоремы
2.3. Переход от одной формы задачи ЛП к другой
3. Методы решения задач нелинейного программирования. Геометрическая интерпретация
Пример постановки задачи оптимизации
Для изготовления 3-х видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия приведены в таблице.
| Тип оборудования | Затраты времени (станко-ч.) на обработку одного изделия вида | Общий фонд рабочего времени | ||
| А | В | С | ||
| Фрезерное | ||||
| Токарное | ||||
| Сварочное | ||||
| Шлифовальное | ||||
| Прибыль |
Определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Составить математическую модель задачи.
Решение.
Пусть будет изготовлено Х1 единиц изделия А
Х2 единиц изделия В
Х3 единиц изделия С.
Тогда при использовании фрезерного оборудования потребуется затратить 2Х1 + 4Х2 + 5Х3 станко-часов.
Но по условию ограничения общего фонда времени
2Х1 + 4Х2 + 5Х3 £ 120.
Аналогично для токарного, сварочного и шлифовального оборудования:
Х1 + 8Х2 + 6Х3 £ 280
7Х1 + 4Х2 + 5Х3 £ 240
4Х1 + 6Х2 + 7Х3 £ 360
При этом, т.к. количество изготовляемых деталей не может быть отрицательным, то
Х1 ³ 0, Х2 ³ 0, Х3 ³ 0.
Далее, если будет изготовлено Х1 изделий А, Х2 изделий В и Х3 изделий С, то прибыль от их реализации составит
F = 10Х1 + 14Х2 + 12Х3
Итак, мы получаем систему четырех линейных неравенств с тремя неизвестными (Xj (j = 1…3):
2Х1 + 4Х2 + 5Х3 £ 120
Х1 + 8Х2 + 6Х3 £ 280
7Х1 + 6Х2 + 7Х3 £ 360
Х1 ³ 0, Х2 ³ 0, Х3 ³ 0.
и линейную функцию F = 10Х1 + 14Х2 + 12Х3 относительно этих же переменных.
Требуется среди всех неотрицательных решений системы неравенств найти такое, при котором целевая функция F принимает максимальное значение.
Линейное программирование
Постановка задачи линейного программирования
Найти оптимум (наибольшее или наименьшее значение) целевой функции (линейной формы)
на области допустимых значений системы ограничений
при наличии дополнительных условий неотрицательности переменных
хj ³ 0, j = 1, …, n.
Если в системе ограничений l = m, т.е. она состоит только из уравнений, то соответствующая форма записи называется канонической.