Задача 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 ед. продукции.

Примечаний нет.