Задача (стр. 2 )

Для того чтобы получить максимум прибыли предприятие должно продавать 15 единиц товаров 1 группы, 0 единиц 2 группы и 10 единиц товаров 3 группы. В этом случае получаемая прибыль составит

Определим структуру товарооборота

товары 1 группы составят %

товары 2 группы составят

Задача №3

Используя вариант предыдущего контрольного задания №25-50 необходимо:

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

- установить сопряженные пары переменных прямой и двойственной задач;

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

Решение

Построим двойственную задачу

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

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

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

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

Если переменная xj исходной задачи может принимать только лишь положительные значения, то j–е условие в системе ограничений двойственной задачи является неравенством вида “ ”.

Двойственная задача

Получили 2 пары задач. Сопряженные пары переменных прямой и двойственной задач

Воспользуемся второй теоремой

Теорема 2 (о дополняющей нежёсткости). Если при подстановке компонент оптимального плана в систему ограничений исходной за­дачи i-е ограничение обращается в строгое неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю. Если i-я ком­понента оптимального плана двойственной задачи положительна, то i-е ограничение исходной задачи удовлетворяется ее оптимальным ре­шением как строгое равенство.

первое ограничение выполняется как строгое равенство, следовательно . Поскольку , то

в результате получаем

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

Задача №4

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

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

76.

Решение

bj	b1	b2	b3	b4	b5
ai
a1	23	21	11	8	3	222
a2	7	17	5	2	4	188
a3	3	9	21	8	4	210
						380
	125	75	200	380	220

Проверим условия задачи на сбалансированность

222+188+210+380=1000

125+75+200+380+220=1000

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

Находим верхний левый угол, в клетку (1,1) помещаем меньшее из и , т. е. 125. Потребности удовлетворены полностью, а у поставщика остаток 222-125=97. Переходим в клетку (1,2). Помещаем в (1,2) меньшее из 97 и , т. е. 75. Потребности удовлетворены полностью, а у поставщика остаток 97-75=22. Переходим в клетку (1,3). Помещаем в (1,3) меньшее из 92 и , т. е. 22. Запасы поставщика исчерпаны. переходим в клетку (2,3). Помещаем в (2,3) меньшее из и 200-22=178, т. е. 178. Потребности удовлетворены полностью. Переходим в клетку (2,4). Помещаем меньшее из 188-178=10и , т. е. 10. Переходим в клетку (3,4) . Помещаем меньшее из и 380-10=370, т. е. 210. Переходим в клетку (4,4). Помещаем меньшее из 370-210=160 и, т. е.160. В клетку (4,5) помещаем 220.

	125	75	22
			178	10
				210
				160	220

Рассчитаем транспортные расходы при таком плане

Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=8, n+m=4+5=9 , что удовлетворяет условию невырожденности плана.

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

Составим вспомогательную рабочую матрицу затрат. Она строится из исходной матрицы издержек путем переноса только тех ячеек Pij которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми.
Кроме того, введем вспомогательный столбец в который внесем значения неизвестных и вспомогательную строку в которую внесем значения неизвестных Эти n+m неизвестных должны для всех (i, j), соответствующих загруженным клеткам, удовлетворять линейной системе уравнений . Пусть тогда

Для свободных клеток определим значения оценок (разность между прямыми и косвенными тарифами)

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

125	75	22
		178	10
			210
			160	220

получим новый план