Решение задач с помощью линейного программирования

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

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

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

Целью данной курсовой работы является изучение методов решения задач математического моделирования на примере задач планирования производства и транспортной задачи.

Задачи работы:

изучить литературу по данной теме

для заданного варианта получить решение  задачи линейного программирования:

- графическим методом;

- симплекс - методом для прямой  задачи;

- сформулировать двойственную задачу и найти её решение.

- сформулировать и решить транспортную задачу.

1 Теоретические вопросы  к решению задач линейного  программирования 

1.1 Определение и характеристика  линейного программирования

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

Линейное программирование - наиболее разработанный и широко применяемый раздел математического  программирования. Это объясняется  следующим:

• математические модели очень большого числа экономических задач линейны относительно искомых переменных;
• эти типы задач в настоящее время наиболее изучены;
• для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;
• многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;
• некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования [1].

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

Сущность линейного  программирования состоит в нахождении точек наибольшего или наименьшего  значения некоторой функции при  определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи [3].

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

В общей постановке задача линейного программирования выглядит следующим образом [2]:

Имеются какие-то переменные х = (х₁, х₂, … х_n) и функция этих переменных f(x) = f (х₁, х₂, … х_n), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что а) функция f(x) является линейной функцией переменных х₁, х₂, … х_nб) область G определяется системой линейных равенств или неравенств.

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

• максимум или минимум целевой функции (критерий оптимальности);
• систему ограничений в форме линейных уравнений и неравенств;
• требование неотрицательности переменных [5].

Возникновение и развитие Линейного программирования связано с экономикой. Предположение  о линейности экономических зависимостей несколько ограничивает возможности  Линейного программирования, однако простота и наглядность линейных моделей, с достаточной степенью точности описывающих экономические процессы, позволяет применять эти модели в различных видах экономической деятельности [2].

1.2 Характеристика геометрического  метода решения задач

Рисунок 1

Рассмотрим задачу линейного  программирования в стандартной  форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2 [4].

Пусть геометрическим изображением системы ограничений  является многоугольник ABCDE (рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c₁x₁+c₂x₂ принимает максимальное (или минимальное) значение.

Рассмотрим  так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е.

F = a, или               (2)

c₁x₁+c₂x₂ = а        (3)

Линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

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

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

Уравнение линии  функции (1) есть уравнение прямой линии. При различных уровнях а.

Линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между  коэффициентами c₁ и c₂ и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные «параллели», расположенные обычно под углом к осям координат.

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

Пусть имеются  три линии уровня:

F=c₁x₁ + c₂x₂ = а₁ ( I)            (4)

F=c₁x₁ + c₂x₂ = а₂ (II)                          (5)

F=c₁x₁ + c₂x₂ = а₃  (III)             (6)

Причём линия II заключена между линиями I и III. Тогда а₁ < а₂ < а_{3 и} а₁ > а₂ > а_3.

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

Рисунок 2

Для определения  направления возрастания рекомендуется  изобразить две линии уровня и  определить, на какой них уровень  больше. Например, одну из линий взять  проходящей через начало координат (если линия функция имеет вид F=c₁x₁ + c₂x₂, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рисунке 1 – это точка С или А) [3].

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

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

Допустим, предприятие  предполагает выпускать два вида продукции  и , для производства которых используется сырьё трех видов.

Производство  обеспечено сырьем каждого вида в  количествах: , , кг. На изготовление единицы изделия требуется затратить сырья каждого вида , , кг., соответственно, а для единицы изделия – , , кг. Прибыль от реализации единицы изделия составляет ден.ед., для единицы изделия – ден.ед [4].

Таблица 1.3.1

Составляем  математическую модель:

       (8)

Введем базисные переменные и преобразуем исходную задачу к виду:

   (10)

Решим систему  уравнений относительно базисных переменных x₃, x₄, x₅.

Таблица 1.3.2 – Итерация №0

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

 – вектор, составленный  из координат соответствующих  базисных переменных.

Текущий план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

Будем считать что Z₂ наименьший элемент, а строку с наименьшим отношением свободного члена к соответствующему элементу выбранного столбца - строку Х₂.

Ведущий столбец Х₂, так как ( ) – наименьшее отрицательное число.

За ведущую выберем  строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим.

Разрешающий элемент  .

Разделим элементы строки 2 на разрешающий элемент ( ).

От элементов строки 1 отнимаем соответствующие элементы строки 2, умноженные на .

От элементов строки 3 отнимаем соответствующие элементы строки 2, умноженные на .

От элементов строки Z отнимаем соответствующие элементы строки 3, умноженные на .

Заменяем базисную переменную Х₅ на Х₁.

Количество итераций будет  продолжаться до тех пор, пока в строке Z остаются отрицательные элементы [7].

Рассмотрим порядок работы с симплекс таблицей.

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

Алгоритм перехода к следующей  таблице такой:

• просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов Y0) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;
• просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке- ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
• среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка, в которой он находится ключевой;
• в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных;
• разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы;
• строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место;
• в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1;
• столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же;
• строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же;
• в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы [6].

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

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

1.4 Характеристика метода решения задач с помощью теории двойственности

Имеется т видов сырья в количестве b₁, b₂,..., b_т, которые используются для изготовления п видов продукции. Известно: а_ij — расход i-го вида сырья на единицу j-ой продукции; с_j. — прибыль при реализации единицы j-го вида продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль.

Математическая  модель данной задачи имеет вид:

F(X) = с₁ х₁ + с₂ х₂ + ... + с_п х_п→max,         (11)         

     (12)

где х _j, j = 1,2, ..., п — объем производства j-го вида продукции.

Предположим, что  второй производитель хочет перекупить сырье. Составим двойственную задачу, решение которой позволит определить условия продажи сырья. Введем вектор оценок (цен) видов сырья Y=(у₁, у₂,… …,у_т). Затраты на приобретение i -го вида сырья в количестве b_i равны b_iу_i . Второму производителю выгодно минимизировать суммарные затраты на приобретение всех видов сырья, поэтому целевая функция имеет вид

Z(Y) =b₁у₁ +b₂у₂ +…+b_ту_т→ min      (13)

Первому производителю невыгодно продавать сырье, если суммарная стоимость всех видов сырья, расходуемых на каждое изделие j-й продукции, т.е. а_1j у₁ + а_2j у₂ +…+ а_mj у_т, меньше прибыли сj  получаемой при реализации этого изделия. Система ограничений задачи имеет вид

      (14)

Оценки видов  сырья должны удовлетворять условиям неотрицательности   у_i ≥0,  i = 1, 2, …, т.

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

1.5 Основные этапы, особенности и методы решения транспортной задачи

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение [8].

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

Таблица 1.5.1

Составим математическую модель данной задачи:

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

     (15)

+

Ограничения:

где х_ij – количество груза, отправляемого с базы A_i в пункт B_j.

Одним из способов решения  транспортных задач является метод  северо-западного угла. На каждом этапе  метода максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение происходит таким образом, что полностью выносится груз из или полностью удовлетворяется потребность [9].

Так как транспортная задача является задачей линейного  программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из А_i в B_j груза X_ij ≥ 0, а в маленькие клетки – соответствующие тарифы C_ij [9].

Таблица 1.5.2

Затем решение  задачи разбивается на два этапа:

• Определение опорного плана (Это решение можно найти, используя метод «северо-западного угла» или метод «минимального элемента».)
• Нахождение оптимального решения путем последовательных операций.

1) Метод северо-западного угла

Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части  таблицы, причем максимально возможным  числом: либо полностью выносится  груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Х_ij горизонтальным и вертикальным уравнениям.

2) Метод наименьшего элемента

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

В остальном  действуют аналогично предыдущему способу.

3) Метод потенциалов

Соотношения определяют систему из m+n-1 линейных уравнений  с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному присваивают произвольное значение (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.

Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных  ячеек выполняются условия α_i+β_j ≤ C_ij, то Х0 является оптимальным планом транспортной задачи.

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

Цикл перерасчёта  таблицы – это последовательность ячеек, удовлетворяющая условиям:

– Одна ячейка пустая, все остальные занятые.

– Любые две соседние ячейки находятся в одной строке или в одном столбце.

– Никакие три соседние ячейки не могут быть в одной строке или в одном столбце.

– Пустой ячейке присваивают знак "+", остальным – знаки "–" и "+".

Для перераспределения  плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s), в которой αr+βs > Crs, и строят соответствующий цикл; затем в минусовых клетках находят число X = min(X_ij). Далее составляют новую таблицу по следующему правилу:

– В плюсовых клетках добавляем Х.

– Из минусовых клеток вычитаем Х.

– Все остальные клетки вне цикла остаются без изменения.

Получим новую  таблицу, дающую новое решение Х, такое, что 

F (X₁) ≤ F (X₀); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует [10].

2 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

2.1 Решение задачи планирования производства геометрическим способом

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

Запишем условия задачи. Предприятие предполагает выпускать два вида продукции А₁ и А₂, для производства которых используется сырьё трех видов. Производство обеспечено сырьем каждого вида в количествах: 600, 357, 600 кг. На изготовление единицы изделия А₁ требуется затратить сырья каждого вида 3, 3, 1 кг, соответственно, а для единицы изделия А₂ - 4, 1, 5 кг. Прибыль от реализации единицы изделия А₁ составляет 42 ден.ед., для единицы изделия А₂ - 26 ден.ед.

Требуется составить план производства изделий А₁ и А₂ обеспечивающий максимальную прибыль предприятия от реализации готовой продукции.

Занесём необходимые  нам данные во вспомогательную таблицу:

Таблица 2.1.1