Размещено на http://www.allbest.ru/

4

КОНТРОЛЬНАЯ РАБОТА

на тему: «Область линейных неравенств. Анализ прибыли и товарооборота»

Содержание

Задача 5

Задача 28

Задача 76

Задача 92

система плоскость уравнение товарооборот прибыль

Задача 5

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

Решение.

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

Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение (рис.1.).

Многоугольником решений задачи является четырехугольник АВСD, координаты точек которого удовлетворяют условию неотрицательности и неравенствам системы ограничений задачи.

Для нахождения точек экстремума построим начальную прямую и вектор .

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

Получим координаты точки .

Рис.1.

Вычислим значение функции .

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

.

Ответ: при ; при .

Задача 28

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве единиц, ресурса второго вида в количестве единиц, ресурса третьего вида в количестве единиц. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве и единиц, ресурсов второго вида в количестве и единиц, ресурсов третьего вида в количестве и единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно (тыс. руб.)

Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

Решение.

Составим таблицу:

Запишем математическую модель задачи.

Определим , который удовлетворяет условиям

и обеспечивают максимальное значение целевой функции

Перейдем от неравенств к равенствам, прибавляя к левым частям неотрицательные дополнительные переменные , и :

Преобразованную систему ограничений запишем в векторной форме:

,где

, , , , , .

Исходный единичный базис состоит из векторов , и ; ему соответствует опорный план .

Составим симплекс-таблицу для первой итерации:

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

Переходим к новому опорному решению. В базис введем вектор (столбец разрешающий), так как -8 по модулю наибольшее значение. , соответствует второй строке, поэтому вектор исключаем из базиса. Разрешающий элемент 7.

Пересчитаем рабочую область таблицы, в результате получим симплекс-таблицу для второй итерации:

Новый план

соответствует значению целевой функции . Есть отрицательная оценка -1 5/7. Решение не оптимально. Переходим к новому опорному решению. В базис введем вектор (столбец разрешающий). . вектор исключаем из базиса. Разрешающий элемент 4 3/7.

Пересчитаем рабочую область таблицы, в результате получим симплекс-таблицу для третьей итерации:

Новый план

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

Согласно этому плану необходимо продать единиц товара первой группы и единиц третьей группы. Максимальная прибыль при этом будет равна тысяч рублей. В оптимальном плане среди базисных переменных находится дополнительная переменная . Это указывает, что ресурсы третьего вида недоиспользованы на единиц, так как переменная была введена в третье ограничение задачи, характеризующее собой использование этого ресурса.

Задача 76

Поставщики товара - оптовые коммерческие предприятия имеют запасы товаров соответственно в количестве ед. и розничные торговые предприятия - подали заявки на закупку товаров в объемах соответственно: . Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребление заданы в виде матрицы .

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

Решение.

Проверим необходимое и достаточное условие разрешимости задачи.

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

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

1. Начинаем заполнение таблицы с клетки, которой соответствует наименьший тариф из всей таблицы: , возьмем . Объем запасов поставщика и потребностей потребителя после первого шага уменьшится на : , , это означает, что у первого поставщика закончились запасы. Далее при построении опорного плана исключим строку .

2. . . Корректируем запасы и потребности: , . Потребности удовлетворены, вычеркнем первый столбец.

3. , возьмем . Корректируем запасы и потребности: , . Потребности удовлетворены, вычеркнем пятый столбец.

4. . . Корректируем запасы и потребности: , . Запасы исчерпаны, вычеркнем третью строку.

5. , возьмем . . Корректируем запасы и потребности: , . Потребности удовлетворены, вычеркнем четвертый столбец.

6. . . Корректируем запасы и потребности: , . Потребности удовлетворены, вычеркнем второй столбец.

7. . . Корректируем запасы и потребности: , . Запасы исчерпаны, вычеркнем первую строку.

8. . . Корректируем запасы и потребности: , . Потребности удовлетворены, вычеркнем третий столбец.

Суммарные издержки на перевозку продукции составляют величину, равную:

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

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

.

Значения оценок поместим в нижний левый угол незанятых ячеек.

Наибольшая положительная оценка 10, тогда разрешающая коммуникация (2;3). План не является оптимальным, так как есть положительная оценка. Строим цикл пересчета. Величина корректировки . Вносим изменения в план: перевозки отрицательного полуцикла уменьшаем на , а положительного увеличиваем на эту же величину. Остальные перевозки оставляем без изменения. Переменная исключается из базиса, а переменная вводится со значением 188. Получим план .

Значение функции . План не является оптимальным, так как есть положительные оценки. Находим наибольшую положительную оценку 9(их две). Выбираем коммуникацию с наименьшим тарифом. Строим цикл пересчета и определяем величину корректировки плана . Переменная исключается из базиса, а переменная вводится со значением 10. Изменяя перевозки в вершинах цикла, получим допустимый план .

Значение функции . План не является оптимальным, так как есть положительные оценки. Находим наибольшую положительную оценку 3. Строим цикл пересчета и определяем величину корректировки плана . Переменная исключается из базиса, а переменная вводится со значением 125. Изменяя перевозки в вершинах цикла, получим допустимый план .

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

Анализ плана. Из первой базы необходимо груз направить в третий и пятый магазин, из второй базы направить в третий магазин, с третьей базы следует вывозить в четвертый, а с четвертой базы в первый, второй, четвертый и пятый магазины в количестве 12, 210, 188, 210, 125, 75, 170 и 10 единиц соответственно. Общая стоимость доставки груза потребителям будет минимальной, и составляет 4 992 тыс. руб.

Задача 92

Поставщики товара - оптовые коммерческие предприятия имеют запасы товаров соответственно в количестве ед. и розничные торговые предприятия - подали заявки на закупку товаров в объемах соответственно: . Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребление заданы в виде матрицы .

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

Решение.

Проверим необходимое и достаточное условие разрешимости задачи.

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на трех базах. Следовательно, модель исходной транспортной задачи является не сбалансированной. Чтобы получить сбалансированную модель, введем дополнительную (фиктивную) базу А₄ с запасом груза, равным 790 - 780 = 10 (ед.). Тарифы перевозки единицы груза из базы А₄ во все магазины полагаем равны нулю.

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

1. Начинаем заполнение таблицы с клетки, которой соответствует наименьший тариф из всей таблицы: , . Объем запасов поставщика и потребностей потребителя после первого шага уменьшится на : , , это означает, что у четвертого поставщика закончились запасы. Далее при построении опорного плана исключим строку .

2. . . Корректируем запасы и потребности: , . Потребности удовлетворены, вычеркнем четвертый столбец.

3. , . Корректируем запасы и потребности: , . Запасы исчерпаны, вычеркнем первую строку.

4. . . Корректируем запасы и потребности: , . Потребности удовлетворены, вычеркнем третий столбец.

5. . . Корректируем запасы и потребности: , . Запасы исчерпаны, вычеркнем третью строку.

6. . . Корректируем запасы и потребности: , . Потребности удовлетворены, вычеркнем второй столбец.

7. . . Корректируем запасы и потребности: , . Потребности удовлетворены, вычеркнем первый столбец.

Суммарные издержки на перевозку продукции составляют величину, равную:

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

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

.

Значения оценок поместим в нижний левый угол незанятых ячеек.

Наибольшая положительная оценка 18, тогда разрешающая коммуникация (2;4). План не является оптимальным, так как есть положительная оценка. Строим цикл пересчета. Величина корректировки . Вносим изменения в план: перевозки отрицательного полуцикла уменьшаем на , а положительного увеличиваем на эту же величину. Остальные перевозки оставляем без изменения. Переменная исключается из базиса, а переменная вводится со значением 115. Получим план .

Значение функции . План не является оптимальным, так как есть положительные оценки. Находим наибольшую положительную оценку 16(их две). Выбираем коммуникацию с наименьшим тарифом. Строим цикл пересчета и определяем величину корректировки плана . Переменная исключается из базиса, а переменная вводится со значением 10. Изменяя перевозки в вершинах цикла, получим допустимый план .

Значение функции . План не является оптимальным, так как есть положительные оценки. Находим наибольшую положительную оценку 14. Строим цикл пересчета и определяем величину корректировки плана . Переменная исключается из базиса, а переменная вводится со значением 65. Изменяя перевозки в вершинах цикла, получим допустимый план .

Значение функции . План не является оптимальным, так как есть положительные оценки. Находим наибольшую положительную оценку 14. Строим цикл пересчета и определяем величину корректировки плана . Переменная исключается из базиса, а переменная вводится со значением 10. Изменяя перевозки в вершинах цикла, получим допустимый план .

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

Анализ плана. Из первой базы необходимо груз направить в первый магазин, из второй базы направить в четвертый магазин, с третьей базы следует вывозить в первый, второй, третий и четвертый магазины в количестве 210, 190, 180, 65, 125 и 10 единиц соответственно. Общая стоимость доставки груза потребителям будет минимальной, и составляет 4 365 тыс. руб.

Размещено на Allbest.ru