Графический метод линейного планирования (программирования)

34. Решить задачу линейного программирования (прямая задача 2 условные задачи, двойственная 1 условная задача, все вместе -3 у.з.)

Теория Пусть дана задача

(Условие примера взято из учебника Кремер Н.Ш. Исследование операций).

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

Чтобы построить эту линию границы на плоскости нам необходимы две точки (обычно берут точки пересечения с осям координат, полагая одну из координат равной 0).

При желании также можно рассмотреть и тривиальные ограничения – единственное отличие в том, что тестовой точкой не может быть точка O(0,0)

Строим линии границ

Проводим вектор частных производных – вектор градиента целевой функции, отложенный от начала координат:

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

Выявляем активные ограничения. Записываем эту систему как систему равенств.

Решим полученную систему

Вычислим значение целевой функции

Напишем

Условие:

35. Пользуясь теоремой двойственности (графическим методом) решить задачу двойственную к предыдущей. Сравнить ответы. (Задачи решаются комплектом).

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

36. Транспортная задача (тест) (в этой задаче в abcd параметрах 10-ки не откидываются!!)

1. (Tз4x4) (стоимость до 4х задач – в ИЗРЯДНОЙ зависимости от числа переходов!!, ибо возможно до 4-5ти шагов):

2. Условие1 (не проверенное)

3. 

4. Условие 2: (в среднем 7 итераций).

решение:

1. Исходное решение построить методом минимального элемента. Найти потенциалы,

2. (repeatпока не достигните успеха): построить цикл пересчёта, переходя к новому решению вплоть до нахождения оптимума. (Методом потенциалов вновь и вновь проверять оптимальность – критерий оптимальности – отсутствие отрицательных ЦЕН поставок вне базисного плана после применения потенциалов на очередной итерации).

3. Вычислить Целевую функцию, записать в ответе значение ЦФ и оптимальный план.

1. (1,5/2 уз) (решается только один из всех пунктов)

2. 

37. Транспортная задача (Исследование операций, та же презентация)1

	Одесса 50(c+a)	Минск 200a	Томск 140(c+b)	Львов 80a
Мкв 180a	11a	10	60	11d
СПб 140b	6d	20c	10a	5(2a+с+d)
Владивосток 190c	5a	3b	8c	14+b+c
Ростов 150a	20	5(d+c)	5(a+c+d)	5(c+1+ d)

7. Транспортная задача2(устаревший архивный вариант) (не решается как несбалансированный вариант)

	Тамбов 160	Тверь 200	Томск 120
М 100	11a	10	60
СПб 130	6d	20c	10a
Ввост 250	5a	3b	8c

Дополнительные матрицы

38. Решить задачу о назначениях

по модулю 32, перевести в двоичное представление, рассмотреть как 0-1 матрицу инцидентности неоснащённого двудольного графа, построить оптимальное назначение.