Введение
Актуальность темы. На данный момент эта тема оченьактуальна, т.к. успешная реализация достижений научно – технического прогрессав нашей стране тесным образом связана с использованием математических методов исредств вычислительной техники при решении задач из различных областейчеловеческой деятельности. Исключительно важное значение приобретаетиспользование указанных методов и средств при решении экономических задач. Всвязи с этим для студентов экономических специальностей вузов необходимо какзнание возможностей применения математических методов, так и понимание техпроблем, которые возникают при их использовании.
Цель курсовой работы — изучить методы решения задачлинейного программирования и научиться применять на практике решение задачиграфическим, симплекс-методом (аналитическим и табличным) для прямой идвойственной задачи линейного программирования, а также научиться решатьтранспортную задачу.
Задачи работы:
изучить литературу по данной теме
для заданного варианта получить решение задачи линейногопрограммирования:
— графическим методом;
— симплекс — методом для прямой задачи;
— симплекс — методом для двойственной задачи.
— сформулировать двойственную задачу и найти её решение.
— сформулировать и решить транспортную задачу.
Результаты работы рекомендуется использовать дляуспешного решения задач линейного программирования и дальнейшего изученияматематического и линейного программирования.
Задачи математического и линейного программирования
Исследование различных процессов, в том числе иэкономических, обычно начинается с их моделирования, т.е. отражения реальногопроцесса через математические соотношения.
При этом составляются уравнения или неравенства, которыесвязывают различные показатели (переменные) исследуемого процесса, образуясистему ограничений. В этих соотношениях выделяются такие переменные, меняякоторые можно получить оптимальное значение основного показателя данной системы(прибыль, доход, затраты и т.п.). Соответствующие методы, позволяющие решатьуказанные задачи, объединяются под общим названием «математическое программирование»,или «математические методы исследования операций».
Математическое программирование включает в себя такиеразделы математики, как линейное, нелинейное и динамическое программирование.
Сюда же обычно относят стохастическое программирование,теорию игр, теорию массового обслуживания, теорию управления запасами инекоторые другие.
Математическое программирование — это раздел высшейматематики, посвященный решению задач, связанных с нахождением экстремумовфункций нескольких переменных при наличии ограничений на переменные.
Методами математического программирования решаются задачио распределении ресурсов, планировании выпуска продукции, ценообразовании,транспортные задачи и т.п.
Построение математической модели экономической задачивключает следующие этапы:
1) выбор переменных задачи;
2) составление системы ограничений;
3) выбор целевой функции.
Переменными задачи называются величины x1, x2, ..., хп, которые полностью характеризуют экономический процесс. Их обычно записывают ввиде вектора Х= (х1, х2, ..., хп).
Система ограничений включает в себя систему уравнений инеравенств, которым удовлетворяют переменные задачи и которые следуют изограниченности ресурсов или других экономических или физических условий,например положительности переменных и т.п.
Целевой функцией называют функцию переменных задачи,которая характеризует качество выполнения задачи и экстремум которой требуетсянайти.
Если целевая функция и система ограничений линейны, тозадача математического программирования называется задачей линейногопрограммирования.
Допустимым решением (планом) задачи линейногопрограммирования (ЗЛП) называется любой n-мерный вектор Х= (х1, х2, ..., хn),удовлетворяющий системе ограничений и условиям неотрицательности.
Множество допустимых решений (планов) задачи образуетобласть допустимых решений (ОДР).
Оптимальным решением (планом) ЗЛП называется такоедопустимое решение (план) задачи, при котором целевая функция достигаетэкстремума.
Общий вид задачи линейного программирования:
/>
/>
/>
/>
/>,/>
Ограничения:
1. Правые части всех ограничений должны бытьнеотрицательными />. Если какой-нибудь изкоэффициентов />
2. Все ограничения должны быть представлены в видеравенств, поэтому при переходе от неравенства к равенству используют аппаратдополнительных переменных.
Если исходные ограничения определяют расход некоторогоресурса (знак "/>"), то переменные
/>
следует интерпретировать как остаток, илинеиспользованную часть ресурса. В этом случае />– остаточная переменная и вводитсяв уравнение со знаком "+". Если исходные ограничения определяютизбыток некоторого ресурса (знак "/>"), то вводится избыточнаяпеременная
/>
знаком "-".
Переменные:
Все переменные должны быть неотрицательными, т.е.
/>.
Если переменная не имеет ограничения в знаке, то её нужнопредставить как разность двух неотрицательных переменных:
/>,
где />. Такую подстановку следуетиспользовать во всех ограничениях, содержащих эту переменную, а также ввыражении для целевой функции.
Если такая переменная попадает в оптимальное решение, то />.
Целевая функция:
Целевая функция задачи линейного программирования естьуравнение плоскости (или гиперплоскости для числа переменных больше трех). Максимальноеили минимальное значение целевая функция задачи линейного программированиядостигает либо в вершине выпуклого многогранника, либо на одной из его граней.Таким образом, решение (решения) задачи линейного программирования лежит ввершинах выпуклого многогранника и для его нахождения надо вычислить значенияцелевой функции в вершинах выпуклого многогранника, определяемогоусловиями-ограничениями задачи.
Приступаем к решению задачи.
Требуется составить план производства изделий А₁ и А₂ обеспечивающиймаксимальную прибыль предприятия от реализации готовой продукции. Необходимо:
Решить задачу геометрически;
Решить задачу симплекс-методом(аналитическим и табличным)
Сформулировать двойственную задачу и найти её решение.
Задача №1
Предприятие предполагает выпускать два вида продукции А₁ и А₂, для производствакоторых используется сырьё трех видов. Производство обеспечено сырьем каждоговида в количествах: b₁,b₂, b₃ кг. На изготовлениеединицы изделия А₁требуется затратить сырья каждого вида а₁₁,а₂₁, а₃₁ кг,соответственно, а для единицы изделия А₂- а₁₂, а₂₂, а₃₂ кг. Прибыль отреализации единицы изделия А₁составляет с₁ден.ед., для единицы изделия А₂- с₂ ден.ед.
Вспомогательная таблицаВид сырья Продукция Ограничения по сырью А₁ А₂ 1-й а₁₁ а₁₂ b₁ 2-й а₂₁ а₂₂ b₂ 3-й а₃₁ а₃₂ b₃ прибыль с₁ с₂
Решение задачи геометрическим методом
Трудность построения математической модели заключается видентификации переменных и последующем представлении цели и ограничений в видематематических функций этих переменных. Если модель содержит только двепеременные, то задачу линейного программирования можно решить графически. Вслучае трёх переменных графическое решение становится менее наглядным, а прибольшем значении переменных – даже невозможным. Однако графическое решениепозволяет сделать выводы, которые служат основой для разработки общего методарешения задачи линейного программирования.
Первый шаг при использовании графического методазаключается в геометрическом представлении допустимых решений, т.е. построенииобласти допустимых решений (ОДР.), в которой одновременно удовлетворяются всеограничения модели. При получении графического решения переменная X1 откладываетсяпо горизонтальной оси, а X2 – по вертикальной. При формировании ОДР необходимопредотвратить получение недопустимых решений, которые связаны с необходимостьювыполнения условия неотрицательности переменных. Перед построением необходимоопределить квадранты, в которых будет располагаться ОДР. Квадранты определяютсязнаками переменных X1 и X2. Условия неотрицательности переменных X1 и X2ограничивают область их допустимых значений первым квадрантом. Если переменная X1не ограниченна в знаке, то область ограничивается первым и вторым квадрантом,если X2, то – первым и четвёртым квадрантом.
Области, в которых выполняются соответствующиеограничения в виде неравенств, указываются стрелками, направленными в сторонудопустимых значений переменных.
В результате построений получается многоугольник, которыйопределяет пространство решений. Если одно из ограничений имеет знак"=", то ОДР вырождается в отрезок.
В каждой точке, принадлежащей области или границаммногоугольника решений, все ограничения выполняются, поэтому все решения,соответствующие этим точкам, являются допустимыми. Пространство решенийсодержит бесконечное число таких точек, несмотря на это, можно найтиоптимальное решение. Для этого необходимо построить в плоскости переменных X1,X2 градиент целевой функции. Определение оптимальной точки зависит от тойзадачи, которую необходимо решить.
Если в целевой функции определена задача максимизации, тооптимальная точка будет располагаться в направлении увеличения градиента, еслизадача минимизации – то в направлении уменьшения градиента целевой функции. Дляопределения оптимальной точки будем перемещать целевую функцию в направленииувеличения (уменьшения) градиента до тех пор, пока она не сместиться в областьнедопустимых решений.
После нахождения оптимальной точки пространства решенийопределяют её координаты X1 *, X2 *и значение целевой функции F * в ней.Правильность выбора оптимальной точки можно проверить расчётом целевой функциив вершинах многогранника решений. В ЗЛП область допустимых решений всегдаявляется выпуклым множеством, т.е. таким множеством, что наряду с любыми двумяточками, принадлежащими этому множеству, этому же множеству принадлежит иотрезок, соединяющий эти две точки. Любая функция наискорейшим образомувеличивается в направлении своего градиента.
Далее приступаем к решению задачи:
Занесём необходимые нам данные во вспомогательнуютаблицу:Вид сырья Продукция Ограничения по сырью А₁ А₂ 1-й 5 2 750 2-й 4 5 807 3-й 1 7 840 прибыль 30 49
Решение:
Предположим, что будет изготовлено Х₁ единиц изделий вида А₁ и Х₂ единиц — вида А₂. Посколькупроизводство продукции ограничено имеющимися в распоряжении предприятия сырьемкаждого вида и количество изготовляемых изделий не может быть отрицательным,должны выполняться неравенства:
/>
/>
Общая прибыль от реализации Х₁ изделий А₁и Х₂ изделий видаА₂ составит
F = 30Х₁+49Х₂/>.
Таким образом, мы приходим к следующей математическойзадаче: среди всех неотрицательных решений данной системы линейных неравенствтребуется найти такое, при котором функция F принимает максимальное значение.
Найдем решение сформулированной задачи, используя еегеометрическую интерпретацию. Сначала определим многоугольник решений. Дляэтого в неравенствах системы ограничений и условиях неотрицательностипеременных знаки неравенств заменим на знаки точных равенств и найдемсоответствующие прямые:
/>
/>
Эти прямые изображены на рис №1. Каждая из построенныхпрямых делит плоскость на две полуплоскости. Координаты точек однойполуплоскости удовлетворяют исходному неравенству, а другой — нет. Чтобыопределить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащуюодной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данномунеравенству. Если координаты взятой точки удовлетворяют данному неравенству, тоискомой является та полуплоскость, которой принадлежит эта точка, в противномслучае — другая полуплоскость.
Найдем, например, полуплоскость, определяемую неравенствами.
/>
Построим область допустимых решений:
для прямой/>
/>
С(0;0) => 5·0+2·0=0, а 0≤750, значит прямаястремится к нулю (рис.1)
для прямой />
/>
В(0;0) => 4·0+5·0=0, а 0≤807, значит прямаястремится к нулю (рис.1)
для прямой />
/>
А(0;0) => 1·0+7·0=0, а 0≤840, значит прямаястремится к нулю (рис.1). Это и показано стрелками.
Пересечение полученных полуплоскостей и определяетмногоугольник решений данной задачи.
Как видно из рис №1, многоугольником решений являетсяпятиугольник OABCD. Координаты любой точки, принадлежащей этому пятиугольнику,удовлетворяют данной системе неравенств и условию неотрицательности переменных.Поэтому сформулированная задача будет решена, если мы сможем найти точку,принадлежащую пятиугольнику OABCD, в которой функция F принимает максимальноезначение.
Чтобы найти указанную точку, построим вектор ñ=(30; 49) и прямую 30Х1 + 49Х2 = h, где h — некоторая постоянная такая, чтопрямая 30Х1 + 49Х2 = h имеет общие точки с многоугольником решений. Положим,например, h = 510 и построим прямую 30Х1 + 49Х2 = 510 (рис. №1).
Если теперь взять какую-нибудь точку, принадлежащуюпостроенной прямой и многоугольнику решений, то ее координаты определяют такойплан производства изделий А1 и А2, при котором прибыль от их реализации равна 510руб. Далее, полагая h равным некоторому числу, большему чем 510, мы будемполучать различные параллельные прямые. Если они имеют общие точки смногоугольником решений, то эти точки определяют планы производства изделий А1и А2, при которых прибыль от их реализации превзойдет 510 руб.
Перемещая построенную прямую 30Х1 + 49Х2 = 510 внаправлении вектора ñ, видим, что последней общей точкой ее смногоугольником решений задачи служит точка В. Координаты этой точки иопределяют план выпуска изделий А1 и А2, при котором прибыль от их реализацииявляется максимальной.
Найдем координаты точки В как точки пересечения прямых /> и />. Следовательно, еекоординаты удовлетворяют уравнениям этих прямых
/>
Решим эту систему уравнений:
Х1 = 840 – 7Х2, подставим полученное в первое уравнение /> => 3360 – 28Х2 + 5Х2 =807 => 23Х2 = 2553 =>
Х2 = 111, из этого решения следует, что Х1 = 840 – 7·111= 63 => Х1 = 63
Следовательно, если предприятие изготовит 63 изделий видаА1 и 111 изделий вида А2, то оно получит максимальную прибыль, равную Fmax =30·63 + 49·111= 7329 руб.
Решение задачи аналитическим симплекс-методом
Симплексный метод — это метод целенаправленного перебораопорных решений задачи линейного программирования. Он позволяет за конечноечисло шагов расчета либо найти оптимальное решение, либо установить, чтооптимального решения не существует.
Идея симплексного метода состоит в следующем. Используясистему ограничений, приведенную к общему виду, т. е. к системе т линейныхуравнений с п переменными (т
Симплексный метод гарантирует, что при этом новом решениилинейная форма если и не достигнет оптимума, то приблизится к нему (в случаеперехода к вырожденному базисному решению значение линейной формы неизменится). С новым допустимым базисным решением поступают так же, пока ненаходят решение, которое является оптимальным.
Если первое найденное базисное решение окажетсянедопустимым, то с помощью симплексного метода осуществляют переход к другимбазисным решениям, которые позволяют приблизиться к области допустимых решений,пока на каком-то шаге не получится допустимое выше.
Дадим математическую формулировку задачи. Пусть Х1 и Х2 —количество изделий А1 и А2, запланированных к производству. Так как количествосырья по каждому виду ограничено, то должны выполняться следующие неравенства:
/>
/>
Эта система неравенств и является системой ограниченийданной задачи. Целевая функция (линейная форма), выражающая прибыльпредприятия, имеет вид
F = 30Х₁+49Х₂/>.
Итак, задача сводится к нахождению максимума функции F =30Х₁ +49Х₂ при ограничениях:
/>
/>
Для сведения системы ограничений-неравенств к системеуравнений прибавим к левой части каждого неравенства добавочные неотрицательныепеременные Х3, Х4, Х5. В условиях данной задачи они имеют конкретноеэкономическое содержание, а именно выражают объем остатков сырья каждого видапосле выполнения плана по выпуску продукции. После введения добавочныхпеременных получим систему уравнений:
/>
5Х1+2Х2+Х3 = 750
4Х1+5 Х2+ Х4 = 807
Х1+7Х2+Х5 = 840
Хi≥0, i=1….5
Нужно найти такое допустимое базисное решение этойсистемы ограничений, которое бы максимизировало линейную форму F = 30Х₁ +49Х₂.
Так как система ограничений есть система трех независимыхуравнений с двумя переменными, то число базисных переменных должно равнятьсятрём, а число свободных — двум.
Для решения задачи симплексным методом прежде всего нужнонайти любое базисное решение. В данном случае это легко сделать. Для этогодостаточно взять в качестве базисных добавочные переменные Х3, Х4, Х5. Так каккоэффициенты при этих переменных образуют единичную матрицу, то отпадаетнеобходимость вычислять определитель. Считая свободными переменные Х1 и Х2равными нулю, получим базисное решение (0; 0; 750; 807; 840), которое к тому жеоказалось допустимым. Переходим к поискам оптимального решения.
I ш а г. Базисные переменные: Х3, Х4, Х5; свободные переменные:Х1 и Х2. В системе (1.1) базисные переменные выразим через свободные. Для тогочтобы судить, оставить ли свободные переменные в числе свободных или ихвыгоднее с точки зрения приближения к оптимальному решению перевести вбазисные, следует выразить через них и линейную форму (в данном случае она ужевыражена через переменные Х1 и Х2). Тогда получим:
/>Х3 = 750 — 5 Х1 — 2 Х2
Х4 = 807 — 4 Х1 — 5Х2
[Х5 = 840 — Х1 — 7Х2]
F = 30Х₁+49Х₂
При Х1 = Х2 = 0 имеем Х3 = 750, Х4 = 807, Х5 = 840, чтодает базисное решение (0; 0; 750; 807; 840), которое мы приняли за исходное.При этом базисном решении значение линейной формы
/>
F = 30Х₁+49Х₂ = 0.
Когда мы предположили, что Х1 = Х2 = 0 (предприятиеничего не выпускает), была поставлена цель — найти первое, безразлично какое,базисное решение. Эта цель достигнута. Теперь от этого первоначального решениянужно перейти к другому, при котором значение линейной формы увеличится. Израссмотрения линейной формы видно, что ее значение возрастает при увеличениизначений переменных Х1 и Х2. Иными словами, эти переменные невыгодно считатьсвободными, т. е. равными нулю, их нужно перевести в число базисных. Это иозначает переход к новому базисному решению. При симплексном методе на каждомшаге решения предполагается перевод в число базисных только одной из свободныхпеременных. Переведем в число базисных переменную Х2 так как она входит ввыражение линейной формы F = 30Х₁+49Х₂ с большимкоэффициентом.
Как только одна из свободных переменных переходит в числобазисных, одна из базисных должна быть переведена на ее место в числосвободных. Какую же из четырех базисных переменных нужно вывести? Ответить наэтот вопрос помогут следующие рассуждения: значение Х2 необходимо сделать какможно большим, так как это соответствует конечной цели — максимизации F. Однакооказывается, что увеличение Х2 может продолжаться только до известных границ, аименно до тех пор, пока не нарушится требование неотрицательности переменных.
/>/>Х2 = min /> />;/> = min{375; 161,4; 120} =120,
далее Х2 переведём в базисные вместо Х5.
II ш а г. Базисные переменные: Х3, Х4, Х2; свободныепеременные: Х1, Х5. Выразим базисные переменные и линейную форму черезсвободные. В системе (1.2) берем то уравнение, из которого получено минимальноезначение отношения свободного члена к коэффициенту при Х2. В данном случае этотретье уравнение, которое выделено рамкой. Выразив из этого уравнения Х2,получим:
Х2 = 120 — /> Х1 — /> Х5
Подставив это выражение Х2 во все остальные уравнениясистемы (1.2) и в линейную форму F, получим:
/>Х2 =120 — /> Х1 — /> Х5
Х3 = 750 — 5 Х1 – 2(120 — /> Х1 — /> Х5) = 510 — /> Х1 + /> Х5
Х4 = 807 — 4 Х1 – 5(120 — /> Х1 — /> Х5) = 207 — /> Х1 + /> Х5
/>Х2= 120 — /> Х1 — /> Х5
(1.3) Х3 = 510 — /> Х1 + /> Х5
[Х4 = 207 — /> Х1 + /> Х5]
F = 30Х₁+49(120 — /> Х1 — /> Х5) = 5880 + 23 Х1 — 7 Х5
При Х1 = Х5 = 0 имеем F = 5880. Это уже лучше, чем на Iшаге, но не искомый максимум. Дальнейшее увеличение функции F возможно за счетвведения переменной Х1 в число базисных; так как эта переменная входит ввыражение F с положительным коэффициентом, поэтому ее увеличение приводит кувеличению линейной формы и ее невыгодно считать свободной, т. е. равной нулю.
/>/>Для ответа на вопрос, какуюпеременную вывести из базисных в свободные, примем:
Х1 = min /> />;/> = min{840; 108,2; 63} = 63,
далее Х1 переведём в базисные вместо Х4.
III шаг. Базисные переменные: Х1, Х2, Х3; свободныепеременные: Х4, Х5. Выразим основные переменные и линейную форму черезсвободные. Из последнего уравнения системы (1.3) имеем:
/> Х1 = 207 + /> Х5 – Х4 => Х1 = 63 + /> Х5 — /> Х4
Подставляя это выражение в остальные уравнения и влинейную форму, получим:
/>Х1 = 63+ /> Х5 — /> Х4
Х2 = 120 — /> (63 + /> Х5 — /> Х4) — /> Х5 = 111 — /> Х5 — /> Х4
Х3 = 510 — /> (63 + /> Х5 — /> Х4) + /> Х5 = 213 — /> Х5 + /> Х4
/>Х1 = 63+ /> Х5 — /> Х4
(1.4) Х2 = 111 — /> Х5 — /> Х4
Х3 = 213 — /> Х5 + /> Х4
F = 5880 + 23(63 + /> Х5 — /> Х4) — 7 Х5 = 7329 — 2 Х5 — 7 Х4
Так как в выражение линейной формы переменные Х4 и Х5входят с отрицательным коэффициентами, то никакое увеличение F за счет этихпеременных невозможно.
Следовательно, на III шаге критерий оптимальностидостигнут и задача решена. Оптимальным служит решение (63;111;213;207;0), прикотором Fmаx= 7329.
Таким образом, для получения наибольшей прибыли, равной7329 ден. ед., из данных запасов сырья предприятие должно изготовить 63 видаизделий А1 и 111изделий вида А2.
Ответ: Х1* = 63; Х2* = 111. Fmаx= 7329.
Решить задачу табличным симплексным методом
Рассмотренный симплексный метод решения ЗЛП в предыдущемпункте можно свести к записи однотипно заполняемых таблиц. Осуществить этовозможно, придерживаясь следующего алгоритма:
Привести задачу линейного программирования кканоническому виду.
Найти начальное опорное решение с базисом из единичныхвекторов и коэффициенты разложений векторов условий по базису опорного решения.Если опорное решение отсутствует, то задача не имеет решения в силунесовместности системы ограничений.
Вычислить оценки разложений векторов условий по базисуопорного решения и заполнить симплексную таблицу.
Если выполняется признак единственности оптимальногорешения (для любого вектора условий, не входящего в базис, оценка отлична отнуля), то решение задачи заканчивается.
Если выполняется условие существования множестваоптимальных решений (оценка хотя бы одного вектора условий, не входящего вбазис, равна нулю), то путем простого перебора находят все оптимальные решения.
Если выполняются условия отсутствия оптимального решениявследствие неограниченности целевой функции (не имеет решения, если длякакого-либо из векторов условий с оценкой, противоречащей признакуоптимальности, среди коэффициентов разложения по базису опорного решения нет положительного),то задача не имеет решения ввиду неограниченности целевой функции.
Если пункты 4-6 алгоритма не выполняются, находят новоеопорное решение с использованием условий нахождения оптимального решения.
Составим математическую модель задачи. Искомый выпускпродукции А1 обозначим через Х1, продукции А2 – Х2. Поскольку имеютсяограничения на выделенный предприятию фонд сырья каждого вида, переменные Х1,Х2 должны удовлетворять следующей системе неравенств:
/>5Х1+2Х2≤ 750
(1.1) 4Х1+5 Х2 ≤ 807
Х1+7Х2 ≤ 840
Х1≥0, Х2≥0
Общая стоимость произведенной предприятием продукции приусловии выпуска Х1изделий А1 и Х2 изделий А2 составляет F = 30Х₁ +49Х₂
По своему экономическому содержанию переменные Х1 и Х2 могутпринимать только лишь неотрицательные значения: Х1, Х2 ≥0.
Таким образом, приходим к следующей математическойзадаче: среди всех неотрицательных решений системы неравенств (1.1) требуетсянайти такое, при котором функция F = 30Х₁+49Х₂ принимаетмаксимальное значение.
Запишем эту задачу в форме основной задачи линейногопрограммирования. Для этого перейдем от ограничений-неравенств кограничениям-равенствам. Введем три дополнительные переменные, в результатечего ограничения запишутся в виде системы уравнений:
/>
5Х1+2Х2+Х3 = 750
(1.1) 4Х1+5 Х2+ Х4 = 807
Х1+7Х2+Х5 = 840
Хi≥0, i=1….5
Эти дополнительные переменные по экономическому смыслуозначают не используемое при данном плане производства количество сырья тогоили иного вида. Например, Х3 — это неиспользуемое количество сырья 1-ого вида ит.д.
Для решения задачи табличным симплексным методом преждевсего нужно найти любое базисное решение. В данном случае это легко сделать.Для этого достаточно взять в качестве базисных добавочные переменные Х3, Х4,Х5., а в качестве свободных переменные Х1 и Х2 равными нулю, получим базисноерешение (0; 0; 750; 807; 840), которое к тому же оказалось допустимым. F = 30Х₁ +49Х₂ => F — 30Х₁ — 49Х₂ = 0
Переходим к поискам оптимального решения.
Составим симплексную таблицу:
Как видно из таблицы (2.1), значения всех переменныхотвечают такому «плану», при котором ничего не производится, сырье неиспользуется и значение целевой функции равно нулю (т. е. стоимостьпроизведенной продукции отсутствует). Этот план, конечно, не являетсяоптимальным.
Это видно и из 4-й строки таблицы (2.1), так как в нейимеется два отрицательных числа: (- 30; — 49;0;0;0). Отрицательные числа нетолько свидетельствуют о возможности увеличения общей стоимости производимойпродукции, но и показывают, на сколько увеличится эта сумма при введении в планединицы того или другого вида продукции.
Даже с экономической точки зрения наиболее целесообразнымявляется включение в план производства изделий А2. Это же необходимо сделать ина основании формального признака симплексного метода, поскольку максимальноепо абсолютной величине отрицательное число -49, стоит в 4-й строке 2-го столбца=> этот столбец является разрешающим.Определяем вектор, подлежащийисключению из базиса и выбираем разрешающую строку. Для этого находим:
/>/>Х2 = min />; />;/> = 120.
Найдя число /> = 120, => 3-я строка (Х5)является разрешающей. Следовательно, в базис введем Х2 вместо Х5. Тем самым мы,с экономической точки зрения определили, какое количество изделий А2 предприятиеможет изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида.
Таблица (2.1)Базисные переменные Свободные переменные 1 2 3 4 5 Х1 Х2 Х3 Х4 Х5 1 Х3 750 5 2 1 2 Х4 807
/>4 5 1 3 Х5 840 1 7 1 4 F -30 -49
На пересечении разрешающего столбца и строки находитсяразрешающий элемент — это число 7. Производим пересчет всех коэффициентовтаблицы, таким образом, чтоб на месте разрешающего элемента получить 1, а вразрешающем столбце все элементы = 0.
Для этого: 1) Третью строку разделим на 7, в результатеполучим на месте разрешающего элемента 1.
2) Третью строку умножим на 2 и из первой строки вычтемто, что получилось при умножении. Результат записываем в первую строку.
3) Третью строку домножим на 5 и из второй строки вычтемто, что получилось при умножении. Результат записываем во вторую строку.
4) Третью строку умножим на 49 и прибавим к строке F.
При пересчете у нас в столбике F, таблицы (2.2), опятьоказалось отрицательное число, а это говорит о том что решение нужнопродолжать.
Далее, разрешающим столбцом у нас будет Х1, т.котрицательное число -23 находится в нем.
/>Определяемвектор, подлежащий исключению из базиса и выбираем разрешающую строку. Дляэтого находим:
/>Х1= min />; />;/> = 63.
Найдя число /> = 63, => 2-я строка (Х4)является разрешающей. Следовательно, в базис введем Х1 вместо Х4.
Запишем все расчёты в таблицу
Таблица (2.2)Базисные переменные Свободные переменные 1 2 3 4 5 Х1 Х2 Х3 Х4 Х5 1 Х3 510
/>33/7 1 -2/7 2 Х4 207 23/7 1 -5/7 3 Х2 120 1/7 1 1/7 4 F 5880 -23 7
На пересечении разрешающего столбца и строки находитсяразрешающий элемент — это число 23/7. Производим пересчет всех коэффициентовтаблицы, таким образом, чтоб на месте разрешающего элемента получить 1, а вразрешающем столбце все элементы = 0.
Для этого: 1) Третью строку разделим на /> и запишем получившееся вэту же строку.
2) Из первой строки вычтем вторую, умноженную на /> и записываем в первуюстроку.
3) Из третьей строки вычтем вторую умноженную на />, результат запишем втретью строку.
4) К строке F прибавим вторую строку умноженную на 23 изапишем в строку F.
Таблица (2.3)Базисные переменные Свободные переменные 1 2 3 4 5 Х1 Х2 Х3 Х4 Х5 1 Х3 213 1 -33/23 119/161 2 Х1 63 1 7/23 -5/23 3 Х2 111 1 -1/23 28/161 4 F 7329 7 2
Ответ: из изложенного выше экономического содержанияданных таблицы (2.3) следует, что на втором шаге план задачи являетсяоптимальным. Х1* = 63; Х2* = 111. Fmаx= 7329, это значит, что общая стоимость всейпроизведенной продукции, а она равна 7329 рублей, является максимальной
Решение задачи двойственным методом
Под двойственной задачей понимается вспомогательнаязадача линейного программирования, формулируемая с помощью определённых правилнепосредственно из условий прямой задачи. Заинтересованность в определенииоптимального решения прямой задачи путём решения двойственной к ней задачиобусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными.Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числаограничений, а не от количества переменных.
Каждой задаче линейного программирования можноопределенным образом сопоставить некоторую другую задачу линейногопрограммирования, называемую двойственной или сопряженной по отношению кисходной или прямой.
/>/>5Х1+2Х2 ≤ 750 Y1
(1.1) 4Х1+5 Х2 ≤ 807 Y2
Х1+7Х2 ≤ 840 Y3
/>
F = 30Х₁+49Х₂ => max
Целевая функция исходной задачи задаётся на максимум, ацелевая функция двойственной – на минимум.
/>/>Составим матрицу дляисходной задачи:
А = />
Чтобы составить матрицу для двойственной задачи нужноприменить транспонирование (т.е. замена строк – столбцами, а столбцов –стоками)
/>/>АТ = />
Число переменных в двойственной задаче равно числусоотношений в системе (1.1) исходной задачи, т.е. равно трем.
Коэффициентами в целевой функции двойственной задачиявляются свободные члены системы уравнений, т.е 750,807,840.
Целевая функция исходной задачи исследуется на максимум, асистема условий содержит только уравнения. Поэтому в двойственной задачецелевая функция исследуется на минимум, а её переменные могут принимать любыезначения (в том числе и отрицательные). Следовательно, для исходной задачидвойственная задача такова: умножим правые части ограничений на соответствующиепеременные двойственной задачи и сложим их, получим целевую функции
Z(Y) = 750Y1 + 807Y2 + 840Y3 => min.
/>5Y1 + 4Y2 + Y3 ≥ 30
2Y1 + 5Y2 + 7Y3 ≥ 49
Y1 = 0
Y2 = 7
Y3 = 2
Z(Y) = 750·0 + 807·7+ 840·2 = 7329
Ответ: Z(Y) = F(Х) = 7329, Y1* = 0, Y2* = 7, Y3* = 2.
Транспортная задача линейного программирования
Под названием «транспортная задача» объединяется широкийкруг задач с единой математической моделью. Данные задачи относятся к задачамлинейного программирования и могут быть решены симплексным методом. Однакоматрица системы ограничений транспортной задачи настолько своеобразна, что дляее решения разработаны специальные методы. Эти методы, как и симплексный метод,позволяют найти начальное опорное решение, а затем, улучшая его, получитьоптимальное решение.
Задача №2
Формулировка транспортной задачи
На три базы: А₁,А₂, А₃ поступил однородныйгруз в количествах: а₁,а₂, а₃, соответственно. Грузтребуется перевезти в пять пунктов: b₁в пункт В₁, b₂ в пункт В₂, b₃ в пункт В₃, b₄ в пункт В₄, b₅ в пункт В₅.
Спланировать перевозки так, чтобы общая их стоимость быламинимальной. Матрица тарифов сij перевозок между пунктами отправления ипунктами назначения, а также запасы и потребности представлены ниже: