Решение. 4 страница. Найдя число 192/8 = 24, мы тем самым с экономической точки зрения определили, какое количество изделий С пред­приятие может изготовлять с учетом норм расхода

Найдя число 192/8 = 24, мы тем самым с экономической точки зрения определили, какое количество изделий С пред­приятие может изготовлять с учетом норм расхода и имеющих­ся объемов сырья каждого вида. Так как сырья данного вида соответственно имеется 360, 192 и 180 кг, а на одно изделие С требуется затратить сырья каждого вида соответственно 12, 8 и 3 кг, то максимальное число изделий С, которое может быть изготовлено предприятием, равно , т.е. ограничивающим фактором для производства изделий С является имеющийся объем сырья II вида. С учетом его наличия предприятие может изготовить 24 изделия С. При этом сырье II вида будет полностью использовано.

Следовательно, вектор подлежит исключению из базиса. Столбец вектора и 2-я строка являются направляющими. Элемент, стоящий на пересечении столбца и 2-й строки, называется разрешающим элементом. Составляем таблицу для II итерации (табл. 1.2).

Таблица 1.2

	Базис
					-2

Сначала заполняем строку вектора, вновь введенного в ба­зис, т.е. строку, номер которой совпадает с номером направ­ляющей строки. Здесь направляющей является 2-я строка. Эле­менты этой строки табл. 1.2 получаются из соответствующих элементов табл. 1.1 делением их на разрешающий элемент (т.е. на 8). При этом в столбце записываем коэффициент , стоящий в столбце вводимого в базис вектора . Затем запол­няем элементы столбцов для векторов, входящих в новый базис. В этих столбцах на пересечении строк и столбцов одноимен­ных векторов проставляем единицы, а все остальные элементы полагаем равными нулю.

Для определения остальных элементов табл. 1.2 применяем правило прямоугольника:

a c

d

b , где - пересчитанный коэффициент новой таблицы,

d – разрешающий элемент,

b, c – элементы, стоящие на диагонали прямоугольника.

Вычислим элементы табл. 1.2, стоящие в столбце вектора Первый из них находится в 1-й строке этого столбца. Получаем:

; записываем его в 1-й строке столбца вектора табл. 1.2.

Второй элемент столбца вектора табл. 1.2 был уже вычис­лен ранее. Вычисляем третий элемент столбца вектора : . Число 108 записываем в 3-й строке столбца вектора табл. 1.2.

Значение в 4-й строке столбца этого же вектора можно найти двумя способами:

1) по формуле ,т.е.

2) по правилу прямоугольника; в данном случае прямоугольник образован числами 0, 192, 8, -16. Этот способ приводит к тому же результату: .

Аналогично пересчитываем оставшиеся элементы табл. 1 и записываем их в новую табл. 2.

По окончании расчета всех элементов табл. 1.2 в ней полу­чены новый опорный план и коэффициенты разложения векторов через базисные векторы и значения .Как видно из этой таблицы, новым опорным планом задачи является план . При данном плане производства изготовляется 24 изделия С и остается неисполь­зованным 72 кг сырья I вида и 108 кг сырья III вида. Стоимость всей производимой при этом плане продукции равна 384 руб. Указанные числа записаны в столбце вектора табл. 1.2. Как видно, данные этого столбца по-прежнему представляют собой параметры рассматриваемой задачи, хотя они претерпели зна­чительные изменения. Изменились данные и других столбцов, а их экономическое содержание стало более сложным. Так, на­пример, возьмем данные столбца вектора Число во 2-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий С, если запланировать выпуск одного изделия В. Числа 9 и в 1-й и 3-й строках вектора пока­зывают соответственно, сколько потребуется сырья I и II вида при включении в план производства одного изделия B, а число -2 в 4-й строке показывает, что если будет запланирован вы­пуск одного изделия В, то это обеспечит увеличение выпуска продукции в стоимостном выражении на 2 руб. Иными слова­ми, если включить в план производства продукции одно изде­лие В, то это потребует уменьшения выпуска изделия С на ед. и потребует дополнительных затрат 9 кг сырья I вида и кг сырья III вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастет на 2 руб. Таким образом, числа 9 и выступают как бы новыми «норма­ми» затрат сырья I и III вида на изготовление одного изделия В (как видно из табл. 1.1, ранее они были равны 15 и 3), что объясняется уменьшением выпуска изделий С.

Такой же экономический смысл имеют и данные столбца век­тора табл. 1.2. Несколько иное экономическое содержание имеют числа, записанные в столбце вектора . Число во 2-й строке этого столбца, показывает, что увеличение объемов сырья II вида на 1 кг позволило бы увеличить выпуск изделий С на ед. Одновременно потребовалось бы дополнительно кг сырья I вида и кг сырья III вида. Увеличение выпуска изделий С на ед. приведет к росту выпуска продукции на 2 руб.

Из изложенного выше экономического содержания данных табл. 1.2 следует, что найденный на II итерации план задачи не является оптимальным. Это видно и из 4-й строки табл. 1.2, поскольку в столбце вектора этой строки стоит отрицатель­ное число -2. Значит, в базис следует ввести вектор , т. е. в новом плане следует предусмотреть выпуск изделий В. При определении возможного числа изготовления изделий В следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий В определяется для т.е. находим .

Следовательно, исключению из базиса подлежит вектор , иными словами, выпуск изделий В ограничен имеющимся в распоряжении предприятия сырьем I вида. С учетом имеющих­ся объемов этого сырья предприятию следует изготовить 8 изде­лий В. Число 9 является разрешающим элементом, а столбец вектора и 1-я строка табл. 1.2 являются направляющими. Составляем таблицу для III итерации (табл. 1.3).

Таблица 1.3

	Базис

В табл. 1.3 сначала заполняем элементы 1-й строки, которая представляет собой строку вновь вводимого в базис вектора . Элементы этой строки получаем из элементов 1-й строки табл. 1.2 делением последних на разрешающий элемент (т.е. на 9). При этом в столбце данной строки записываем

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

Проверяем, является ли данный опорный план оптимальным или нет. Для этого рассмотрим 4-ю строку табл. 1.3. В этой строке среди чисел нет отрицательных. Это означает, что найден­ный опорный план является оптимальным и

Следовательно, план выпуска продукции, включающий из­готовление 8 изделий В и 20 изделий С, является оптимальным. При данном плане выпуска изделий полностью используется сырье I и II видов и остается неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 руб.

Оптимальным планом производства продукции не предусмат­ривается изготовление изделий А. Введение в план выпуска про­дукции изделий вида А привело бы к уменьшению указанной общей стоимости. Это видно из 4-й строки столбца вектора , где число 5 показывает, что при данном плане включение в него выпуска единицы изделия А приводит лишь к уменьшению об­щей величины стоимости на 5 руб.

Ответ: максимальная прибыль от реализации всей продукции составляет 400 руб.

Задача 39

1) На три базы поступил однородный груз в ко­личествах, соответственно равных 140, 180 и 160 ед. Этот груз требуется перевезти в пять пунктов назначения соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза с каждого из пунктов отправления в со­ответствующие пункты назначения указаны в следующей таблице:

Таблица 2.1

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

Найти план перевозок данной транспортной задачи методом северо-западного угла.

Решение. При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначе­ния. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного («северо-западный угол») и заканчивается клеткой для неизвестного , т. е. идет как бы по диагонали таблицы.

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

Заполнение таблицы начнем с клетки для неизвестного , т. е. попытаемся удовлетворить потребности первого пункта назначе­ния за счет запасов первого пункта отправления. Так как запасы пункта больше, чем потребности пункта , то полагаем , записываем это значение в соответствующей клетке табл.1и временно исключаем из рассмотрения столбец , считая при этом запасы пункта равными 80.

Таблица 2.2

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

Рассмотрим первые из оставшихся пунктов отправления и назначения . Запасы пункта больше потребностей пункта . Положим , запишем это значение в соответствующей клетке табл. 2.2 и временно исключим из рассмотрения стол­бец . В пункте запасы считаем равными 10 ед. Снова рассмо­трим первые из оставшихся пунктов отправления и назначе­ния Потребности пункта больше оставшихся запасов пункта . Положим и исключим из рассмотрения стро­ку .Значение запишем в соответствующую клетку табл. 2.2 и считаем потребности пункта равными 110 ед.

Теперь перейдем к заполнению клетки для неизвестного и т. д. Через шесть шагов остается один пункт отправления с запасом груза 100 ед. и один пункт назначения с потреб­ностью 100 ед. Соответственно имеется одна свободная клетка, которую и заполняем, полагая (табл. 2.2). В резуль­тате получаем опорный план

Согласно данному плану перевозок, общая стоимость перево­зок всего груза составляет

2) Четыре предприятия для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190, 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Найти опорный план транспортной задачи методом минимального элемента.

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

Исходные данные задачи запишем в виде табл. 3.1.

Таблица 3.1

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

Минимальный тариф, равный 1, находится в клетке для переменной . Положим запишем это значение в соот­ветствующую клетку табл. 3.1 и исключим временно из рассмо­трения строку . Потребности пункта назначения считаем равными 30 ед.

Дата добавления: 2014-12-26