Примеры решений Теория игр Решение интегралов Пределы онлайн Деление столбиком онлайн Транспортная задача Двойственная задача Графический метод онлайн Производная онлайн Симплекс-метод

Графический метод решения задач линейного программирования с помощью таблиц Excel

Постановка задачи
Найти графическим методом максимум целевой функции

F=2x1+3x2 → max
x1+3x2≤18, (1)
2x1+x2≤16, (2)
x2≤5, (3)
3x1≤21, (4)
x1≥0, x2≥0, (5,6)
при ограничениях

Решение с помощью таблиц Excel
Вначале построим на листе Excel решение системы неравенств.
Рассмотрим первое неравенство x1+3x2≤18.
Построим граничную прямую x1+3x2=18 по двум точкам. Прямую обозначим (L1)(или Ряд1). Координаты х2 считаем по формулам:



Для построения выбираем точечную диаграмму


Выбираем данные для прямой

Изменяем название прямой:

Выбираем макет диаграммы. Изменяем название осей координат:


Прямая (L1) на графике:

Решение строгого неравенства x1+3x2≤18 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L1). Например, с помощью точки (0; 0)Ï(L1).
При подстановке координат точки (0; 0), получаем неравенство
0 + 3×0 < 18 или 0 < 18 .
Неравенство является верным, следовательно решением неравенства (1) будет та полуплоскость, в которой пробная точка расположена (на рисунке ниже прямой L1).
Затем решаем неравенство (2) 2x1+x2≤16.
Построим граничную прямую 2x1+x2=16 по двум точкам. Прямую обозначим (L2).

Прямая (L2) на графике:

Решение строгого неравенства 2x1+x2≤16 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L2). Например, с помощью точки (0; 0)Ï(L2).
При подстановке координат точки (0; 0), получаем неравенство
2×0 + 0 < 16 или 0 < 16 .
Неравенство является верным, следовательно решением неравенства (2) будет та полуплоскость, в которой пробная точка расположена (на рисунке ниже прямой L2).
Затем решаем неравенство (3) x2≤5.
Построим граничную прямую x2=5 по двум точкам. Прямую обозначим (L3).
На листе Excel добавляем данные


Прямая (L3) на графике:

Решение строгого неравенства 2x2<5 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L3). Например, с помощью точки (0; 0)Ï(L3).
При подстановке координат точки (0; 0), получаем неравенство
0 < 5 .
Неравенство является верным, следовательно решением неравенства (3) будет та полуплоскость, в которой пробная точка расположена (на рисунке ниже прямой L3).
Затем решаем неравенство (4) 3x2≤21.
Построим граничную прямую 3x2=21 по двум точкам. Прямую обозначим (L4).
На листе Excel добавляем данные


Прямая (L4) на графике:

Решение строгого неравенства 3х1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).
При подстановке координат точки (0; 0), получаем неравенство
0 < 21 .
Неравенство является верным, следовательно, решением неравенства (4) будет та полуплоскость, в которой пробная точка расположена (на рисунке левее прямой L4).
Решением двух неравенств (5) и (6) x1≥0 и x2≥0 является 1-ая четверть, ограниченная координатными прямыми x1=0 и x2=0.
Система неравенств решена. Решением системы неравенств (1) – (6) в данном примере является выпуклый многоугольник в левом нижнем углу рисунка, ограниченный прямыми L1, L2, L3, L4 и координатными прямыми x1=0 и x2=0. Убедиться, что многоугольник выбран правильно, можно подстановкой пробной точки, например (1; 1) в каждое неравенство исходной системы. При подстановке точки (1; 1) получаем, что все неравенства, в том числе естественные ограничения, верные.
Рассмотрим теперь целевую функцию
F = 2x1 + 3x2.
Построим линии уровня для значений функции F = 0 и F = 12 (числовые значения выбраны произвольно). На листе Excel добавляем данные

Линии уровней на графике:

Построим вектор направлений (или градиент) {2; 3}. Координаты вектора совпадают с коэффициентами целевой функции F.
Добавляем на листе Excel координаты начальной и конечной точки вектора.

Вектор на рисунке:

Градиент указывает направление увеличения целевой функции F.
Теперь следует линию уровня F=0 передвинуть параллельно до последней точки угловой точки выпуклого многоугольника. Последней угловой точкой пересечения выпуклого многоугольника и передвинутой линии уровня будет точка пересечения прямых L1 и L2. Для нахождения координат точки решим систему уравнений
x1+3x2=18
2x1+x2=16
Решаем систему уравнений по формулам Крамера. Для этого на листе Excel создаем массивы для определителей. Для вычисления определителей используем математическую функцию МОПРЕД

Выделяем массив определителя



Находим значения х1 и х2


Пересечением прямых L1 и L2 будет точка с координатами (6; 4).
Подставляем координаты точки в целевую функцию
Fmax= 2×6 +3×4 = 24
Ответ: Fmax= 24 при x1=6 и x2=4.
Формулы в MS Word
Конвертируем формулы из изображения в MS Word.
Из картинки в Word
Метод Гомори
Метод Гомори
Метод Гомори. Решение задачи целочисленного программирования
Решить онлайн
Транспортная задача
Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1234b
112436
243858
3276310
a4688 
Решить онлайн