Решить задачу линейного программирования графическим методом программирование

Задача 1 Решить задачу линейного программирования графическим методом.

Решение.
На плоскости построим многоугольник решений.
Построим граничные прямые: , .
Чтобы определить расположение соответствующей полуплоскости, подставим координаты точки .
Задача 2
Решить задачи симплекс методом

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

Решение.
Составим модель двойственной задачи.

Напишем модель задачи, двойственной к исходной задаче:

Решим двойственную задачу графическим методом.
Построим граничные прямые

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

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

Ответ: .

Задача 4
Составить план перевозок по доставке требуемой продукции из пункта в пункты назначения минимизирующий суммарные транспортные расходы. Стоимость перевозки из пункта i в пункт j единиц груза заданы таблицей
.
Решение.
Составим математическую модель задачи. Через – обозначим объем продукции, доставленный от поставщика потребителю
27+28+29=84. 10+20+30=60. Задача открытого типа.
Введем фиктивного поставщика с запасом продукции 84–60 = 24
Математическая модель задачи имеет вид:

Составим начальную распределительную таблицу методом минимального элемента.

5 4 3 10 0
1 9

6 2 1 20 –2
20

3 2 7 30 –2
2 28

0 0 0 24 –5
24

27 28 29 84

5 4 3
Получили опорный план.

Данному плану отвечают затраты
.
Для исследования полученного плана на оптимальность найдем потенциалы и поставщиков и потребителей. По заполненным клеткам составим систему уравнений:
Откуда получим .
Вычислим оценки свободных клеток по формуле: .
; ; ; ;
;
Среди оценок нет отрицательных, значит, план оптимален.
Суммарные затраты составят 108 ден. ед.
По плану первый поставщик отправит 1 ед. продукции первому потребителю, 9 ед. продукции третьему потребителю.
Второй поставщик отправит 10 ед. продукции третьему потребителю.
Третий поставщик отправит 2 ед. продукции первому потребителю, 28 ед. продукции второму потребителю.
Первый поставщик недополучит 24 ед. продукции.