Контрольная работа по "Моделирование"

Как говорит  народная мудрость, на ошибках учатся.

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 2

Двойственные  задачи в ЛП. Вторая теорема двойственности, т. е. условия о

дополняющей нежесткости, соответствие между переменными  прямой и

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

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

1. В одной  задаче ищется максимум, а в  другой минимум целевой функции.

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

3. В каждой  задаче система ограничений задаётся  в виде неравенств, причём все они одного смысла, а именно: в задаче, в которой ищется максимум линейной формы, все неравенства вида "<=", а в задаче, в которой находится минимум линейной формы, противоположного смысла, т.е.">=".

4. Коэффициенты  при переменных систем ограничений описываются матрицами, транспонированными относительно друг друга.

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

6. Условия не  отрицательности переменных сохраняются  в обеих задачах.

Отсюда вытекает правило составления задачи, двойственной к исходной.

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

Для этого неравенства, у которых вид не соответствует  типу задачи, необходимо умножить на (-1). Далее преобразовать исходную задачу, руководствуясь свойствами (1-6).

Пример:

Вторая теорема  двойственности или теорема о  дополняющей нежесткости.

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

Из условий следует:

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

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

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

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

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

Основные переменные i x обозначали количество произведенной  продукции i-го вида, дополнительные переменные обозначали количество излишков соответствующего вида ресурсов, каждое из неравенств выражало собой расход определенного вида сырья в сравнении с запасом этого сырья. Дополнительные переменные двойственной задачи характеризуют рентабельность продукции. При этом, если у_i>0 то продукция нерентабельна.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 3

Решить транспортную задачу (200;150;150) i a_i - запас единиц груза i-го поставщика, B_j - потребность единиц груза j-го потребителя,

Решение.

Обозначим объем  продукции доставленный от поставщика A_i потребителю B_j через X_i,j . Суммарные потребности потребителей 90+100+70+130+110=500 равны суммарным запасам 200+150+150=500 продукции всех поставщиков. Имеем транспортную задачу закрытого типа. Опорный план находим методом северо-западного угла.

Записываем в левый нижний угол клетки А₁В₁ – 90 ед. продукции. Потребности полностью удовлетворены. Столбец В₁ вычеркиваем. У поставщика А₁ осталось 110 ед. продукции. Удовлетворим потребности 2-го потребителя B₂ за счет запаса поставщика А₁.

Записываем  в левый нижний угол клетки А₁В₂ – 100 ед. продукции. Потребности полностью удовлетворены. Столбец В₂ вычеркиваем. У поставщика А₁ осталось 10 ед. продукции. Записываем в левый нижний угол клетки А₁В₃ – 10 ед. продукции. Запасы полностью исчерпаны. Строку А₁ вычеркиваем.

Удовлетворяем потребителя B₃ за счет запаса поставщика А₂. Записываем 60 ед. в клетку А₂B₃. Потребности полностью удовлетворены. Столбец В₃ вычеркиваем. У поставщика А₂ осталось 90 ед. продукции. Записываем в левый нижний угол клетки А₂В₄ – 90 ед. продукции. Запасы полностью исчерпаны. Строку А₂ вычеркиваем.

Удовлетворяем потребителя B₄ за счет запаса поставщика А₄. Записываем 40 ед. в клетку А₃B₄. Потребности полностью удовлетворены. Столбец В₄ вычеркиваем. У поставщика А₃ осталось 110 ед. продукции. Записываем в левый нижний угол клетки А₃В₅ – 110 ед. продукции. Потребности полностью удовлетворены и запасы исчерпаны. Столбец В₅ и строку А₃ вычеркиваем.

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

Число занятых  клеток должно быть равно m+ n-1= 3+5-1= 7. В нашем случае число занятых клеток равно 7. Имеем невырожденный план.

Построенному  опорному решению отвечают затраты:

Проверим полученный опорный план на оптимальность. Находим потенциалы: U_i и V_j . Для каждой базисной переменной X_i,j потенциалы удовлетворяют условию U_i + V_j = c_i,j. Имеем систему

Теперь для  небазисных клеток найдем оценки  S _I,j=C_i,j-(U_i + V _j). Оценки запишем в левый нижний угол (красный цвет). Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка (-8) стоит в ячейке А₁В₅.

Вводим в  базис переменную  X₁₅ и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+». Выбираем наименьшее значение из клеток со знаком «-» min(10,190;110) =10 : прибавляя 10 к значениям в клетках со знаком «+» и вычитая 10 из значений в клетках со знаком «-».

Теперь для  небазисных клеток найдем оценки S _I,j=C_i,j-(U_i + V_j).. Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка (-9) стоит в ячейке А₂В₂. Вводим в базис переменную  X₂₂ и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+». Выбираем наименьшее значение из клеток со знаком «-» min(100,80;100) =80 : прибавляя 80 к значениям в клетках со знаком «+» и вычитая 80 из значений в клетках со знаком «-».

Теперь для  небазисных клеток найдем оценки S _I,j=C_i,j-(U_i + V_j). Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка (-2) стоит в ячейке А₃В₂. Вводим в базис переменную X₃₂ и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+». Выбираем наименьшее значение из клеток со знаком «-» min(20,20) =20 : прибавляя 20 к значениям в клетках со знаком «+» и вычитая 20 из значений в клетках со знаком «-».

Так как среди  оценок нет отрицательных, то план оптимален.

Согласно плану  перевозок 1-ый поставщик отправляет 90 ед. продукции первому потребителю и 110 ед. продукции пятому потребителю.

2-ой поставщик отправляет 80 ед. продукции второму потребителю и 70 ед. продукции третьему потребителю.

3-ий поставщик  отправляет 20 ед. продукции второму  потребителю, 130 ед. продукции четвертому потребителю.

Суммарные затраты  при этом f _min =6520.

 

 

 

 

 

 

Список используемой литературы

1. http://www.pereplet.ru/obrazovanie/stsoros/655.html
2. http://www.structuralist.narod.ru/dictionary/mathprog.htm