84283 (Задача линейного программирования)
Описание файла
Документ из архива "Задача линейного программирования", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "математика" в общих файлах.
Онлайн просмотр документа "84283"
Текст из документа "84283"
Юридический техникум Рассмотрено и одобрено ПЦК
г. Кропоткин программирования
Председатель ПЦК
Покалицына О.В.
План
чтения лекции по учебной дисциплине
«Математические методы»
Раздел № 2. Линейное программирование.
Тема № 2.1. Виды задач линейного программирования.
Занятие №
Учебные и воспитательные цели: изучить основные виды задач линейного программирования, их математические модели.
Время
Место проведения: аудитория.
Учебные вопросы: Задача линейного программирования (ЗЛП). Трудности решения ЗЛП. Классификация задач оптимизации: задача о пищевом рационе, задача о планировании производства, задача о загрузке оборудования, задача о снабжении сырьем.
Литература:
1. Венцель Е.С. Исследование операций. Задач, принципы, методология. – М.: Наука, 1980.
2. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе. – М.:ЮНИТИДАНА, 2001
Учебные вопросы и расчет времени
№п/п | Учебные вопросы | Время, мин | Методические указания |
1. 2. 3. | Задача линейного программирования (ЗЛП). Трудности решения ЗЛП. Классификация задач оптимизации. |
-
Вводная часть. Организационный момент. План занятия. Основные требования.
-
Основная часть.
1. Задача линейного программирования (ЗЛП).
Термин линейное программирование появился в Америке в середине 40-х годов (первая американская работа по частной задаче линейного программирования опубликована в 1941 г.). В Советском Союзе исследования в этой области начались ранее. В конце 30-х годов целый ряд существенных результатов по линейному программированию был установлен Л.В. Канторовичем.
Задача линейного программирования – это задача нахождения значений параметров, обеспечивающих экстремум функции при наличии ограничений на аргументы.
Задачи линейного программирования являются самыми простыми и лучше изученными задачами. Для них характерно: показатель эффективности (целевая функция) выражается линейной зависимостью; ограничения на решения – линейные равенства или неравенства.
2. Трудности решения ЗЛП.
Трудности решения задач линейного программирования зависят от: вида зависимости, связывающей целевую функцию с элементами решения; размерности задачи, то есть от количества элементов решения х1, х2,…, xn; вида и количества ограничений на элементы решений.
3. Классификация задач оптимизации.
Задача о рациональном питании (задача о пищевом рационе).
ПОСТАНОВКА ЗАДАЧИ. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П1, П2, П3, П4; стоимость единицы каждого продукта равна соответственно С1, С2, С3, С4. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков – не менее bi единиц; углеводов – не менее b2 единиц; жиров – не менее b3 единиц. Для продуктов П1, П2, П3, П4 содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице, где aij (i=1,2,3,4; j=1,2,3) – какие – то определённые числа; первый индекс указывает номер продукта, второй – номер элемента (белки, углеводы, жиры).
продукт | элементы | ||
белки | углеводы | жиры | |
П1 П2 П3 П4 | A11A21 A31 A41 | A12 A22 A32 A42 | A13 A23 A33 A43 |
Требуется составить такой пищевой рацион (т.е. назначить количества продуктов П1, П2, П3, П4, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.
МАТЕМАТИЧЕСКУЮ МОДЕЛЬ. Обозначим x1, x2, x3, x4 количества продуктов П1, П2, П3, П4, входящих в рацион. Показатель эффективности, который требуется минимизировать, - стоимость рациона (обозначим её L): она линейно зависит от элементов решения x1, x2, x3, x4.
Система ограничений:
a11x1+a21x2+a31x3+a41x4≥b1
a12x1+a22x2+a32x3+a42x4≥b2
a13x1+a23x2+a32x3+a43x4≥b3
Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения x1, x2, x3, x4.
Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных x1, x2, x3, x4, чтобы они удовлетворяли ограничениям – неравенствам и одновременно обращали в минимум линейную функцию этих переменных:
Задача о планировании производства.
ПОСТАНОВКА ЗАДАЧИ. Предприятие производит изделия трёх видов: U1, U2, U3. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не мене b1 единиц изделия U1, не мене b2 единиц изделия U2 и не мене b3 единиц изделия U3. План может быть перевыполнен, но в определённых границах; условия спроса ограничивают количества произведённых единиц каждого типа: не более соответственно 1, 2, 3 единиц. На изготовление изделий идёт какое-то сырьё; всего имеется четыре вида сырья: s1, s2, s3, s4, причём запасы ограничены числами 1, 2, 3, 4 единиц каждого вида сырья. Теперь надо узнать какое количество сырья каждого вида идёт на изготовление каждого вида изделий. Обозначим aij количество единиц сырья вида si (I= 1, 2, 3, 4), потребное на изготовление одной единицы изделия Uj (j= 1, 2, 3). Первый индекс у числа aij – вид изделия, второй – вид сырья. Значения aij сведены в таблицу (матрицу).
Сырьё | Изделия | ||
U1 | U2 | U3 | |
S1 S2 S3 S4 | a11 a12 a13 a14 | a21 a22 a23 a24 | a31 a32 a33 a34 |
При реализации одно изделие U1 приносит предприятию прибыль c1, U2 – прибыль c2, U3 – прибыль c3. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Элементами решения будут x1, x2, x3 – количества единиц изделий U1, U2, U3, которые мы произведём. Обязательность выполнения планового задания запишется в виде трёх ограничений – неравенств: x1b1, x2b2, x3b3.
Отсутствие изделий продукции (затоваривания) даёт нам ещё три ограничения – неравенства: x11, x22, x33.
Целевая функция: L=c1x1+c2x2+c3x3→ max.
Система ограничений:
a11x1+a21x2+a31x31.
a12x1+a22x2+a32x32.
a13x1+a23x2+a33x33.
a14x1+a24x2+a34x34.
Задача о загрузки оборудования.
ПОСТАНОВКА ЗАДАЧИ. Ткацкая фабрика располагает двумя видами станков, из них N1 станков типа 1 и N2 станков типа 2. Станки могут производить три вида тканей: T1, T2, T3, но с разной производительностью. Данные aij производительности станков в таблице (первый индекс – тип станка, второй – вид ткани).
Каждый метр ткани вида T1 приносит фабрике доход c1, вида Т2 – доход с2, Т3 – доход с3.
Тип станка | Вид ткани | ||
Т1 | Т2 | Т3 | |
1 2 | а11 а21 | а12 а22 | а13 а23 |
Фабрике предписан план согласно которому она должна производить в месяц не менее b1 метров ткани Т1, b2 метров ткани Т2, b3 метров ткани Т3; количество метров каждого вида ткани не должно превышать соответственно 1, 2, 3 метров. Кроме того, все без исключения станки должны быть загружены. Требуется так распределить загрузку станков производством тканей Т1, Т2, Т3, чтобы суммарный месячный доход был максимален.
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Введём букву x с двумя индексами (первый – тип станка, второй – вид ткани). Всего будет шесть элементов решения: x11 x12 x13 x21 x22 x23 .
Здесь x11 – количество станков типа 1, занятых изготовлением ткани Т1, x12 – количество станков типа 1, занятых изготовлением ткани Т2 и т.д.
Запишем суммарный доход от производства всех видов тканей. Суммарное количество метров ткани Т1, произведённое всеми станками, будет равно a11x11+a21x21 и принесёт доход c1(a11x11+a21x21).
Целевая функция: L=c1 (a11x11+a21x21)+c2 (a12x12+a22x22)+c3 (a13x13+a23x23) → max.
Система ограничений:
Обеспечим выполнения плана ограничениями по минимальным параметрам:
a11x11+a21x21b1,
a12x12+a22x22b2,
a13x13+a23x23b3,