1. Правила получения условий двойственной задачи.

Одним из способов экономического анализа решения, его чувствительности к возможным изменениям является построе­ние так называемых двойственных задач. В принципе любой зада­че линейного программирования соответствует действенная (об­ратная) по отношению к ней; она строится по определенным правилам.Воспользуемся простой и наиболее универсальной схемой, основанной на представлении любой задачи в стандарт­ной форме, в которой все ограничения приведены к типу «=» с помощью остаточных и избыточных переменных, но без искусст­венных переменных, а правые части ограничений и все перемен­ные неотрицательны. Теоремы: 1. если 1 из двойственных задач имеет оптимальное решение х* , то и другие имеют оптимальное решение у^* ,причем max z= min F 2. для оптимальности допустимых решений прямой и двойственной задачи необходимо достаточно чтобы выполнились следующие условия: если сумма от i=1 до n a_ij x_j <= b_i  то у_i^* =0, если сумма от j=1  до n a_ij y_i >= c_j то x_j^* =0.

исходная	двойственная
1. max Z	Min F
2. переменные х	Переменные у
3.  кол-во переменных х	Кол-во ограничений
4.  кол-во ограничений	Кол-во переменных
5. хj>=0	j=0
6. i<=0	yi=0
7. хj не ограничено по знаку	j ограничение вида =
8. i ограничение вида =	yi не ограничено по знаку
9. свободный член ограничений Вi	Коэф-ты Сi в целевой функции
10.коэф. при хj в целев.функцииСi	Свободный член ограничения
11.матрица коэф-ов при неизвестных в ограничениях А	Транспонированная матрица Ат

2. Постановка задачи оптимизации размещения культур по участкам различного плодородия.

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

Экономико - математическая модель:

Переменные: площади под культуры на первой почвенной разности, прирост продукции с первой почвенной разности, площади под культуры на второй почвенной разности, прирост продукции со второй почвенной разности

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

Целевая функция максимум чистого дохода, руб.

Задача относится к блочно–диагональному типу.

 

Билет 18 Стандартная и каноническая формы задачи линейного программирования.

1. Основные положения теории двойственности.

Одним из способов экономического анализа решения, его чувствительности к возможным изменениям является построе­ние так называемых двойственных задач. В принципе любой зада­че линейного программирования соответствует действенная (об­ратная) по отношению к ней; она строится по определенным правилам.Воспользуемся простой и наиболее универсальной схемой, основанной на представлении любой задачи в стандарт­ной форме, в которой все ограничения приведены к типу «=» с помощью остаточных и избыточных переменных, но без искусст­венных переменных, а правые части ограничений и все перемен­ные неотрицательны. Теоремы: 1. если 1 из двойственных задач имеет оптимальное решение х* , то и другие имеют оптимальное решение у^* ,причем max z= min F 2. для оптимальности допустимых решений прямой и двойственной задачи необходимо достаточно чтобы выполнились следующие условия: если сумма от i=1 до n a_ij x_j <= b_i  то у_i^* =0, если сумма от j=1  до n a_ij y_i >= c_j то x_j^* =0.

исходная	двойственная
1. max Z	Min F
2. переменные х	Переменные у
3.  кол-во переменных х	Кол-во ограничений
4.  кол-во ограничений	Кол-во переменных
5. хj>=0	j=0
6. i<=0	yi=0
7. хj не ограничено по знаку	j ограничение вида =
8. i ограничение вида =	yi не ограничено по знаку
9. свободный член ограничений Вi	Коэф-ты Сi в целевой функции
10.коэф. при хj в целев.функцииСi	Свободный член ограничения
11.матрица коэф-ов при неизвестных в ограничениях А	Транспонированная матрица Ат

 

2. Математическая модель задачи оптимизации размещения культур по участкам различного плодородия.

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

Экономико - математическая модель:

Переменные: площади под культуры на первой почвенной разности, прирост продукции с первой почвенной разности, площади под культуры на второй почвенной разности, прирост продукции со второй почвенной разности

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

Целевая функция максимум чистого дохода, руб.

Задача относится к блочно–диагональному типу

Билет 19 Теорема о разрешимости транспортной задачи. Сведение задачи открытого типа к задаче закрытого типа