Контрольная работа по "Математическое программирование"

     

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

     

     Найдем  решение двойственной задачи.

     Из  первой теоремы двойственности . По второй теореме двойственности получаем: так как , то ограничения выполняются как равенства:

     

     Подставим (оптимальный план исходной задачи) в ограничения исходной задачи и получим:

     

     Тогда

     

 

       

     Ответ: максимальная прибыль составляет 10800 руб. при производстве изделий А в количестве 12 ед., изделий В в количестве 18 ед.  
 

     Задача  2

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

     Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.

     Решить  транспортную задачу методом потенциалов. 

 

     Решение

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

     Найдем  опорное решение с помощью  метода минимальной стоимости (табл. 4).

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

     Таблица 4

 

     Транспортные  расходы составляют:

     

 ден.ед.

     Проверим  полученный опорный план на оптимальность  с помощью метода потенциалов.

     Построим  систему потенциалов:

       

     Найдем  оценки каждой свободной клетки:

       и т.д.

     В результате получим (табл. 5):

     Таблица 5

 

     Т.к. имеются положительные оценки, план не является оптимальным. Выбираем максимальную из положительных. Поэтому строим цикл, начиная с клетки (3,1). . Учитывая это, получим табл. 6.

     Таблица 6

 

     Положительный оценок нет, поэтому план является оптимальным. Минимальные транспортные расходы составляют:

     

 ден.ед.

     План  перевозок имеет вид: