Задача линейного программирования

Юридический техникум Рассмотрено и одобрено ПЦК

г. Кропоткин программирования

Председатель ПЦК

Покалицына О.В.

План

чтения лекции по учебной дисциплине

«Математические методы»

Раздел № 2.Линейное программирование.

Тема № 2.1. Виды задач линейного программирования.

Занятие №

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

Время

Место проведения: аудитория.

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

Литература:

1. Венцель Е.С. Исследование операций. Задач, принципы, методология. – М.: Наука, 1980.

2. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе. – М.:ЮНИТИДАНА, 2001

Учебные вопросы и расчет времени

1. Вводная часть. Организационный момент. План занятия. Основные требования.

2. Основная часть.

1. Задача линейного программирования (ЗЛП).

Термин линейное программирование появился в Америке в середине 40-х годов (первая американская работа по частной задаче линейного программирования опубликована в 1941 г.). В Советском Союзе исследования в этой области начались ранее. В конце 30-х годов целый ряд существенных результатов по линейному программированию был установлен Л.В. Канторовичем.

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

Задачи линейного программирования являются самыми простыми и лучше изученными задачами. Для них характерно: показатель эффективности (целевая функция) выражается линейной зависимостью; ограничения на решения – линейные равенства или неравенства.

2. Трудности решения ЗЛП.

Трудности решения задач линейного программирования зависят от: вида зависимости, связывающей целевую функцию с элементами решения; размерности задачи, то есть от количества элементов решения х1, х2,…, xn; вида и количества ограничений на элементы решений.

3. Классификация задач оптимизации.

Задача о рациональном питании (задача о пищевом рационе).

ПОСТАНОВКА ЗАДАЧИ. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П₁, П₂, П₃, П₄; стоимость единицы каждого продукта равна соответственно С₁, С₂, С₃, С₄. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков – не менее b_i единиц; углеводов – не менее b₂ единиц; жиров – не менее b₃ единиц. Для продуктов П₁, П₂, П₃, П₄ содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице, где a_ij (i=1,2,3,4; j=1,2,3) – какие – то определённые числа; первый индекс указывает номер продукта, второй – номер элемента (белки, углеводы, жиры).

Требуется составить такой пищевой рацион (т.е. назначить количества продуктов П₁, П₂, П₃, П₄, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.

МАТЕМАТИЧЕСКУЮ МОДЕЛЬ. Обозначим x₁, x₂, x₃, x₄ количества продуктов П₁, П₂, П₃, П₄, входящих в рацион. Показатель эффективности, который требуется минимизировать, - стоимость рациона (обозначим её L): она линейно зависит от элементов решения x₁, x₂, x₃, x₄.

Целевая функция:

Система ограничений:

a₁₁x₁+a₂₁x₂+a₃₁x₃+a₄₁x₄≥b₁

a₁₂x₁+a₂₂x₂+a₃₂x₃+a₄₂x₄≥b₂

a₁₃x₁+a₂₃x₂+a₃₂x₃+a₄₃x₄≥b₃

Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения x₁, x₂, x₃, x₄.

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных x₁, x₂, x₃, x₄, чтобы они удовлетворяли ограничениям – неравенствам и одновременно обращали в минимум линейную функцию этих переменных:

Задача о планировании производства.

ПОСТАНОВКА ЗАДАЧИ. Предприятие производит изделия трёх видов: U₁, U₂, U₃. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не мене b₁ единиц изделия U₁, не мене b₂ единиц изделия U₂ и не мене b₃ единиц изделия U₃. План может быть перевыполнен, но в определённых границах; условия спроса ограничивают количества произведённых единиц каждого типа: не более соответственно b₁, b₂, b₃ единиц. На изготовление изделий идёт какое-то сырьё; всего имеется четыре вида сырья: s₁, s₂, s₃, s₄, причём запасы ограничены числами g₁, g₂, g₃, g₄ единиц каждого вида сырья. Теперь надо узнать какое количество сырья каждого вида идёт на изготовление каждого вида изделий. Обозначим a_ij количество единиц сырья вида s_i (I= 1, 2, 3, 4), потребное на изготовление одной единицы изделия U_j (j= 1, 2, 3). Первый индекс у числа a_ij – вид изделия, второй – вид сырья. Значения a_ijсведены в таблицу (матрицу).

При реализации одно изделие U₁ приносит предприятию прибыль c₁, U₂ – прибыль c₂, U₃ – прибыль c₃. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Элементами решения будут x₁, x₂, x₃ – количества единиц изделий U₁, U₂, U₃, которые мы произведём. Обязательность выполнения планового задания запишется в виде трёх ограничений – неравенств: x₁³b₁, x₂³b₂, x₃³b₃.

Отсутствие изделий продукции (затоваривания) даёт нам ещё три ограничения – неравенства: x₁£b₁, x₂£b₂, x₃£b₃.

Целевая функция: L=c₁x₁+c₂x₂+c₃x₃→ max.

Система ограничений:

a₁₁x₁+a₂₁x₂+a₃₁x₃£¡₁.

a₁₂x₁+a₂₂x₂+a₃₂x₃£¡₂.

a₁₃x₁+a₂₃x₂+a₃₃x₃£¡₃.

a₁₄x₁+a₂₄x₂+a₃₄x₃£¡₄.

Задача о загрузки оборудования.

ПОСТАНОВКА ЗАДАЧИ. Ткацкая фабрика располагает двумя видами станков, из них N1 станков типа 1 и N2 станков типа 2. Станки могут производить три вида тканей: T1, T2, T3, но с разной производительностью. Данные a_ijпроизводительности станков в таблице (первый индекс – тип станка, второй – вид ткани).

Каждый метр ткани вида T1 приносит фабрике доход c₁, вида Т2 – доход с₂, Т3 – доход с₃.

Фабрике предписан план согласно которому она должна производить в месяц не менее b₁ метров ткани Т1, b₂ метров ткани Т2, b₃ метров ткани Т3; количество метров каждого вида ткани не должно превышать соответственно b₁, b₂, b₃ метров. Кроме того, все без исключения станки должны быть загружены. Требуется так распределить загрузку станков производством тканей Т1, Т2, Т3, чтобы суммарный месячный доход был максимален.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Введём букву x с двумя индексами (первый – тип станка, второй – вид ткани). Всего будет шесть элементов решения: x₁₁x₁₂x₁₃x₂₁x₂₂x₂₃ .

Здесь x₁₁ – количество станков типа 1, занятых изготовлением ткани Т1, x₁₂ – количество станков типа 1, занятых изготовлением ткани Т2 и т.д.

Запишем суммарный доход от производства всех видов тканей. Суммарное количество метров ткани Т1, произведённое всеми станками, будет равно a₁₁x₁₁+a₂₁x₂₁ и принесёт доход c₁(a₁₁x₁₁+a₂₁x₂₁).

Целеваяфункция: L=c₁ (a₁₁x₁₁+a₂₁x₂₁)+c₂ (a₁₂x₁₂+a₂₂x₂₂)+c₃ (a₁₃x₁₃+a₂₃x₂₃) → max.

Система ограничений:

Обеспечим выполнения плана ограничениями по минимальным параметрам:

a₁₁x₁₁+a₂₁x₂₁³b₁,

a₁₂x₁₂+a₂₂x₂₂³b₂,

a₁₃x₁₃+a₂₃x₂₃³b₃,

После этого ограничим выполнение плана по максимальным параметрам:

a₁₁x₁₁+a₂₁x₂₁£b₁,

a₁₂x₁₂+a₂₂x₂₂£b₂,

a₁₃x₁₃+a₂₃x₂₃£b₃,

Теперь запишем ограничения, связанные с наличием оборудования и его полной загрузкой. Суммарное количество станков типа 1, занятых изготовлением всех тканей, должно быть равно N1; типа 2 – N2.

x₁₁+x₁₂+x₁₃=N1,

x₂₁+x₂₂+x₂₃=N2,

Задача о снабжении сырьём.

ПОСТАНОВКА ЗАДАЧИ. Имеется три промышленных предприятия: П₁, П₂, П₃, требующих снабжения определённым видом сырья. Потребности в сырье каждого предприятия равны соответственно a₁, a₂, a₃ единиц. Имеются пять сырьевых баз, расположенных от предприятий на каких – то расстояниях и связанных с ними путями сообщения с разными тарифами. Единица сырья, получаемая предприятием П_ic базы Б_{j ,} обходится предприятию в с_ijрублей (первый индекс – номер предприятия, второй – номер базы).

Возможности снабжения сырьём с каждой базы ограничены её производственной мощностью: базы Б₁, Б₂, Б₃, Б₄, Б₅ могут дать не более b₁, b₂, b₃, b₄, b₅ единиц сырья. Требуется составить такой план снабжения предприятий сырьём (с какой базы, куда и какое количество сырья везти), чтобы потребности предприятий были обеспечены при минимальных расходах на сырьё.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Обозначим x_ijколичества сырья с j – ой базы. Всего план будет состоять из 15 элементов решения: x₁₁x₁₂x₁₃x₁₄x₁₅ x₂₁x₂₂x₂₃x₂₄x₂₅x₃₁x₃₂x₃₃x₃₄x_35.

Целевая функция:

Система ограничений:

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅=a₁,

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅=a₂,

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅=a₃,

x₁₁+x₂₁+x₃₁£b₁,

x₁₂+x₂₂+x₃₂£b₂,

x₁₃+x₂₃+x₃₃£b₃, (4.3.)

x₁₄+x₂₄+x₃₄£b₄,

x₁₅+x₂₅+x₃₅£b₅,