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

Условие задачи для вариантов 1-20

На заводах A₁, A₂, A₃ производится однородная продукция в количестве a₁, a₂, a₃ единиц.

Четырем потребителям B₁, B₂, B₃, B₄ требуется соответственно b₁, b₂, b₃, b₄ единиц готовой продукции. Известны расходы c_ij ден. ед. по перевозке единицы готовой продукции с завода A_i потребителю B_i.

Необходимо найти план перевозок, минимизирующий общие затраты по изготовлению продукции на заводах A₁, A₂, A₃ и B₁, B₂, B₃, B₄.

ЗАДАНИЕ

1. Внести числовые данные транспортной задачи в распределительную таблицу.
2. Составить математическую модель задачи.
3. Если транспортная задача открытого типа, то привести ее к закрытой. Построить исходные планы перевозок по методу «северо-западного» угла () и по методу «минимального элемента» (). Вычислить значения общих затрат для построенных планов f() и f() и выявить, какой из планов лучше.
4. Методом потенциалов проверить этот план X на оптимальность.
5. последовательно улучшая план перевозок X с помощью циклов пересчета в распределительной таблице, найти оптимальный план перевозок X^опт
6. Определить по оптимальному плану перевозок X^опт

1) количество продукции, отправляемое из каждого завода A₁, A₂, A₃ каждому потребителю B₁, B₂, B₃, B₄;

2) наименьшие общие затраты на производство продукции и доставку ее потребителям;

3) заводы A_i, в которых остается нераспределенная продукция, и указать ее объем;

4) пункты потребления B_i, которые недополучают продукцию, и указать ее количество;

Вопросы для самоконтроля и подготовки к зачету

1. Запишите задачу ЛП в общей форме.

2. Запишите задачу ЛП в канонической, стандартной форме.

3. С помощью каких преобразований можно перейти от общей или. стандартной ЗЛП к канонической?

4. Дайте определения допустимого решения, оптимального решения ЗЛП.

5. Дайте определение базисного, опорного решения ЗЛП. Какую роль играют опорные решения в линейном программировании?

6. Сколько опорных решений имеет ЗЛП? Каков их геометрический смысл?

7. Сформулируйте основную теорему линейного программирования.

8. Сформулируйте основную идею симплексного метода решения ЗЛП. Какие этапы включает в себя симплексный метод?

9. Задачу линейного программирования можно решить симплексным методом, если выполнены условия:

1) система ограничений состоит из...;

2) свободные члены системы ограничений...;

3) все переменные удовлетворяют условию....

10. Таблица какого вида называется симплексной, как она заполняется?

11. Сформулируйте алгоритм симплексных преобразований в симплексных таблицах.

12. Какие преобразования необходимо осуществить, чтобы построить исходное опорное решение ЗЛП?

13. Как по симплексной таблице записать компоненты опорного решения ЗЛП?

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

15. Как вычислить оценки свободных переменных в целевой функции ЗЛП по симплексной таблице? Каков их экономический смысл в задаче об использовании сырья?

16. Чтобы перейти от опорного решения к улучшенному опорному решению, нужно для ЗЛП /— max выбрать разрешающий элемент по правилу..., а для задачи/— min выбрать разрешающий элемент по правилу.... (заполните пропущенные места).

17. Запишите формулу нахождения приращения целевой функции при переходе к новому опорному решению.

18. В каком случае можно сказать, что ЗЛП не имеет оптимального решения? Как это определить по симплексной таблице?

19. Заполните пропущенные места в формулировке правил двойственных задач (ДЗ): • если в прямой задаче ЗЛП целевая функция /— max, то в ДЗ…;

• если в прямой ЗЛП все ограничения - уравнения, то в ДЗ… Если в ЗЛП все ограничения - неравенства, то в ДЗ...;

• если в ЗЛП..., то в ДЗ все переменные неотрицательны. Если в ЗЛП..., то все ограничения в ДЗ являются уравнениями;

• свободные члены в системе ограничений прямой ЗЛП являются для ДЗ…;

• в задаче Т —> min ограничения - неравенства имеют знак…, а в задаче f — mах - ...;

• матрицы коэффициентов при переменных в прямой ЗЛП и ДЗ…

• число переменных в ДЗ равно числу.... Число переменных прямой ЗЛП равно числу....

20. Дайте экономическую и математическую постановку прямой ЗЛП об использовании сырья для производства продукции нескольких видов. Каков экономический смысл основных и дополнительных переменных X_] в оптимальном решении ЗЛП об использовании ресурсов?

21. Дайте экономическую постановку ДЗ в задаче об использовании сырья. Каковы интересы предприятия-продавца и предприятия-покупателя?

22. Запишите левую часть j -го ограничения-неравенства ДЗ, укажите экономический смысл. Почему неравенства имеют вид >?

23. Сформулируйте первую теорему двойственности и поясните экономический смысл. Всегда ли пара двойственных задач решима?

24. Какие двойственные задачи называются симметричными? Как устанавливается соответствие между переменными в прямой и двойственной симметричных задачах?

25. Как зная оптимальное решение Х ° - (х₁°,...,х_n⁰) прямой ЗЛП, найти оптимальное решение У ° = ( y₁⁰ ,…, y_n⁰) симметричной задачи ДЗ?

26. Сформулируйте и запишите математически вторую теорему двойственности.

27. Заполните пропущенные места, применяя вторую теорему двойственности:

· если первое и второе ограничения прямой ЗЛП при подстановке в них оптимального решения обращаются в строгие неравенства, то в ДЗ…;

· если в оптимальном решении ЗЛП вторая и четвёртая переменные положительны, то в ДЗ....

28. Дайте экономическое истолкование второй теоремы двойственности на примере задачи об оптимальном выпуске продукции и двойственной ей.

29. Пусть Х ° =(х ₁ °, x ₂⁰,| х₃ °, х ₄⁰, х ₅⁰) - оптимальный план задачи о производстве двух видов продукции с применением трёх ресурсов, а Y = (у₁⁰, y₂⁰, y₃⁰ | y₄⁰,y₅⁰) - оптимальный план ДЗ о ценах на ресурсы.

30. Заполните пропущенные места:

• x₂⁰ > 0, х₄⁰ > 0 экономически означают, что...;

• x₁⁰ =х₃⁰=x₅⁰ экономически означают, что...;

• Ресурсы... являются дефицитными, а ресурсы… - недефицитными, потому что....

31. Пусть Y ⁰ (y₁⁰,y₂⁰,y₃⁰| y₄⁰,y₅⁰)-оптимальный план ДЗ о ценах на ресурсы. Пусть по оптимальному плану производства двух видов продукции с применением трёх ресурсов Х°= (х₁°,х₂°,|х₃⁰х₄°,х₅⁰) выпускается только второй вид продукции и ресурсы S₁, S₃ израсходованы полностью. Заполните пропущенные места, считая, что Y ⁰ (y₁⁰,y₂⁰,y₃⁰| y₄⁰,y₅⁰)- оптимальный план ДЗ о ценах на ресурсы:

· переменные в Y ⁰ (y₁⁰,y₂⁰,y₃⁰| y₄⁰,y₅⁰) равны нулю, а переменные… положительны, потому что…;

· ресурсы… являются дефицитными, а ресурсы… - недефицитными, потому что…

32. Сформулируйте третью теорему двойственности. Где применяется эта теорема?

33. Как вычислить изменение целевой функции при изменении некоторого свободного члена системы ограничений на величину

34. Если в задаче об оптимальном плане выпуска продукции ресурсы с S₁, S₂, S₃ поочерёдно увеличить на одну условную единицу, то максимальная прибыль возрастает соответственно на... денежных единиц, а если увеличить одновременно, то - на... денежных единиц. Дайте ответ используя экономический смысл оптимального решения Y ⁰ (y₁⁰,y₂⁰,y₃⁰| y₄⁰,y₅⁰) двойственной задачи о ценах на ресурсы.

35. Каков экономический смысл основных и дополнительных переменных y_i в оптимальном решении задачи о ценах на сырьё?Дайте экономическую постановку транспортной задачи (ТЗ) по критерию стоимости.

36. Какая транспортная задача называется закрытой; открытой?

37. Каково необходимое и достаточное условие разрешимости ТЗ?

38. Запишите математическую модель закрытой ТЗ по критерии стоимости, дайте экономическое истолкование перемени ограничениям и целевой функции.

39. Сколько переменных X_ij содержит математическая модель закрытой ТЗ?

40. Сколько базисных и свободных переменных имеет ограничений ТЗ?

41. Опишите построение исходного опорного плана перевозок в распределительной таблице методом «северо-западного угла» Сколько заполненных клеток должно быть в распределительной таблице и как этого достичь?

42. Опишите построение исходного опорного плана перевозок распределительной таблице методом «минимально элемента» Сколько заполненных клеток должно быть в распределительной таблице и как этого достичь?

43. Опишите сущность метода потенциалов для нахождения оптимального перевозок ТЗ.

44. Сформулируйте признак оптимальности плана перевозок ТЗ, решаемой методом потенциалов?

45. Что называют циклом пересчета в распределительной таблице ТЗ?

46. С какой целью и как строится цикл пересчёта в распределительной таблице если план перевозок не является оптимальным? Для заполненных клеток распределительной таблицы удалось построить цикл. Что это означает?

47. Как определяется наименьшая загрузка свободной клетки, с помощью которой происходит перемещение груза по циклу?

48. Запишите формулу для вычисления оценок свободных переменных в ТЗ.

49. Каков признак альтернативного оптимума (не единственности оптимального плана перевозок) в ТЗ? Как найти в этом случае общее оптимальное решение?

Опишите процесс решения открытой транспортной задачи.