Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Торговое предприятие, располагающее материально-денежными ресурсами, реализует три группы товаров А, В и С. Плановые нормативы затрат ресурсов на тыс, руб. товарооборота, прибыль от продажи товаров на тыс. руб. товарооборота, а также объем ресурсов заданы в таблице 2.
Определить плановый объем продажи и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.
1. Запишем математическую модель задачи.
Определить =(x1, x2, x3), который удовлетворяет условиям
и обеспечивают максимальное значение целевой функции .
Таблица 2
Виды материально-денежных ресурсов | Норма затрат материально-денежных ресурсов на ед. товарооборота, тыс. руб. | Объем ресурсов b1 | ||
А группа | В группа | С группа | ||
Рабочее время продавцов, чел/ч | 0,1 | 0,2 | 0,4 | |
Площадь торговых залов, м2 | 0,05 | 0,02 | 0,02 | |
Площадь складских помещений. м2 | ||||
Прибыль, т.руб. | max |
Для построения первого опорного плана систему неравенств приведем к системе уравнений.
В матрице этой системы уравнений А=(аij) имеет:
векторы А4,А5,А6 - линейно независимы, так как определитель, составленный из компонент этих векторов, отличен от нуля:
Соответствующие этим векторам переменные х4,.х5.х6 будут базисными.
Решим систему уравнений относительно базисных переменных
Функцию цели запишем в виде:
=0-(-3x1-5x2-4x3).
2. Полагая, что свободные переменные x1=0, х2=0, х3=0, полупим первый опорный план =(0,0,0,1100,120,8000), F()=0, в котором базисные переменные х4=1100, х5=120, х6=8000, следовательно товары не продаются и прибыль равна нулю, а ресурсы не используются.
Заносим первый опорный план 1 в симплексную таблицу 3.
3. Первый опорный план 1 не оптимальный, так как в индексной строке находятся отрицательные коэффициенты - -3,-5,-4.
За ведущий столбец выберем столбец, соответствующий временной х2, так как сравнивая по модулю имеем: |5|>{|3|, |4|} Рассчитываем значения 0 по строкам, как частное от отделения и выбираем наименьшее:
Симплексная таблица 3
План | Базисные переменные | Ресурсы план | Значения коэффициентов переменных при | ||||||
х1 | х2 | х3 | х4 | xs | х6 | ||||
I план | x4 x5 x6 | 1100 120 8000 | 0,1 0,05 3 | 0,2 0,02 | 0,4 0,02 2 | 5500 6000 8000 | |||
Индексная строка | -3 | -5 | -4 | ||||||
II план | х2 x5 x6 | 5500 10 | 0,5 0,04 2,5 | -0,02 | –0,1 -5 | ||||
Индексная строка | -0,5 | ||||||||
III план | х2 х1 х6 | 5 375 | 2,25 -0,5 1,25 | 6,25 -2,5 1,25 | -12,5 -62,5 | ||||
Индексная строка | 27 625 | 5,75 | 23,75 | 12,5 |
Следовательно, первая строка является ведущей.
Разрешающий элемент равен 0,2 и находится на пересечении следующего столбца и ведущей строки и выделен кругом.
5. Формируем следующую симплексную таблицу. Вместо переменной х4 в план II войдет переменная х2. Строка, соответствующая переменной х2 в плане II, получена в результате деления всех элементов строки х4 плана I на разрешающий элемент РЭ=0,2. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столбца х2 плана II записываем нули.
Таким образом в новом плане II заполнены строки х2 и столбец х2. Все остальные элементы нового плана II, включая элементы индексной строки определяется по правилу прямоугольника. Для этого выбираем из старого плана 4 числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=0,2. Во второй вершине по диагонали находится старое значение элемента например, значение целевой функции F(K,)=0=C3, которое указывает на место расположение нового НЭ в новом плане II. Третий элемент А=1100 и четвертый элемент В=-5 завершают построение прямоугольника в недостающих двух вершинах и расположены по другой диагонали. Значение нового элемента в плане II находится из выражения:
Элементы строки определяются аналогично:
Все элементы, расположенные на пересечении строк и столбцов, соответствующих одноименным базисным элементам равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны 0. Аналогично проводятся расчеты по всем строкам таблицы, включая индексную.
Выполняя последовательно все этапы алгоритма, формируем план II.
6. На третьей итерации таблицы 3 получаем план III, который является оптимальным, так как все коэффициенты в индексной строке ≥0.
Оптимальный план можно записать так:
=(250,5375,0,0,0,1875), =27625 тыс. руб.
Следовательно, необходимо продавать товаров первой группы А 250 ед., а второй группы В - 5375 ед. При этом торговое предприятие получает максимальную прибыль в размере 27625 тыс. руб. Товары группы С не реализуются.
В оптимальном плане среди базисных переменных находится дополнительная переменная х6. Это указывает, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м2. так как переменная х6 была введена в третье ограничение задачи, характеризующее собой использование складских помещений.
В индексной строке оптимального плана в столбцах переменных х3, х4, х5 не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи Линейного программирования является единственным.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Какие задачи линейного программирования можно решать симплексным методом?
2. Каков признак оптимальности в симплексном методе?
3. Как строится первый опорный план?
4. Как определяется ведущий столбец и ведущая строка симплексной таблицы?
5. Как осуществляется пересчет элементов симплексной таблицы?
6. Каковы особые случаи при реализации симплексного метода?
Дата публикования: 2015-03-29; Прочитано: 298 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!