55. Метод потенциалов. Псевдостоимость. Условия оптимальности плана.

4.4. Проверка лучшего опорного плана на оптимальность

Для проверки плана на оптимальность можно применить метод потенциалов.

Для этого надо ввести так называемые псевдостоимости . Входящие в псевдостоимости величины _i и _j называют потенциалами. Псевдостоимости обладают следующими свойствами:

при x_ij  0 (базисные клетки); (4.1)

при x_ij = 0 (свободные клетки). (4.2)

Кроме того, псевдостоимости могут быть отрицательными.

Для транспортной задачи 4х6 введем величины ₁, ₂, ₃, ₄, соответствующие первым четырем ограничениям, и ₁, ₂, ₃, ₄, ₅, ₆ – остальным ограничениям.

Запишем условия (4.1) для базисных клеток:

 ₁ + ₂ = 1;

₁ + ₄ = 1;

₂ + ₂ = 1;

₂ + ₅ =7;

₂ + ₆ = 4;

₃ + ₃ = 4;

 ₃ + ₅ =7;



(4.3)

₄ + ₁ =1;

₄ + ₅ =9.

Запишем условия (4.2) для свободных клеток:

 ₁ + ₁  7;

₁ + ₃  8;

₁ + ₅  5;

₁ + ₆  3;

₂ + ₁  7;

₂ + ₃  8;

₂ + ₄  5;

₃ + ₁  3;

₃ + ₂  7;

₃ + ₄  5;

 ₃ + ₆  5;

₄ + ₂  2;



(4.4)

₄ + ₃  4;

₄ + ₄  9;

₄ + ₆  9.

Система (4.3) состоит из 9 уравнений и содержит 10 переменных: . Поскольку число независимых переменных в данной системе равно 4 + 6  1 = 9, то одна переменная из множества  или  свободная. Пусть это будет ₁. Положив ₁=0, получим: ₁ = 0, ₂ = 0, ₃ =2, ₄ = 4, ₁  = –3, ₂ =1, ₃ = 2, ₄ = 1, ₅ = 5, ₆ = 4. Составим таблицу перевозок, соответствующую данному решению (табл. 4.7).

Полученное решение ₁, ₂, ₃, ₄, ₁, ₂, ₃, ₄, ₅, ₆ подставляем в систему (4.4), т.е. в пустые клетки. Если ограничения системы (4.4) являются верными неравенствами при найденном решении, то проверяемый допустимый план исходной задачи является оптимальным, иначе  план не оптимален, и его надо улучшать.

Из табл. 4.7 видно, что при данном решении не выполняются четвертое, одиннадцатое, двенадцатое и тринадцатое неравенства системы (4.4) – им соответствуют клетки А₁В₆, А₃В₆, А₄В₂, А₄В₃. Это значит, что полученное решение не оптимально, его необходимо улучшить.

Таблица 4.7

Проверка плана ТЗ на оптимальность и первый цикл пересчета

	1 = –3	2 = 1	3 = 2	4 = 1	5 = 5	6 = 4
1 = 0	–3  7	1 = 1	2  8	1 = 1	5  5	4  3
		5		20
– 2 = 0	–3  7	1 = 1	2  8	1  5	5 = 5	4 = 4
		6			5	21
3 = 2	–1  3	3  7	4 = 4	3  5	7 = 7	6  5
			24		7
+ + – 4 = 4	1 = 1	5  2	6  4	5  9	9 = 9	8  9
	18				16

56. Приведение транспортной задачи с неправильным балансом к сбалансированной задаче.

57 Особенности решения транспортной задачи по критерию времени. Метод запрещенных клеток.

Задача линейного программирования (ЗЛП).

44. 3адача о пищевом рационе.

45. 3адача о загрузке станков.

Термин линейное программирование появился в Америке в середине 40-х годов (первая американская работа по частной задаче линейного программирования опубликована в 1941 г.). В Советском Союзе исследования в этой области начались ранее. В конце 30-х годов целый ряд существенных результатов по линейному программированию был установлен Л.В. Канторовичем.

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

Задачи линейного программирования являются самыми простыми и лучше изученными задачами. Для них характерно: показатель эффективности (целевая функция) выражается линейной зависимостью; ограничения на решения – линейные равенства или неравенства.