Лекция № 2. Общая задача линейного программирования

Транспортная задача

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

Задача о выпуске продукции

Задача о диете

Исторические задача о диете является одной из первых задач линейного программирования.

Постановка задачи - первый и наиболее важный этап построения модели, способный обеспечить правильное решение проблемы.

Даме необходимо похудеть, за помощью обратилась к подруге.

Построение модели - рассмотрение этого этапа и является главной целью.

Подруга посоветовала перейти на рациональное питание, состоящее из двух продуктов P и Q.

Суточное питание этими продуктами должно давать не более 14 единиц жира (чтобы похудеть), но не менее 300 калорий. На упаковке продукта Р написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150 калорий, а на упаковке с продуктом Q - 4 единицы жира и 200 калорий соответственно. При этом цена 1 килограмма продукта Р равна 15 руб., а 1 кг продукта Q - 25 руб.

Так как дама была стеснена в средствах, но ее интересовал вопрос: в какой пропорции нужно брать эти продукты для того, чтобы выдержать условия диеты и истратить как можно меньше денег?

Перейдем к формализации данной ситуации на языке математических символов.

Обозначим через х количество продукта Р и через у количество продукта Q, требуемые для выполнения условий диеты.

Количество единиц жира, содержащегося в х кг продукта Р и в у кг продукта Q, равно 15 х + 4 и по условию диеты не должно превосходить 14:

В свою очередь, количество калорий, содержащихся в х кг продукта Р и в у кг продукта Q, равно 150 х + 200 у и по условию диеты должно быть не меньше 300:

Теперь о стоимости z продуктов. Она равна

и в соответствии с высказанными пожеланиями должна быть минимальной.

Последнее записывается так:

Тем самым мы получили систему формул:

которую решим графическим способом.

Нас интересует только та ее часть, которая лежит над треугольником BDE. Вычисляя значения z во всех трех вершинах этого треугольника

и сравнивая полученные результаты, замечаем, что наименьшее значение (35) достигается в вершине Е. Таким образом,

и искомая пропорция - 2: 3.

Фирма выпускает два вида древесно-стружечных плит - обычные и улучшенные. При этом производится две основные операции - прессование и отделка. Требуется указать, какое количество плит каждого типа можно изготовить в течение месяца так, чтобы обеспечить максимальную прибыль при следующих ограничениях на ресурсы (материал, время, затраты):

Затраты	Партия из 100 плит	Имеющиеся ресурсы на месяц
обычных	улучшенных
Материал (фунты) Время на прессование (часы) Время на отделку (часы) Средства (деньги)	20 4 4 30	40 6 4 50	4000 900 600 6000
Прибыль			max

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

х - количество партий в 100 плит обычного вида, изготавливаемых в течение месяца;
у - количество партий в 100 плит улучшенного качества, изготавливаемых в течение месяца.

Тогда ожидаемую прибыль можно записать так:

Требуется найти такие значения х и у, подчиненные условиям

для которых

Для того, чтобы найти в первой четверти плоскости хОу множество точек, координаты (х, у) которых удовлетворяют указанным выше неравенствам, необходимо сначала построить прямые (по точкам их пересечения с координатными осями)

а затем, используя точку начала отсчета О (0, 0), определить соответствующие полуплоскости. Пересечением полученных полуплоскостей будет четырехугольник ОВМЕ.

Наша целевая функция достигает наибольшего значения в одной из вершин четырехугольника.

Нам необходимо найти координаты точки М - точки пересечения прямых EF и АВ, для этого надо решить систему уравнений

Вычислить значения z в точках В (0, 100), Е (150, 0), М (100, 50):

Из полученных значений выберем наибольшее и получим ответ:

В общем случае и число неизвестных, и число ограничений могут достигать десятков, сотен, тысяч и т.д. Однако набор соответствующих условий ничем (кроме количества) от рассмотренных выше примеров не отличается. Это нетрудно заметить уже по общей постановке задачи линейного программирования.

Стандартная математическая формулировка общей задачи линейного программирования выглядит так: требуется найти экстремальное значение показателя эффективности (целевой функции)

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

где - заданные числа.

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

Общую постановку задачи линейного программирования можно записать в более компактной форме, если воспользоваться следующим правилом.

Правило сокращенного суммирования. Для обозначения суммы чисел :

принята такая запись:

где ∑ - знак суммирования, а k - индекс суммирования.

Это обозначение очень удобно:

А вот как выглядит запись общей задачи линейного программирования:

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

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

Пример 1. Рассмотрим транспортную задачу, заданную таблицей

	В	Наличие
А
Запрос

Решение. Пусть - искомое число единиц товара, пересылаемого из пункта в пункт . Тогда данные таблицы можно представить в следующем виде:

при условии, что

Положим и выразим через t остальные переменные:
из первого уравнения: ,
из второго уравнения: ,
из третьего уравнения:

Тогда

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

Тем самым, мы получили условие .

Не трудно заметить, что при t = 16.

Ответ:

Пример 2. Компания имеет два товарных склада и трех оптовых покупателей. Известно, что общий объем запасов на складах составляет 300 тыс. единиц продукции и совпадает с общим объемом заказов покупателей.

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

Тогда соответствующая транспортная задача может быть сформулирована следующим образом.

Минимизировать общую стоимость перевозок:

при условии, что

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

Положим и выразим через u и v остальные переменные. Имеем

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

которую можно решить графическим методом.

Выписанные неравенства определяют на плоскости (u, v) пятиугольник с вершинами (30, 0), (70, 0), (70, 50), (0, 120), (0, 30).

Ответ:

В начало

Хостинг от uCoz

Разделы орфографии (4 часа)

1. Орфографическая сфера письма:

1) буквенное обозначения звукового состава слова;

2) употребление прописных и строчных букв;

3) слитные, раздельные и полуслитные написания;

4) перенос слов;

5) графическое сокращение слов на письме

2. Общая характеристика каждого из разделов орфографии

Собственно орфографическая сфера письма достаточно ши­рока. Сюда относятся:

1) буквенное обозначение звукового состава слов в той его части,
которая не определена алфавитом и графикой: [горът] - город;

2) употребление прописных и строчных букв: орел и Орел;

3) слитные, раздельные и полуслитные написания: не высокий и
невысокий, по новому и по-новому;

4) перенос слов (более точно: перенос написания какой-либо
части слова) из одной строки в другую: ре-бята или ребя-та, но не реб-ята;

5) графические сокращения слов на письме: товарищ — т. или тов., но не «то», не «това».

Это части орфографии, и каждая из них состоит из значитель­ного набора конкретных правил. Части орфографии различаются, однако, не только своими конкретными правилами и даже не только их общей направленностью (обозначение звукового состава слов, употребление больших и малых букв и т. п.), но и своими общими принципами, лежащими в основе конкретных правил. В этом отношении части русской орфографии различаются следую­щим образом:

1. Первая часть орфографии (буквенное обозначение звукового
состава слов) свои конкретные правила строит на основе так назы­ваемого морфологического принципа. Основным требованием мор­фологического принципа орфографии является единообразное на­
писание конкретных морфем — каждого данного корня, суффикса,
окончания и т. п., если при изменении фонетического положения
входящих в их состав звуков они произносятся по-разному. Корень
слова город, например, пишется всегда одинаково - город, хотя
в составе разных слов и словоформ произносится по-разному:
[горът], [гърад]а, [горъд]а, при[гърът] и т. п.

2. Употребление прописных и строчных букв (2-я часть орфографии) связывается с характером слов (с прописной буквы пишутся, например, имена собственные: город Москва), а также с их
положением в речи (с прописной буквы пишется начало каждого
самостоятельного предложения). Основной принцип этой части
орфографии может быть определен поэтому как лексико-синтаксический.

3. Основным правилом слитных и раздельных написаний яв­ляется следующее простое положение: слова пишутся раздельно, части слов - слитно; для переходных или неясных случаев введе­ны полуслитные написания - написания через черточку (дефис), например: в первый раз, но во-первых. В основе этих правил лежит, таким образом, понятие слова: каждое слово само по себе пишется слитно и отделяется от других слов. Принцип, следовательно, лек­сический, точнее - лексико-морфологический.

4. При переносе написания какой-либо конечной части слова
в другую строку учитывается прежде всего слоговое строение слова,
а затем и его морфемная (морфологическая) структура: ре-бята или
ребя-та, но не «реб-ята»; noд-бить, а не «по-дбить» и т. п. Это, следовательно, слоговой принцип, осложненный принципом морфемным; его можно назвать и слого-морфемным (или морфемо-слоговым).

5. При графическом сокращении слов на письме учитывается
характер звуков и, соответственно, букв: нельзя, например, со­кращать написание слова на неначальных гласных: город - г. или
гор., но не «го» или «горо». Здесь, таким образом, буквенно-звуковой принцип.

Основной частью орфографии по праву считается ее первая часть - буквенное обозначение звукового состава слов. Это самая большая часть орфографии, в ней сосредоточена преобладающая масса орфографических правил. Кроме того, что особенно важно, эта часть орфографии более других ее частей соответствует основ­ному, буквенно-звуковому типу современного русского письма. Она в этом отношении непосредственно продолжает алфавит и гра­фику, составляя вместе с ними ведущие факторы, определяющие современное русское письмо. Другие части орфографии, особенно перенос слов и раздельные или слитные написания, не имеют столь тесной связи с типом письма и с его основой - алфавитом и гра­фикой.

Главенствующее положение первой части орфографии косвенно проявляется и в том, что ее основной принцип (морфологический) обычно считается и основным принципом всей орфографии в це­лом, - морфологический принцип орфографии.

При всем различии части орфографии имеют и объединяющую их основу: все они так или иначе ориентируются на слово - слитное и раздельное написание слов, сокращения слов, перенос слов; даже употреблением больших и малых букв выделяются определенные слова сами по себе или по их месту в тексте.