Правило построения двойственной пары





К пяти признакам, сформулированным ранее, необходимо добавить следующие:

1. в исходной задаче ограничения неравенства следует записывать со знаком ≥, если целевая функция стремится к min, и со знаком ≤, если целевая функция стремится к max;

2. каждому ограничению неравенства исходной задачи соответ­ствует в двойственной задаче условие неотрицательности переменных
uj ≥ 0;

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

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

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

Теорема (вторая теорема двойственности).Для того чтобы допустимые решения X = (x1, x2, ..., xn) и U = (u1, u2, ..., um) являлись оптимальными решениями пары двойственных задач, необходимо и достаточно, чтобы выполнялись следующие условия сопряжения:

 

Пара двойственных задач может быть решена симплекс методом. Преобразуем пару двойственных задач к виду, допускающему при­менение симплекс алгоритма. Для этого введем неотрицательные выравнивающие переменные yj, j =1,2,…,m в прямую задачу и vi, i = 1,2,…, n – в двойственную задачу:

 

прямая задача:

(1.8)

 

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

(1.9)

 

Построим для задач (1.8) и (1.9) общую симплекс-таблицу,причем эта таблица имеет дополнительные столбец и строку для двойственной задачи:

 

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


1.1 Задания

 

Задание 1.1.1

 

Составьте математическую модель задачи:

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

 

Вариант 1

Вид сырья Норма расхода на 1 изделие Запас на складе
А Б
прибыль от 1 изделия  

 

Вариант 2

Вид сырья Норма расхода на 1 изделие Запас на складе
А Б
прибыль от 1 изделия  

 

Вариант 3

Вид сырья Норма расхода на 1 изделие Запас на складе
А Б
прибыль от 1 изделия  

 

Вариант 4

Вид сырья Норма расхода на 1 изделие Запас на складе
А Б
прибыль от 1 изделия  

 

Вариант 5

Вид сырья Норма расхода на 1 изделие Запас на складе
А Б
прибыль от 1 изделия  

 

 


Задание 1.1.2

 

Составьте математическую модель задачи:

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

 

 

Вариант 1

Вид питательного вещества Содержание питательного вещества в единице корма Необходимое количество питательного вещества
А Б
Стоимость единицы корма  

 

 

Вариант 2

Вид питательного вещества Содержание питательного вещества в единице корма Необходимое количество питательного вещества
А Б
Стоимость единицы корма  

 

 

Вариант 3

Вид питательного вещества Содержание питательного вещества в единице корма Необходимое количество питательного вещества
А Б
Стоимость единицы корма  

 

Вариант 4

Вид питательного вещества Содержание питательного вещества в единице корма Необходимое количество питательного вещества
А Б
Стоимость единицы корма  

 

Вариант 5

Вид питательного вещества Содержание питательного вещества в единице корма Необходимое количество питательного вещества
А Б
Стоимость единицы корма  

 

Задание 1.1.3

 

Решить ЗЛП графическим методом.

 

Вариант 1   Вариант 2
Вариант 3 Вариант 4
Вариант 5    

Задание 1.1.4

 

Записать симметричную двойственную пару ЗЛП. Привести к виду для составления общей симплекс - таблицы.

 

Вариант 1 Вариант 2
  Вариант 3   Вариант 4
  Вариант 5  

 

 


2. Транспортная задача

 

2.1 Основные определения и понятия

 

Постановка транспортной задачи (ТЗ)

Однородный груз находится у т поставщиков в объемах а1, а2. ..., аm. Груз необходимо доставить n потребителям в объемах b1 , b2, ..., bn. Общий объем поставок равен общему объему заявок. Заданы стоимости сij, i = 1,2,…, m, j =1,2,…, п доставки единицы груза от каждого поставщика i каждому потребителю j. Требуется рассчитать такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, заявки всех потребителей полностью удовлетворяются и суммарные транспортные издержки минимальны.

 

Математическая модель ТЗ

(2.1)     (2.2)     (2.3)     (2.4)   (2.5)

Переменными (неизвестными) ТЗ являются хij– объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Целевая функция (2.1) выражает требование минимизации транспортных издержек на перевозку всех грузов. Ограничения (2.2) отражают тот факт, что запасы всех m поставщиков вывозятся полностью. Ограничения (2.3) выражает требование полностью удовлетворить заявки всех п потребителей. Ограничения (2.4) называется уравнением баланса и отражает равенство общего объема поставок общему объему заявок.

Математическая формулировка ТЗ: найти такой план перевозок хij, удовлетворяющий ограничениям (2.2)–(2.5) и обеспечивающий минимум целевой функции (2.1). ТЗ всегда имеет решение, т.к. целевая функция (2.1) ограничена снизу нулем ввиду неотрицательности её слагаемых.

Исходные данные ТЗ записываются в таблице (называемой транспортной таблицей) вида

 

bj ai b1 b2 bn
a1 c11 c12 c1n
a2 c21 c22 c2n
am cm1 cm2 cmn

В дальнейшем все действия по нахождению решения ТЗ будут сводиться к преобразованию транспортной таблицы.

Доказано, что система ограничений (2.2)-(2.5) ТЗ имеет ранг
N = m + n – 1, поэтому решение ТЗ не может иметь отличных от нуля координат больше, чем N. Значит, в каждом решении, включая оптимальное, будут отличны от нуля не более, чем (n+т—1) перевозок хij. Ячейки (клетки) таблицы, в которых записываются эти отличные от нуля перевозки, называются базисными, а остальные (пустые) - свободными.

Решение ТЗ называется невырожденным, если число ненулевых координат вектора решения X равно N = m + n – 1. Уравнение баланса (2.4) является обязательным условием решения ТЗ.

Когда уравнение баланса нарушено, то в ТЗ необходимо искусственно восстановить баланс следующим способом:

- в ТЗ с избытком заявок вводится фиктивный поставщик с запасом аф, равным недостающему объему поставок;

- в ТЗ с избытком запасов вводится фиктивный потребитель с заявкой bф, равной превышающему объему поставок.

Транспортная таблица дополняется в первом случае фиктивной строкой аф, во втором – фиктивным столбцом bф. В клетках таблицы, связывающих фиктивные пункты с реальными, стоимости перевозки
сij = 0.

 

Метод «северо-западного угла»

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

После построения начального опорного решения необходимо проверить, чтобы число занятых клеток равнялось N = m + n – 1, т.е. решение было невырожденным.





Читайте также:
Пример оформления методической разработки: Методическая разработка - разновидность учебно-методического издания в помощь...
Конфликтные ситуации в медицинской практике: Наиболее ярким примером конфликта врача и пациента является...
Жанры народного творчества: Эпохи, люди, их культуры неповторимы. Каждая из них имеет...
Тест Тулуз-Пьерон (корректурная проба): получение информации о более общих характеристиках работоспособности, таких как...

Рекомендуемые страницы:


Поиск по сайту

©2015-2019 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-03-02 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:

Обратная связь
0.023 с.