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

Задачи по линейному программированию с решением

 

Если у вас нету времени на задачи по линейному программированию вы всегда можете попросить меня, вам нужно написать мне, и я вам помогу онлайн или в срок 1-3 дня всё зависит что там у вас за работа, вдруг она огромная! Чуть ниже размещён теоретический и практический материал, который вам поможет сделать работу если у вас много свободного времени и желания!

 

Возможно, вас также заинтересует эта ссылка:

Заказать работу по линейному программированию помощь в учёбе

 

Линейное программирование

Задача линейного программирования. Каноническая и стандартная формы

Основные сведения

Пусть Задачи по линейному программированию - множество, заданное системой ограничений

Задачи по линейному программированию
где каждый из знаков означает Задачи по линейному программированию или Задачи по линейному программированию Предполагается, что система (7.1) содержит неравенства

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

Пусть также задана линейная функция

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

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

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

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

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

Если система (7.1) состоит только из уравнений и неравенств вида (7.2), то говорят о канонической форме задачи ЛП, если же в системе (7.1) присутствуют только неравенства, то говорят о стандартной форме задачи ЛП. Если предполагается, что Задачи по линейному программированию

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

 

Возможно, вас также заинтересует эта ссылка:

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

 

 

Задача 1.

Стальные прутья длиной 110 см требуется разрезать на заготовки длиной 50, 45, 30 см. Заготовок длиной 50 см должно быть изготовлено не менее 20, длиной 45 см - не менее 40, длиной 30 см не менее 60. Сколько прутьев и каким способом следует разрезать, чтобы получить указанное количество заготовок при минимальных отходах? Составить математическую модель этой задачи.

  • Решение:

Нетрудно перебрать все возможные варианты разреза (табл. 7.1):

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

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

Задачи по линейному программированию
В итоге приходим к следующей стандартной задаче ЛП:

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

при условиях (7.4).

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

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

 

Возможно, вас также заинтересует эта ссылка:

Контрольная работа по линейному программированию заказать

 

Задача 2.

На двух складах Задачи по линейному программированию имеется 50 и 100 тонн товара соответственно. Потребности магазинов Задачи по линейному программированию в товаре соответственно равны 30, 40, 80 тонн. Известны тарифы перевозок , Задачи по линейному программированию где Задачи по линейному программированию - стоимость в рублях перевозки одной тонны товара со склада Задачи по линейному программированию в магазин Задачи по линейному программированию Найти минимальный по стоимости план перевозки товара со складов в магазины. Составить математическую модель этой задачи.

  • Решение:

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

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

составляет план перевозок. Так как в данном случае суммарные запасы равны суммарным потребностям: 50 + 100 = 30 + 40 + 80, то с каждого склада должен быть вывезен весь товар. Это приводит к уравнениям

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

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

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

Суммарная стоимость всех перевозок задается линейной функцией

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

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

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

при условиях (7.5) - (7.7).

Данная задача приводится к стандартной форме следующим образом. Преобразуем систему (7.5), (7.6) методом Гаусса к виду
Задачи по линейному программированию
с базисными неизвестными Задачи по линейному программированию и свободными неизвестными Задачи по линейному программированию В силу (7.7) справедливы неравенства

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

Заменив в (7.8) базисные неизвестные по формулам (7.9), приведем целевую функцию к виду Задачи по линейному программированию Таким образом, получаехМ задачу линейного программирования в стандартной форме

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

при условиях (7.10), (7.11), эквивалентную задаче в канонической форме.

 

Возможно, вас также заинтересует эта ссылка:

Помощь по линейному программированию онлайн

 

 

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

Основные сведения

Рассматривается задача ЛП в стандартной форме при Задачи по линейному программированию Допустимое множество Задачи по линейному программированию (заданное неравенствами) - выпуклое множество на плоскости Задачи по линейному программированию Целевая функция имеет вид Задачи по линейному программированию

Прямые вида Задачи по линейному программированию где Задачи по линейному программированию - постоянная, называются линиями уровня. Все линии уровня параллельны друг другу

и перпендикулярны общему вектору нормали Задачи по линейному программированию

Задача линейного программирования с двумя переменными допускает решение графическим методом, который состоит в следующем:

  • 1) строится допустимое множество Задачи по линейному программированию
  • 2) если Задачи по линейному программированию - пустое множество, то задача неразрешима, так как система ограничений противоречива;
  • 3) если Задачи по линейному программированию - непустое множество, то рассматриваются линии уровня Задачи по линейному программированию При монотонном увеличении Задачи по линейному программированию от Задачи по линейному программированию прямые Задачи по линейному программированию смещаются параллельно в направлении вектора Задачи по линейному программированию

Если при таком перемещении линии уровня существует Задачи по линейному программированию первая общая точка линии уровня и множества Задачи по линейному программированию то Задачи по линейному программированию - минимум Задачи по линейному программированию на множестве Задачи по линейному программированию Если Задачи по линейному программированию - последняя точка пересечения

линии уровня и множества Задачи по линейному программированию то в этой точке достигается максимум Задачи по линейному программированию на множестве Задачи по линейному программированию Если при неограниченном уменьшении

параметра Задачи по линейному программированию прямая Задачи по линейному программированию пересекает множество Задачи по линейному программированию то Задачи по линейному программированию

Если аналогичное свойство справедливо при неограниченном увеличении параметра Задачи по линейному программированию то Задачи по линейному программированию

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

 

Возможно, вас также заинтересует эта ссылка:

Курсовая работа по линейному программированию заказать готовую онлайн

 

Задача 3.

Найти минимальное и максимальное значения целевой функции Задачи по линейному программированию при условиях:

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

  • Решение:

На рис. 7.1 изображены допустимое множество Задачи по линейному программированию линия уровня Задачи по линейному программированию и вектор нормали Задачи по линейному программированию Перемещая линию

уровня по направлению вектора Задачи по линейному программированию находим сначала точку минимума целевой функции Задачи по линейному программированию а затем точку максимума Задачи по линейному программированию

Задачи по линейному программированию
2. Решить следующую задачу линейного программирования:

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

После исключения переменных Задачи по линейному программированию получим задачу с двумя переменными:

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

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

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

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

В результате получаем оптимальное решение исходной задачи:

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

 

Возможно, вас также заинтересует эта ссылка:

РГР по линейному программированию расчетно графическая работа

 

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

Основные сведения

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

  • 1. Привести задачу к каноническому виду.
  • 2. Преобразовать систему ограничений (уравнений) к специальному виду, в котором переменные разделены на базисные и свободные, а соответствующее базисное решение - неотрицательное (оно называется допустимым базисным решением или опорным решением).

 

Пример такой системы:
Задачи по линейному программированию

где Задачи по линейному программированию - базисные переменные, Задачи по линейному программированию - свободные переменные Задачи по линейному программированию

3. Исключить из целевой функции базисные переменные с помощью (7.12) и записать ее в виде

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

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

Из (7.12), (7.13) следует, что на допустимом базисном решении

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

целевая функция принимает значение Задачи по линейному программированию

После выполнения подготовительного этапа заполняется начальная симплекс-таблица (табл. 7.12):

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

Здесь и ниже используются следующие сокращения:

  • 1. Задачи по линейному программированию - базисные неизвестные.
  • 2. Задачи по линейному программированию - свободные члены.

Таблица соответствует системе уравнений (7.12) с присоединенной целевой функцией (7.13). Последняя строка таблицы называется строкой оценок.

Пусть решается задача о нахождении минимума функции Задачи по линейному программированию

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

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

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

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

2. Если в строке оценок нет положительных чисел, то оптимальное решение найдено.

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

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

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

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

 

 

Задача 4.

Решить симплекс-методом задачу:

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

  • Решение:

Переменные Задачи по линейному программированию - базисные. Исключив их из целевой функции, получаем Задачи по линейному программированию На исходном базисном решении Задачи по линейному программированию значение целевой функции Задачи по линейному программированию

Заполним начальную симплексную таблицу 7.13 и преобразуем ее.

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

Все оценки в последней строке неположительные, следовательно, получено оптимальное решение Задачи по линейному программированиюЗадачи по линейному программированию

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

 

 

Задача 5.

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

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

  • Решение:

Преобразуем целевую функцию: Задачи по линейному программированию Система имеет исходное базисное решение Задачи по линейному программированию со значением целевой функции Задачи по линейному программированию Заполним симплексную таблицу (табл. 7.14) и преобразуем ее в соответствии с алгоритмом.

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

В последней строке есть положительная оценка Задачи по линейному программированию но в соответствующем столбце нет ни одного положительного элемента, следовательно, задача не имеет решения: Задачи по линейному программированию

 

 

Задача 6.

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

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

  • Решение:

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

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

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

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

Использование симплекс-метода

для отыскания допустимого базисного решения.

 

 

 

Метод искусственных переменных

Основные сведения

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

1. Исходная система ограничений- уравнений переписывается в виде

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

где все свободные члены Задачи по линейному программированию

2. В каждое уравнение системы (7.14) вводятся искусственные переменные Задачи по линейному программированию

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

Решение системы (7.15) Задачи по линейному программированию а сама система имеет допустимое базисное решение

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

3. Рассматривается вспомогательная целевая функция

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

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

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

при ограничениях (7.15).

Если эта задача имеет решение, то возможны два случая.

1) Задачи по линейному программированию Тогда исходная система (7.14) не имеет неотрицательных решений.

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

 

 

 

Задача 7.

Преобразовать следующую систему уравнений к виду, допускающему неотрицательное базисное решение:

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

  • Решение:

Введем искусственные переменные Задачи по линейному программированию в двух последних уравнениях (в первом уравнении уже имеется базисная переменная Задачи по линейному программированию

Задачи по линейному программированию
и рассмотрим вспомогательную целевую функцию Задачи по линейному программированию Учитывая (7.16), получаем Задачи по линейному программированию

Решим задачу Задачи по линейному программированию при ограничениях (7.16). Решение дано в виде последовательности симплекс-таблиц (табл. 7.15).

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

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

допускающему неотрицательное базисное решение Задачи по линейному программированиюЗадачи по линейному программированию

 

 

Взаимно двойственные задачи линейного программирования

Основные сведения

Следующие задачи линейного программирования в стандартной форме, записанные в матричной форме, называются симметричной парой взаимно двойственных задач:

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

Решения задач I и II взаимосвязаны. Решив любую из них (исходную задачу), можно восстановить решение другой (двойственной задачи).

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

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

Вторая теорема двойственности. Оптимальные решения

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

пары двойственных задач связаны между собой следующими соотношениями:

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

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

Пусть теперь рассматривается общая задача линейного программирования. Приведем правила построения двойственной задачи. Матрицу коэффициентов при неизвестных дополним справа столбцом знаков неравенств Задачи по линейному программированию и равенств Задачи по линейному программированию для соответствующих ограничений, а также столбцом правых частей. Снизу матрицу дополним строкой ограничений для неизвестных: Задачи по линейному программированию если Задачи по линейному программированию при отсутствии ограничения на знак неизвестной; еще ниже добавим строку коэффициентов целевой функции. В результате получим следующую матрицу:
Задачи по линейному программированию
Тогда аналогичная матрица двойственной задачи выглядит следующим образом:
Задачи по линейному программированию
Из сравнения матриц (7.17) и (7.18) видно, что числовые части этих матриц получаются друг из друга транспонированием. Строка неравенств исходной задачи переходит без изменения в столбец неравенств двойственной задачи, причем символ Задачи по линейному программированию переходит в знак Задачи по линейному программированию Столбец неравенств исходной задачи переходит в строку ограничений на неизвестные, причем знаки неравенства меняются на противоположные, а знаки Задачи по линейному программированию на знаки Задачи по линейному программированию

При этом для пары двойственных задач с матрицами (7.17) и (7.18) остаются в силе формулировки первой и второй теорем двойственности.

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

число неизвестных в каждой задаче станет равным одному и тому же числу Задачи по линейному программированию Можно установить взаимнооднозначное соответствие между этими неизвестными, а именно, основные неизвестные задачи I будут соответствовать дополнительным неизвестным задачи И, и дополнительные неизвестные задачи 1 - основным неизвестным задачи II.

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

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

 

 

Задача 8.

Сформулировать двойственную задачу линейного программирования для следующей задачи:

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

  • Решение:

Составим расширенную матрицу данной задачи:
Задачи по линейному программированию

В соответствии с указанными правилами расширенная матрица двойственной задачи будет выглядеть следующим образом:
Задачи по линейному программированию

Поэтому развернутая запись двойственной задачи имеет вид:

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

 

 

Задача 9.

Найти решение следующей задачи линейного программирования, используя первую и вторую теоремы двойственности:

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

  • Решение:

По общему правилу составим двойственную задачу:

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

Двойственная задача совпадает с задачей из § 7.2, которая была решена графическим методом, и ее оптимальное решение

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

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

Чтобы найти недостающее уравнение, подставим значения Задачи по линейному программированию в неравенства двойственной задачи:

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

Поскольку третье неравенство строгое, то по второй теореме двойственности соответствующая этому неравенству переменная Задачи по линейному программированию Таким образом, имеем систему уравнений:

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

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

 

 

Задача 10.

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

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

  • Решение:

Для решения задачи ЛП симплекс-методом введем дополнительные переменные и изменим знак целевой функции

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

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

Запишем исходную симилекс-таблицу для данной задачи и решим ее симплекс-методом (табл. 7.16):

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

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

Двойственная задача к исходной выглядит следующим образом:

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

Установим соответствие между неизвестными исходной и двойственной задач, записанными в канонической форме:

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

поэтому из строки коэффициентов целевой функции последовательно находим:

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

Таким образом, решение двойственной задачи Задачи по линейному программированию на базисном решении Задачи по линейному программированию