Симплекс-метод решения задач линейного программирования

Двумерные задачи линейного программирования решаются графически. Для случая n=3 нужно ужерассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

В общем виде, когда в задаче участвуют n -неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n -мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более 3 весьма затруднительно и даже невозможно.

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

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

Поэтому надо найти способ перехода от данной вершины к «лучшей», а от нее – к еще «лучшей». Кроме того, сюда же надо добавить какие-то условия существования оптимального решения для данной задачи.

В этом и заключается суть метода последовательного улучшения плана для решения задачи ЛП, который называется симплекс-методом и наиболее широко применяется в настоящее время.

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

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

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

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

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

 

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

Имеется много данных об успешном использовании моделей ЛП в различных задачах управления и проектирования в строительстве. Рассмотрим некоторые схемы таких задач.

6.4.1. Задача об оптимальном плане выпуска продукции

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

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

 

 

Постановка задачи. Предприятие выпускает n видов продукции, на которую употребляет m видов сырья. Расход i-го вида сырья на единицу j-го вида продукции составляет aij единиц. Известно, что на каждой единице продукции j-го вида предприятие получает прибыль cj Требуется определить, сколько единиц каждого вида продукции должно изготовить предприятие (оптимальный план выпуска продукции), чтобы обеспечить максимальную прибыль. При этом следует учесть, что запасов сырья каждого ( i-го) вида имеется bi.

В качестве проектных (управляемых) параметров в данной задаче можно принять объемы выпуска соответствующего вида продукции: . Иначе говоря, x_i, i=1, 2, …, n - количество единиц каждого i-го вида продукции, которое должно изготовить предприятие.

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

при выполнении ограничений

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

n Пример 6.6. Построить математическую модель задачи планирования производства.

Цех производит два вида продукции (продукт1 и продукт2) стоимостью соответственно 5 у.е. и 5, 5 у.е. (усл. единиц). На производстве действуют ограничения по ресурсам: сырье; трудовые затраты; транспортные расходы (аренда машины для вывоза продукции). Расход каждого ресурса на изготовление того и другого продукта, количество ресурса в распоряжении цеха приведены в таблице.

Используемые ресурсы	Расход ресурсов на изготовление	Количество ресурса в распоряжении цеха
продукта1	продукта2
Сырье Трудовые затраты Транспортные расходы			не менее 2
Стоимость продукта	5 у.е.	5, 5 у.е.

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

В качестве проектных параметров x₁, x₂ выберем оптимальные объемы производства обоих продуктов.

Тогда целевая функция запишется в виде

Z_max = 5 x₁+ 5, 5 x₂. (6.20)

Ограничения записываем из условия ресурсов, которыми располагает цех.

(6.21)

Решение задачи с использованием электронных таблиц Excel приведено в подразделе 6.5.

6.4.2. Задача об оптимальном раскрое материалов (о минимизации отходов)

В строительном деле достаточно часто приходится решать проблему раскроя полуфабрикатов или минимизации отходов производства.

Постановка задачи. Из имеющихся заготовок в виде досок длиной D каждая требуется получить bi частей длиной Li (i=1, 2, …, m). Имеется несколько вариантов раскроя Vj (j=1, 2, …, n) каждой доски L (план раскроя). При каждом j-м варианте раскроя получается aij частей длиной lj. (При этом . Это условие, наложенное на коэффициенты, содержится в определении «вариант раскроя» и не является условием оптимизации). Требуется так распилить доски, чтобы было как можно меньше отходов, или требуемое количество частей должно быть получено из минимального количества заготовок.

В качестве независимых параметров выбираем x_j – количество досок (заготовок), распиленное по j-му варианту.

Оптимизацию будем проводить исходя из минималь-ного количества распиленных заготовок.

Математической модели задачи имеет вид: минимизировать целевую функцию

при ограничениях:

Задачи об оптимальном раскрое довольно разнообразны и в качестве примера рассмотрим еще один вариант такой задачи.

n Пример 6.7. При серийном производстве некоторого изделия из полос проката длиной 5000мм необходимо вырезать 3 вида заготовок. Номер, длина и количество заготовок:

№1 длина 1655мм, 1шт.

№2 длина 1050мм, 5шт.

№3 длина 210мм, 1шт.

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

Решение

Оптимизацию будем производить, исходя из минимальных отходов полос проката при их раскрое.

1. Составим таблицу - карту раскроя:

Cпособ раскроя	Количество заготовок длиной (мм)	Полезно используемая длина (мм)	Длина отходов (мм)	Количество полос
						x1 x2 x3 x4

Таким образом, получилось четыре способа раскроя полос.

2. В качестве проектных параметров возьмем: x_i – количество прокатных полос, раскроенных i-способом.

3. Определим длину отходов при каждом способе раскроя.

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

Z_min = 35x₁ + 430x₂ + 195x₃ + 590x_4.

5. Запишем ограничения. Для 12 изделий необходимо заготовок:

№1 – 12 шт. №2 – 12 × 5 шт.; №3 – 12 шт.

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

 

 

6.4.3. Задача о планировании смен на предприятии

Полученная ММ задачи об оптимальном раскрое материалов (6.23) – (6.25) может быть использована также при решении задач о планировании смен на предприятии.

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

V_j (j=1, 2, …, n) – возможные в течение дня смены;

L_i (i=1, 2, …, m) – определенное время дня;

а_ij = 1, если V_j предусматривает работу во время L_i, в противном случае а_ij = 0;

b_i – число работников, требующихся в момент времени L_i;

x_j – количество работников смены V_j.

⇐ Предыдущая9101112131415161718Следующая ⇒

Поделиться:

Популярное:

1. I I. Цели, задачи, результаты выполнения индивидуального проекта
2. I. Автоматизации функциональных задач в государственном и региональном управлении.
3. II. Основные задачи управления персоналом.
4. II. Решить следующие ниже финансовые задачи на листе “Задачи”.
5. II. Цели, задачи и предмет деятельности
6. III. Задачи, решаемые организацией с помощью ИСУ и ИТУ.
7. III. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ РАЙОННОЙ ОРГАНИЗАЦИИ ПРОФСОЮЗА
8. III. Экономико-управленческие задачи производственной практики
9. IV. Решить следующую задачу.
10. VII. Перечень вопросов для проведения проверки знаний кандидатов на получение свидетельства линейного пилота с внесением квалификационной отметки о виде воздушного судна - вертолет
11. А. П. Петрова. «Сценическая речь» - Пути воплощения сверхзадачи
12. АДМИРАЛ РЕШАЕТ ТРУДНУЮ ЗАДАЧУ