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

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

Сколько стоит помощь?

• Цена зависит от объёма, сложности и срочности. Присылайте любые задания по любым предметам - я изучу и оценю.

Какой срок выполнения?

• Мне и моей команде под силу выполнить как срочный заказ, так и сложный заказ. Стандартный срок выполнения – от 1 до 3 дней. Мы всегда стараемся выполнять любые работы и задания раньше срока.

Если требуется доработка, это бесплатно?

• Доработка бесплатна. Срок выполнения от 1 до 2 дней.

Могу ли я не платить, если меня не устроит стоимость?

• Оценка стоимости бесплатна.

Каким способом можно оплатить?

• Можно оплатить любым способом: картой Visa / MasterCard, с баланса мобильного, google pay, apple pay, qiwi и т.д.

Какие у вас гарантии?

• Если работу не зачли, и мы не смогли её исправить – верну полную стоимость заказа.

В какое время я вам могу написать и прислать задание на выполнение?

• Присылайте в любое время! Я стараюсь быть всегда онлайн.

Содержание:

1. Ответы на вопросы по заказу заданий по линейному программированию:
2. Линейное программирование
3. Задача 1.
4. Задача 2.
5. Графический метод решения задачи линейного программирования
6. Задача 3.
7. Симплексный метод решения задачи линейною программирования
8. Задача 4.
9. Задача 5.
10. Задача 6.
11. Метод искусственных переменных
12. Задача 7.
13. Взаимно двойственные задачи линейного программирования
14. Задача 8.
15. Задача 9.
16. Задача 10.

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

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

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

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

где каждый из знаков означает или Предполагается, что система (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):

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

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

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

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

Таким образом, решение двойственной задачи на базисном решении

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

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