ЧАСТЬ 1 3 страница

В матрице этой системы уравнений имеет:

Векторы - линейно независимы, так как определитель, составленный из компонент этих векторов, отличен от нуля:

Соответствующие этим векторам переменные будут базисными.

Решим систему уравнений относительно базисных переменных.

Функцию цели запишем в виде:

2.Полагая, что свободные переменные =0, =0, =0, получим первый опорный план

=(0,0,01100,120,8000), F = 0, в котором базисные переменные =1100, =120, =8000,

следовательно товары не продаются и прибыль равна нулю, а ресурсы не используются.

Заносим первый опорный план 1 в симплексную таблицу 3.

План	Базисные переменные	Ресурсы плана	Значения коэффициентов при переменных
I план		1100 120 8000	0,1 0,05 3	0,2 0,02 1	0,4 0,02 2		0 1 0
Инд. Строка			-3	-5	-4
II план		5500 10 2500	0,5 0,04 2,5		-0,02 0	-0,1 -5
Инд. Строка			-0,5
III план		5375 250 1 875			2,25 -0,5 1,25	6,25 -2,5 1,25	-12,5 25 -62,5	0 0
Инд. строка					5,75	23,75	12,5

Симплексная таблица 3

Первый опорный план 1 не оптимальный, так как в индексной строке находятся отрицательные коэффициенты - -3,-5,-4.

За ведущий столбец выберем столбец, соответствующий переменной , так как сравнивая по модулю имеем:

|- 5| > |- 3I, |- 4I} Рассчитываем значения 9 по строкам, как частное от деления и выбираем наименьшее:

Следовательно, первая строка является ведущей.

Разрешающий элемент равен 0,2 и находится на пересечении ведущего столбца и ведущей строки и выделен кругом.

5. Формируем следующую симплексную таблицу. Вместо переменной в план II войдет переменная . Строка, соответствующая переменной в плане II, получена в результате деления всех элементов строки плана I на разрешающий элемент . На месте разрешающего элемента в плане II получаем 1. В остальных клетках столбца плана II записываем нули.

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

Элементы строки определяются аналогично:

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

Выполняя последовательно веб этапы алгоритма, формируем план II.

6.На третьей интеракции таблицы 3 получаем план III, который является оптимальным, так как все коэффициенты в индексной строке 0.

Оптимальный план можно записать так:

X = (250,5375,0,0,0,1875), 27625 тыс. руб.

Следовательно, необходимо продавать товаров первой группы А 250 ед., а второй группы В - 5375 ед. При этом торговое предприятие получает максимальную прибыль в размере 27625 тыс. руб. Товары группы С не реализуются.

"В оптимальном плане среди базисных переменных находится дополнительная переменная .Это указывает, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м², так как переменная была введена в третье ограничение задачи, характеризующее собой использование складских помещений.

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какие задачи линейного программирования можно решать симплексным методом?

2. Каков признак оптимальности в симплексном методе?

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

4. Как определяется ведущий столбец и ведущая строка симплексной таблицы?

5. Как осуществляется пересчет элементов симплексной таблицы?

6. Каковы особые случаи при реализации симплексного метода?

3. ДВОЙСТВЕННАЯ ЗАДАЧА.

Двойственная задача формулируется следующим образом.

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

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

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

и доставляет минимальное значение целевой функции

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

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

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

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

3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

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

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

6. Двойственная задача решается на минимум, если целевая функция прямой задачи задаётся на максимум, и наоборот.

7. Коэффициентами функции цели двойственной задачи служат свободные члены системы ограничений прямой задачи.

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

Установим сопряженные пары переменных прямой и двойственной задач. Запишем переменные задач в двух строчках. В первой располагаем переменные по порядку номеров: сначала основные, затем -дополнительные, а во. второй строке запишем переменные двойственной задачи: сначала дополнительные, затем - основные.

основные дополнительные

дополнительные основные

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

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

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

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

Z()=1100y₁+120y₂+8000y₃ min

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

_

= (23,75; 12,5; 0; 0; 0; 5,75) =27625

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Как сформулировать экономическую постановку двойственной задачи к задаче планирования торгового процесса?

2. Как записывается математическая модель прямой и двойственной задач?

3. Каков план построения двойственной задачи?

4. Как определяется сопряженные пары переменных: прямой и двойственной задач?

4. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Транспортная задача заключается в определении оптимального плана перевозок некоторого однородного груза из m пунктов от­правления в пунктов потребления .

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

Введем обозначения:

запасы груза в ом пункте отправления ;

величина заказа на этот груз в ом пункте назначения ;

стоимость перевозки единицы груза из А го пункта отправления в В ый пункт потребления (тариф перевозок);

- количество груза, доставленного из пункта в пункт, 0 •

Определить план перевозок груза из пунктов отправления в пункты назначения так, чтобы: вывести все грузы от поставщиков; удовлетворить заявки каждого потребителя; обеспечить минимальные транспортные расходы на перевозку груза.

Все исходные данные транспортной задачи можно записать в виде транспортной таблицы 4.

Таблица 4

Пункты отправления	Пункты назначения	Запасы
		…		…
			…		…
			…		…
…	…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…	…
			…		…
Заявки			…		…

где - суммарный запас груза у поставщиков;

- суммарная величина заявок потребителей.

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

', , которая удовлетворяет следующим условиям:

а) Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей

', называется допустимым планом транспортной задачи.

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

в) Допустимый план транспортной задачи, имеющий не более отличных от нуля величин , называется опорным.

г) Если в опорном плане число отличных от нуля компонент равно в точности , то план является невырожденным, если меньше, то план называется вырожденным.

д) План ', при котором функция 4 принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

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

ж) Модель транспортной задачи, удовлетворяющая этому условию, называется закрытой. Если же указанное условие не выполняется, то модель называется открытой.

В случае превышения запаса над заявками:

вводится фиктивный пункт назначения с потребностью

= и соответствующие тарифы считаются равными нулю: .

При вводится фиктивный (m+1) пункт отправления с запасом груза = , итарифы принимаются равными нулю:

Рассмотрим один из методов построение первого опорного плана - метод наименьших тарифов.

з) Наилучшим элементом матрицы тарифов называется наименьший тариф, если задача поставлена на минимум, наибольший тариф - если задача поставлена на максимум целевой функции.

Алгоритм построения первого опорного плана методом наименьшей стоимости включает следующие этапы.